騎士的遊覽深度優先搜索無限循環

Question

我試圖使用深度優先搜索算法來解決knight's tour問題。只要有兩個選擇導致死衚衕，算法似乎都會循環。我知道這是由於算法將'wasVisited'布爾值重新設置爲false，無論何時發現死衚衕，但我根本不知道如何解決它。

下面的代碼我到目前爲止：

public void dfs() { 
    vertexList[0].wasVisited = true; 
    theStack.push(0); 
    System.out.println("Visited: 0"); 

    while (!theStack.isEmpty()) { 
     int v = getAdjUnvisitedVertex(theStack.peek()); 
     if (v == -1) { 
      vertexList[lastVisited].wasVisited = false; 
      theStack.pop(); 
      System.out.println("Go back to: " + theStack.peek()); 
     } else { 
      vertexList[v].wasVisited = true; 
      lastVisited = v; 
      System.out.println("Visited: " + v); 
      theStack.push(v); 
     } 
    } 

    for (int j = 0; j < nVerts; j++) { 
     vertexList[j].wasVisited = false; 
    } 

} 

public int getAdjUnvisitedVertex(int v) { 
    for (int j = 0; j < nVerts; j++) { 
     if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false) { 
      if (j != lastVisited) { 
       return j; 
      } 
     } 
    } 
    return -1; 
} 

感謝提前:)。

編輯：

下面是更新後的代碼和一個位輸出：

public void dfs() { 
    vertexList[0].wasVisited = true; 
    theStack.push(0); 
    System.out.println("Visited: 0"); 

    while (!theStack.isEmpty()) { 
     int v = getAdjUnvisitedVertex(theStack.peek()); 
     if (v == -1) { 
      vertexList[lastVisited].wasVisited = false; 
      theStack.pop(); 
      System.out.println("Go back to: " + theStack.peek()); 
      int backTo = theStack.peek(); 
      int newDestination = getNextAdjVertex(backTo, lastVisited); 
      lastVisited = newDestination; 
      while (newDestination == -1) { 
       theStack.pop(); 
       backTo = theStack.peek(); 
       System.out.println("Go back to: " + backTo); 
       newDestination = getNextAdjVertex(backTo, lastVisited); 
       lastVisited = newDestination; 
       if (newDestination != -1) { 
        vertexList[newDestination].wasVisited = false; 
       } 
      } 
      System.out.println("New Destination " + newDestination); 
      vertexList[newDestination].wasVisited = true; 
      lastVisited = newDestination; 
      System.out.println("Visited: " + newDestination); 
      theStack.push(newDestination); 
     } else { 
      vertexList[v].wasVisited = true; 
      lastVisited = v; 
      System.out.println("Visited: " + v); 
      theStack.push(v); 
     } 
    } 

    for (int j = 0; j < nVerts; j++) { 
     vertexList[j].wasVisited = false; 
    } 

} 

public int getNextAdjVertex(int currentVertex, int vertexICameFrom) { 
    for (int j = 0; j < nVerts; j++) { 
     if (adjMat[currentVertex][j] == 1 && vertexList[j].label != vertexICameFrom && vertexList[j].wasVisited == false) { 
      return j; 
     } 
    } 
    return -1; 
} 

public int getAdjUnvisitedVertex(int v) { 
    for (int j = 0; j < nVerts; j++) { 
     if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false) { 
      if (j != lastVisited) { 
       return j; 
      } 
     } 
    } 
    return -1; 
} 

我想這樣也有25個verticles（0 - 24）來解決這個一個5x5的主板。這裏有一個位在當前的問題變得更加清晰的輸出：

Visited: 0 
Visited: 7 
Visited: 4 
Visited: 13 
Visited: 2 
Visited: 5 
Visited: 12 
Visited: 1 
Visited: 8 
Visited: 11 
Visited: 18 
Visited: 9 
Go back to: 18 
New Destination 21 
Visited: 21 
Visited: 10 
Visited: 17 
Visited: 6 
Visited: 3 
Visited: 14 
Visited: 23 
Visited: 16 
Go back to: 23 
Go back to: 14 
Go back to: 3 
Go back to: 6 
New Destination 15 
Visited: 15 
Visited: 22 
Visited: 19 
Go back to: 22 
Go back to: 15 
Go back to: 6 
Go back to: 17 
New Destination 20 
Visited: 20 
Go back to: 17 
New Destination 24 
Visited: 24 
Go back to: 17 
New Destination 20 
Visited: 20 
Go back to: 17 
New Destination 24 
Visited: 24 

在輸出末端的循環被着，當然，不應該發生的。

Answer 1

我會用一個例子來說明這一點：

A - B - D 
    | 
    C 

當代碼獲取到節點C，發現沒有其他的頂點去：v == -1。然後會發生什麼，它會清除C並返回B.這一切都很好。但是，在B我們只知道我們從哪裏來（堆棧包含[A,B]）。現在它找到了第一個未訪問的頂點，但這又是C了！

你需要什麼，當你從C上升到B，然後找到下一個要訪問的頂點。你需要列出所有相鄰的順序。

int getNextAdjVertex(int currentVertex,int vertexICameFrom) { 
    return the first vertex adjacent to currentVertex, bigger than vertexICameFrom 
    or -1 if it does not exist 
} 

if (v == -1) { 
    vertexList[lastVisited].wasVisited = false; 
    System.out.println("Go back to: " + theStack.peek()); 
    //going down in the right direction: 

    int backTo = theStack.peek(); 
    int newDestination = getNextAdjVertex(backTo,lastVisited); 

    //now same as the else part, a step downward 
    vertexList[newDestination].wasVisited = true; 
    lastVisited = newDestination; 
    System.out.println("Visited: " + newDestination); 
    theStack.push(newDestination); 
} 

只有一個小問題，如果newDestination == -1你需要上升一個級別。你必須在循環中這樣做，直到有一個未訪問的頂點。

---

我認爲問題出在getNextAdjVertex。

System.out.println("Go back to: " + theStack.peek()+","+lastVisited); 

將提供更多有用的信息來發現問題。但我認爲這應該工作：

public int getNextAdjVertex(int currentVertex, int vertexICameFrom) { 
    for (int j = vertexICameFrom+1; j < nVerts; j++) { 
     if (adjMat[currentVertex][j] == 1 && !vertexList[j].wasVisited) { 
      return j; 
     } 
    } 
    return -1; 
}