0

我有一个作业问题，要求实现接口方法isHamiltonian，我尝试使用递归来解决问题。

这个想法只是简单地尝试来自节点的所有路径，如果存在满足条件的路径

  • 只遍历所有节点一次
  • 最后一个节点直接连接到第一个节点

我会说这是哈密顿量。

我已经尝试过这些代码，但它不起作用

public static boolean isHamiltonian(Graph g) throws InvalidGraphException {
    if (g == null || !(g instanceof GraphI) || ((GraphI) g).getDirected()) {
        throw new InvalidGraphException();
    }

    NodeI[] nodes = (NodeI[]) g.nodes();
    if (nodes.length < 3)
        return false;

    return isHamiltonian(nodes[0], nodes[0], new HashSet<NodeI>());
}

private static boolean isHamiltonian(NodeI start, NodeI n, HashSet<NodeI> hs) {
    hs.add(n);
    NodeI[] nodes = n.getReachableNeighbours();
    boolean connectedWithStart = false;
    for (int i = 0; i < nodes.length; i++) {
        if (nodes[i].compareTo(start) == 0) {
            connectedWithStart = true;
            break;
        }
    }
    if (hs.size() == n.getGraph().nodes().length && connectedWithStart) {
        return true;
    }
    for (int i = 0; i < nodes.length; i++) {
        if (!hs.contains(nodes[i]))
            isHamiltonian(start, nodes[i], hs);
    }

    return false;
}
4

1 回答 1

1

在我看来，您的回溯是问题所在。您贪婪地将节点添加到您hs的路径以构建您的路径，但是当您无法创建循环/没有任何路可走时，您不会删除它们。

我要做的第一件事是放在hs.remove(n)最后的return false. 然后我也会保存结果isHamiltonian(start,nodes[i],hs)并在它为真时退出。像这样的东西

boolean result = isHamiltonian(start,nodes[i],hs);
if(result)return true;`

那应该解决很多。我确实认为这种详尽的搜索会很慢。

编辑：整个事情应该是这样的：

private static boolean isHamiltonian(NodeI start, NodeI n, HashSet<NodeI> hs) {
    hs.add(n);
    NodeI[] nodes = n.getReachableNeighbours();
    boolean connectedWithStart = false;
    for (int i = 0; i < nodes.length; i++) {
        if (nodes[i].compareTo(start) == 0) {
            connectedWithStart = true;
            break;
        }
    }
    if (hs.size() == n.getGraph().nodes().length && connectedWithStart) {
        return true;
    }
    for (int i = 0; i < nodes.length; i++) {
        if (!hs.contains(nodes[i])){
            boolean result=isHamiltonian(start, nodes[i], hs);
            if(result)return true;
        }
    }
    hs.remove(n);
    return false;
}

问题本身是 NP 难的，所以不要指望通用图的快速解决方案。阅读一些基本算法并决定是否值得花时间为您的应用程序实现。

于 2013-02-12T11:25:10.467 回答