Рыцарский тур - поиск в глубине бесконечного цикла

Question

Я пытаюсь решить проблему коня , используя алгоритм поиска в глубину. Алгоритм кажется зацикленным всякий раз, когда у него есть два варианта, которые приводят к тупику. Я понимаю, что это вызвано тем, что алгоритм сбрасывает логическое значение 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;
}

Заранее спасибо:).

Edit:

Вот обновленный код и немного вывода:

    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;
}

Я пытаюсь решить эту проблему для доски 5х5, чтобы было 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

Цикл в конце вывода, конечно, не должен происходить.

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;
}