我想使用迭代深度优先搜索,使用图中表示的迷宫,从开始节点找到一条通往目标的路径。它是一个只包含一对数字的文本文件,如成对连接,也称为边/弧。像这样:
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一样。我想让它尽可能简单,让每个人都能理解。有什么建议吗?
如果不更改算法(这不会使其成为dfs)或(如果您试图为除此特定数据集之外的任何内容创建映射,则会浪费时间),您将无法从搜索中获得不同的答案。您可以在代码找到减少遍历节点数量的路径后尝试实现某种回溯,但这不是您想要的简单答案。
简短的回答是:不,DFS并不是这样工作的。
编辑:错过了你的一点问题,你的代码中没有任何东西可以让它变得随机。如果,而不是
for (int arc : G.getAdjacencyList(newNode)) {
if (!visited[arc]) {
visited[arc] = true;
arrayStack.push(arc);
}
如果您对G进行随机采样,那么您将有机会获得不同的结果,但实际上并没有随机元素。