2

これは、グラフ内のハミルトニアン サイクルを見つけるための私のアルゴリズムです。

private SolutionArray solution;
private int V, pathCount;
private int[] path;
private int[][] graph;

/**
 * Constructor
 */
public ConcreteSolver() {
    solution = new SolutionArray();
}

@Override
public SolutionArray solve(PathMatrix input) {

    V = input.getNbVertex();
    path = new int[V];

    /** Set all path to non-visited **/
    boolean[] visited = new boolean[V];
    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }

    Arrays.fill(path, -1);
    graph = input.getMatrix();

    try {
        path[0] = input.getFirstVertex();
        pathCount = 1;

        findPaths(0);

        System.out.println("No solution");
    } catch (Exception e) {

        System.out.println("\nSolution found");
        //input.printMatrix();
        displayAndWrite();
    }

    return solution;

}

/**
 * function to find paths recursively
 */
private void findPaths(int vertex) throws Exception {


    /** solution **/
    if (graph[vertex][0] >= 1 && pathCount == V) {
        throw new Exception();
    }
    /** all vertices selected but last vertex not linked to 0 **/
    if (pathCount == V)
        return;

    for (int v = 0; v < V; v++) {
        /** if connected **/
        if (graph[vertex][v] >= 1) {
            /** add to path **/
            path[pathCount++] = v;

            /** if vertex not already selected solve recursively **/
            if (!isPresent(v))
                findPaths(v);

            /** remove path **/
            path[--pathCount] = -1;

        }

    }

}

/**
 * function to check if path is already selected
 */
private boolean isPresent(int v) {
    for (int i = 0; i < pathCount - 1; i++)
        if (path[i] == v)
            return true;
    return false;
}

最初のハミルトニアン サイクルを 1 つ見つけることができます。グラフで見つかったすべての可能なハミルトニアンサイクルを見つけるように適応させることは可能ですか?

入力は非対称行列 (ノード間の一部のリンクは一方向) であり、一部のノードは他のノードへの 2 つまたは 3 つのリンクを持つ場合があります。

ありがとうございました

編集：

明確にするために、アルゴリズムは既に解決策を見つけることができますが、2 番目の解決策を見つけることはできません。読んだところ、バックトラッキングを使用する A* で問題が解決する可能性がありますが、既に持っているものに追加できるかどうかはわかりません。

4

2 に答える 2

1

現在、探索中の現在のパスをキャプチャするための単一の配列があります。おそらく、displayAndWriteメソッドはこの情報を使用してソリューションを出力します。

すべてのソリューションを記録するには、ハミルトニアン サイクルを見つけたときにパスのコピーを取得する必要があります。

次のようなもの:

private static final int MAX_SOLUTIONS = 100;
private int[][] solutions = new int[MAX_SOLUTIONS][];
private int solutionCount = 0;

private void addSolution(int[] path) {
    if (solutionCount < MAX_SOLUTIONS)
        solutions[solutionCoun++] = Arrays.copyOf(path, path.length);
}

addSolution現在例外が発生している再帰メソッドを呼び出す必要があります。

余談ですが、成功を示すために例外をスローすることは、ほぼすべての経験豊富な Java コーダーにとって不適切なスタイルと見なされます。他の言語でも同じことが当てはまると思います-例外は例外です:-)

于 2015-11-12T23:32:16.317 に答える
0

現在、サイクルを検出したときに例外をスローします。

if (graph[vertex][0] >= 1 && pathCount == V) {
    throw new Exception();
}

例外をスローすることは実際には例外的な状態ではないため、ここで行うのは間違っているという事実は別として-質問に対する私のコメントを参照してください-サイクルが少ないことがわかったときに実行するアクションを作成するだけです「爆発物」。

の定義がわからSolutionArrayないと、それを利用して答えを出すことはできません。

いくつのサイクルが見つかるかわからないため、 a を追加しListて解を収集します。

private List<int[]> solutions = new ArrayList<>();

解決策が見つかったら、このリストに何かを追加して、メソッドから戻ります。

if (graph[vertex][0] >= 1 && pathCount == V) {
    solutions.add(java.util.Arrays.copyOf(path, V));
    return;
}

これは、例外をスローするのではなく、単にメソッドから戻るため、呼び出し元の関数の実行が続行され、次の可能なパスがチェックされます。

パスのコピーを取得することが重要です。それ以外の場合は、作業コピーとして使用している配列への参照を追加するだけなので、それらはすべて同じ配列になり、後で更新する可能性があるため、最後に有効なソリューションが含まれているとは限りません。

次に、メイン メソッドで、このリストが空でないかどうかを確認します。

if (!solutions.isEmpty()) {
  System.out.println("\nSolution(s) found");
  displayAndWrite();
}
于 2015-11-13T00:06:45.310 に答える