0

我在 Java（图论）中编写了一个递归函数来获取 4x4 表中的所有路径，从随机起点开始。可能的方向是水平、垂直和对角线，但我要求不能两次访问同一位置。

到目前为止，该脚本运行良好，我得到了很多组合。问题是，在函数的 for 循环中，当有不止一种可能的方法时，我会在第二个和后续循环中得到错误的结果，因为 boolean[] tempvisited 没有恢复到他的旧值。

我希望有人能理解我的英语和我的问题。到目前为止，这是我的代码：

// 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 回答