我可能遗漏了一些关于 DFS/DLS 的信息，维基百科没有说访问的节点应该与当前深度连接......
问题：你有这个 2x4 地图 S=start E=exit
____
E |
|
|
S |
如果您使用 DFS maxDepth=3 并且您的移动生成器是：
dir = {right, left, up, down}
DFS 不会在深度 3 解决这个问题（这意味着 IDDFS 也会失败......）
DFS 将首先尝试此路径：
____
E |
|
3 2 |
0 1 |
如果您现在标记已访问的位置，E 只能在深度 5 处到达，因为 dfs 将回溯到深度 0 并发现第一次“向上”移动不再有效，因为它已经在深度 3 处进行了！
我看到的唯一解决方案是用当前深度标记访问过的位置（如果visited.depth > currentDepth，你可以忽略“访问过”的位置），这意味着当depth=X时，每个DFS搜索中的每个位置都会被访问很多次使其无法用于大问题！
在我的测试中，如果你有足够的内存在一个大问题中运行广度优先搜索，即使 X 是要解决的最短深度，它也会比深度 = X 的 DFS 运行得快得多。听起来我错了，但是我只是不明白为什么或我做错了什么……有人请赐教！（是的，这就是问题......我不知道发生了什么）
这是我解决谜题的搜索功能：
BFS（效果很好，但不是非常大的问题.. 使用大量 RAM）
注意我没有使用 hasmap 的值（总是 0）
HashMap<State, Integer> table = new HashMap();
State bfs() {
State state = this.initState;
Queue<State> pending = new LinkedList();
table.put(state, 0);
pending.add(state);
while ( !pending.isEmpty() ) {
state = pending.remove();
for ( State child : state.getChildren() ) {
if ( !table.containsKey(child) ) {
table.put(child, 0);
if ( child.isSolved() )
return child;
pending.add(child);
}
}
}
return null;
}
DFS（非常慢，节点太多，无法用于大问题）
注意 hashMap.put 也会更新旧值
State dls(State state, int depth) {
if ( depth == maxDepth )
return state.isSolved() ? state : null;
for ( State child : state.getChildren() ) {
if ( !table.containsKey(child) ||
table.get(child) > depth ) {
table.put(child, depth);
State solution = dls(child, depth + 1);
if (solution != null)
return solution;
}
}
return null;
}
State solution(int depth) {
this.maxDepth = depth;
table.put(this.initState, 0);
return dls(this.initState, 0);
}