0

Java (グラフ理論) で再帰関数を作成して、ランダムな開始点から始まる 4x4 テーブル内のすべてのパスを取得しています。可能な方向は水平、垂直、斜めですが、同じ場所を 2 回訪れてはならないという要件があります。

スクリプトはこれまでのところ正常に動作し、多くの組み合わせが得られます。問題は、関数の for ループで、複数の可能な方法がある場合、2 番目以降のループで間違った結果が得られることです。

私の英語と私の問題も理解してくれる人がいることを願っています。これまでの私のコードは次のとおりです。

// here I define a constant input of values:
String letters = "1548987425461854"

// This matrix shows all possible directions from every startpoint in the matrix:
// from the second value, you may get to the following locations: 1,3,5,6 and 7
    private int[][] matrix = {
        {1,4,5},
        {0,2,4,5,6},
        {1,3,5,6,7},
        {2,6,7},
        {0,1,5,8,9},
        {0,1,2,4,6,8,9,10},
        {1,2,3,5,7,9,10,11},
        {2,3,6,10,11},
        {4,5,9,12,13},
        {4,5,6,8,10,12,13,14},
        {5,6,7,9,11,13,14,15},
        {6,7,10,14,15},
        {8,9,13},
        {8,9,10,12,14},
        {9,10,11,13,15},
        {10,11,14}
};

// Here begins the recursive function 
public List<Combination> depthFirst(int vertex, boolean[] visited, Combination zeichen, List<Combination> combis){
  // A temporary list of booleans to mark every value position visited or not
  boolean[] tempvisited = new boolean[16];

  // combis is the whole list of ways, zeichen is just the actual combination
  zeichen.name = zeichen.name + this.letters.charAt(vertex);
  combis.add(zeichen.name);

    //marks actual value as visited
    visited[vertex] = true;
    for(int i = 0; i < 16; i++){
        tempvisited[i] = visited[i];
    }//end for

    // going to next possible locations
    for (int i = 0; i < this.matrix[vertex].length; i++) {
        if (!visited[this.matrix[vertex][i]]) {         
            combis = depthFirst(this.matrix[vertex][i], tempvisited, zeichen, combis);      
        }//end if
    }//end for
    return combis;
}
4

4 に答える 4

0

あなたは、コピーを作成することで正しい考えを持ってtempvisitedいます。しかし、あなたは間違った場所でそうしています。

設定しています。これは、渡したものが変更されていることvisited[vertex] = trueを意味します。visitedあなたが望むのはvisited決して変わらないことです。そのコピーを作成し、そのコピーに変更を加えます。

zeichenまた、毎回同じものを使用していることに気づきました。したがって、3ステップの長さのパスがある場合、combisリストは同じの3つのコピーになりzeichenます。それは間違っているようです。

于 2013-03-11T20:46:04.527 に答える
0

最初のforループの前にvisited[vertex]をtrueに設定しました。戻る直前にfalseにリセットできます。すべての呼び出しが（直接）行った変更を元に戻すと、すべての呼び出しは、その呼び出しが行われたときの状態に戻って訪問して戻ります。誘惑は必要ありません。

于 2013-03-11T20:47:25.110 に答える
0

深さ優先探索（DFS）のこの他の再帰的ソリューション（擬似コード）を見てください。

void search(Node root) {
 if (root == null) return;

 visit(root);
 root.visited = true;
 foreach (Node n in root.adjacent) {
  if (n.visited == false)
   search(n);
 }
}
于 2013-03-11T20:47:53.147 に答える
0

実際には、訪問した配列のコピーは必要ありません。繰り返しのdepthFirstの呼び出しの直前にノードを訪問済みとしてマークし、呼び出しの直後に「マークを外します」。何かのようなもの：

for (int i = 0; i < this.matrix[vertex].length; i++) {
    if (!visited[this.matrix[vertex][i]]) {     
        visited[this.matrix[vertex][i]] = true;  
        combis = depthFirst(this.matrix[vertex][i], tempvisited, zeichen, combis);      
        visited[this.matrix[vertex][i]] = false;
    }//end if
}//end for
于 2013-03-11T20:48:08.253 に答える