2

深さ優先探索アルゴリズムを使用してナイト ツアー問題を解こうとしています。両方とも行き止まりになる 2 つの選択肢がある場合、アルゴリズムは常にループしているように見えます。これは、行き止まりが見つかるたびにアルゴリズムが「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;
}

5x5 ボードでこれを解決しようとしているので、25 個の頂点 (0 - 24) があります。現在の問題がより明確になる出力の一部を次に示します。

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

もちろん、出力の最後のループは発生しないはずです。

4

1 に答える 1

4

これを例で説明します。

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もう 1 つレベルを上げる必要がある場合は、小さな問題が 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;
}
于 2012-01-15T14:28:37.847 に答える