java - 深度优先搜索随机选择节点/顶点

Question

我想使用图中所示的迷宫，使用迭代深度优先搜索找到从起始节点到目标的路径。它是一个仅包含一对数字的文本文件，例如成对连接，又称边/弧。像这样:

11 3
2 3
0 3
1 4
5 4
5 7
6 7
7 8
8 9
9 10
0 5

那么我的代码是这样的:

private void performIterativeDFS(MazeGraph G, int node, int goal) {
        ArrayBasedStack arrayStack = new ArrayBasedStack();
        ArrayBasedStack pathStack = new ArrayBasedStack();
        arrayStack.push(node);
        visited[node] = true;
        while (!arrayStack.isEmpty()) {
            int newNode = arrayStack.pop();
            if (newNode == 0) {
                out.print("Starting at " + newNode + " ");
            }
            pathStack.push(newNode);
            if (newNode == goal) {
                out.println("Path if goal found: " + pathStack.toString());
            }
            for (int arc : G.getAdjacencyList(newNode)) {
                if (!visited[arc]) {
                    visited[arc] = true;
                    arrayStack.push(arc);
                }
            }
        }
    }

我输入0作为起始节点，目标节点为1。那么输出的路径是0,5,7,8,9,10,6,4,1。不幸的是，这并不是一个正确的解决方案，您可以使用 0,5,4,1 来代替。迭代深度优先搜索在达到目标之前是否会随机选择下一步要执行的节点？

我尝试修改我的代码来做到这一点，但我无法像 0,5,4,1 那样打印路径。我想尽可能简单，以便每个人都能理解。有什么建议或建议吗？

Answer 1

如果不更改算法(这不会使其成为 dfs)或(如果您试图为除此特定数据集之外的任何内容创建 map ，这将是浪费时间)，您不会从搜索中得到不同的答案。您可以在代码找到减少遍历节点数量的路径后尝试实现某种回溯，但这不是您正在寻找的简单答案。

简短回答:不，DFS 并不是这样工作的。

编辑:错过了您的一些问题，您的代码中没有任何内容使其成为随机的。如果，而不是

for (int arc : G.getAdjacencyList(newNode)) {
            if (!visited[arc]) {
                visited[arc] = true;
                arrayStack.push(arc);
            }

你随机采样G，那么你将有机会得到不同的结果，但事实上它没有随机元素。