0
我可能會丟失一些關於DFS/DLS時，維基百科不說訪問節點應該與當前深度連接起來......算法 - DFS極其緩慢保持visisted節點
問題：你有這樣的2x4地圖S =啓動E =出口
____
E |
|
|
S |
如果您正在使用DFS MAXDEPTH = 3，您的移動發電機是：
dir = {right, left, up, down}
DFS不會在深度爲3（這意味着IDDFS將解決這一失敗太...）
DFS會嘗試這條道路首先：如果你是標誌着拜訪位置現在E爲僅在深度可達5 DFS以來將回溯到深度0找到
____
E |
|
3 2 |
0 1 |
的第一次移動'up'已經不再有效，因爲它已經在第3深度了！
我看到的唯一解決方案是標記與當前的深度被訪問的位置（因此可以忽略一個「訪問」的位置，如果visited.depth> currentDepth），這意味着每個位置將在每個DFS搜索被訪問很多很多次當深度= X時，不可能在大問題中使用！
在我的測試中，如果你有足夠的內存在一個大問題中運行廣度優先搜索，它將比深度= X處的DFS運行更快，即使X是最短深度來解決..它聽起來是我'錯了，但我只是沒有看到它爲什麼或什麼我doig錯了..有人請賜教！ （是的，這是問題...我不知道發生了什麼事）
這是我的搜索功能，以解決難題：
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);
}