Java中的骑士之旅（递归），使用图和DFS

Question

我认为在这篇文章中粘贴整个类可能代码太多（可能不够相关），所以我在这里显示它们：

graph.java

depthFirstSearch.java

0  1  2  3  4
5  6  7  8  9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24

可能的骑士步骤是这样定义的（在主类中）（使用图的边G）：

G.addEdge(0, 11);
G.addEdge(0, 7);

G.addEdge(1, 8);
G.addEdge(1, 10);
G.addEdge(1, 12);

G.addEdge(2, 5);
G.addEdge(2, 9);
G.addEdge(2, 11);
G.addEdge(2, 13);

G.addEdge(3, 6);
G.addEdge(3, 12);
G.addEdge(3, 14);

G.addEdge(4, 7);
G.addEdge(4, 13);

G.addEdge(5, 2);
G.addEdge(5, 12);
G.addEdge(5, 16);

G.addEdge(6, 15);
G.addEdge(6, 17);
G.addEdge(6, 3);
G.addEdge(6, 13);

G.addEdge(7, 0);
G.addEdge(7, 4);
G.addEdge(7, 10);
G.addEdge(7, 14);
G.addEdge(7, 16);
G.addEdge(7, 18);

G.addEdge(8, 1);
G.addEdge(8, 17);
G.addEdge(8, 19);
G.addEdge(8, 11);

G.addEdge(9, 2);
G.addEdge(9, 12);
G.addEdge(9, 18);

G.addEdge(10, 1);
G.addEdge(10, 21);
G.addEdge(10, 7);
G.addEdge(10, 17);

G.addEdge(11, 0);
G.addEdge(11, 2);
G.addEdge(11, 20);
G.addEdge(11, 22);
G.addEdge(11, 8);
G.addEdge(11, 18);

G.addEdge(12, 1);
G.addEdge(12, 3);
G.addEdge(12, 21);
G.addEdge(12, 23);
G.addEdge(12, 5);
G.addEdge(12, 9);
G.addEdge(12, 15);
G.addEdge(12, 19);

G.addEdge(13, 2);
G.addEdge(13, 4);
G.addEdge(13, 22);
G.addEdge(13, 24);
G.addEdge(13, 6);
G.addEdge(13, 16);

G.addEdge(14, 3);
G.addEdge(14, 23);
G.addEdge(14, 7);
G.addEdge(14, 17);

G.addEdge(15, 6);
G.addEdge(15, 12);
G.addEdge(15, 22);

G.addEdge(16, 5);
G.addEdge(16, 7);
G.addEdge(16, 13);
G.addEdge(16, 23);

G.addEdge(17, 6);
G.addEdge(17, 8);
G.addEdge(17, 10);
G.addEdge(17, 14);
G.addEdge(17, 20);
G.addEdge(17, 24);

G.addEdge(18, 7);
G.addEdge(18, 9);
G.addEdge(18, 11);
G.addEdge(18, 21);

G.addEdge(19, 8);
G.addEdge(19, 12);
G.addEdge(19, 22);

G.addEdge(20, 11);
G.addEdge(20, 17);

G.addEdge(21, 10);
G.addEdge(21, 12);
G.addEdge(21, 18);

G.addEdge(22, 11);
G.addEdge(22, 13);
G.addEdge(22, 15);
G.addEdge(22, 19);

G.addEdge(23, 12);
G.addEdge(23, 14);
G.addEdge(23, 16);

G.addEdge(24, 13);
G.addEdge(24, 17);

int currentSquare = 20;
calculatePath(currentSquare);
System.out.println("From square " + currentSquare + " there are " + tours + " possible tours.");

以下是我试图找到的可能的旅行：

  private static void calculatePath(int currentSquare) {
        boolean foundChoice = false;
        for (int point : G.adj(currentSquare)) {

            if (dfs.marked(currentSquare)) {
                foundChoice = true;
//              dfs.unmark(currentSquare);
                calculatePath(point);
            }
        }
        if (!foundChoice) {
            tours++;
            dfs.unmark(currentSquare);
        }
        System.out.println(currentSquare + " - tours: " + tours);
    }

例如，如果我试图通过calculatePath(20)调用这个递归函数，它应该使用字段上的每个平方返回该平方中所有可能的tour(tours)。

未标记的方块是已经到达的方块，在同一次旅行中不应该再访问了。

现在的问题是，我不能让calculatePath跳过已经访问过的方块（输出显示它从20到17，从20到11，然后停止递归方法）。

此外，该方法还不能计算多次旅行。我想先正确计算一条路径，最终计算出所有可能的游览。

我使用的所有代码都在这篇文章中得到了重视，包括上面链接中的类。

Answer 1

这段代码仍然存在一些问题，但看起来您正在取得进展。

您的方法depthfirstsearch.marked在我看来是错误的。如果它成功地将标记从false更改为true，我会认为它应该返回true。这里只返回标记为[w]的值。

您的DepthFirstSearch构造函数似乎试图标记所有相邻的点（以及它们的所有相邻点）。这似乎很奇怪--你指望这怎么起作用？避免循环的常规DFS机制是在递归时所触及的每个位置留下标记，并在递归完成时移除标记。在这里，你似乎在开始时标记了所有方块，然后当你完成了所有邻接的一轮而没有找到标记的方块时，就取消了它们。