ナイトツアーの深さ優先探索無限ループ

Question

深度優先探索アルゴリズムを使用してknight's tour問題を解決しようとしています。アルゴリズムは、どちらもデッドエンドになるという2つの選択肢があるときはいつでもループしているように見えます。これはアルゴリズムが 'deadVisited'ブール値を再び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

私はつもりは一例でこれを説明しています：v == -1：コードは、ノードCになると

A - B - D 
    | 
    C 

、それはに行くためには他の頂点を見つけていません。何が起きたら、それは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); 
} 

使用すると、1つの以上のレベルに行く必要がnewDestination == -1場合のみ、一つの小さな問題が、あります。あなたはループでそれをしなければならないでしょう、unvisited頂点があるまで上がってください。

---

問題は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; 
}