2

我正在尝试使用深度优先搜索算法来解决骑士之旅问题。每当算法有两个都导致死胡同的选择时，它似乎就在循环。我知道这是因为算法会在发现死胡同时再次将“wasVisited”布尔值重置为假，但我根本不知道如何解决它。

这是我到目前为止的代码：

  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你需要再上一层。您必须循环执行此操作，直到出现未访问的顶点。

我认为问题出在 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 回答