0

我正在尝试计算 5x5 场地上所有可能的骑士移动：

为此，我尝试使用 DFS（深度优先搜索）类和 Graph 类。

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

图.java

深度优先搜索.java

Graph.java 使用 Bag.java：

包.java

该字段看起来像这样（为每个字段使用一个 id）：

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

CalculatePath 方法中使用了以下属性，该方法应计算骑士可以从特定方格到每个方格恰好访问一次（应该需要一两分钟才能解决）的可能旅行量。

可能的 Knight 步骤（在主类中）定义如下（使用 Graph 的边，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)返回所有可能的游览（ ）。tours

未标记的广场是已经到达的广场，在同一次游览中不应再访问。

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

此外，该方法还没有计算多个旅行。我想首先正确计算一条路径并最终计算所有可能的行程。

我使用的所有代码都包含在这篇文章中 - 包括上面链接中的类。

4

1 回答 1

1

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

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

您的DepthFirstSearch构造函数似乎正在尝试标记所有相邻点（及其所有相邻点）。这看起来很奇怪——你希望它如何工作？避免循环的正常 DFS 机制是在递归时在您触及的每个位置留下一个标记，并在递归完成时删除该标记。在这里，您似乎在开始时标记所有方格，然后在完成一轮所有相邻方格但未找到已标记方格时取消标记。

于 2016-01-13T13:51:12.027 回答