0

インターフェイスメソッドの実装を求める割り当ての質問がありますisHamiltonian。再帰を使用して問題を解決しようとしました。

条件を満たすパスがある場合は、ノードからのすべてのパスを試すだけです。

  • すべてのノードを1回だけ移動します
  • 最後のノードは最初のノードに直接接続されています

ハミルトニアンだと思います。

これらのコードを試しましたが、機能しません

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)、 final の前に置くことです。return false次に、結果も保存し、isHamiltonian(start,nodes[i],hs)それが true の場合に終了します。このようなもの

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

これで大分直るはずです。この徹底的な検索はかなり遅くなると思います。

EDIT : 全体は次のようになります。

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 に答える