Iteracyjne wyszukiwanie pogłębione (IDS), które składa się z wielu rund wyszukiwania ograniczonego do głębi (w zasadzie DFS, ale przestaje wyszukiwać, jeśli osiągnięto ograniczenie głębokości d), które stopniowo zwiększa głębokość od 1, znajdzie najkrótszą ścieżkę na nieważonym wykresie.
// Iterative deepening search
// isGoal is a function that checks whether the current node is the goal
function ids(graph, start, isGoal) {
maxDepth = 1
do {
found = dls(graph, start, isGoal, maxDepth, 0)
// Clear the status whether a node has been visited
graph.clearVisitedMarker();
// Increase maximum depth
depth = depth + 1
// You can slightly modify the dls() function to return whether there is a
// node beyond max depth, in case the graph doesn't have goal node.
} while (found == null)
return found
}
// Depth-limited search
// isGoal is a function that checks whether the current node is the goal
function dls(graph, currentNode, isGoal, maxDepth, currentDepth) {
if (graph.visited(currentNode)) {
return null
}
graph.setVisited(currentNode)
if (isGoal(currentNode)) {
return currentNode
}
// Stop searching when exceed max depth
// This is the only difference from DFS
if (currentDepth >= maxDepth) {
return null
}
for (adjNode in graph.getAdjacent(currentNode)) {
found = dls(graph, adjNode, goal, maxDepth, currentDepth + 1)
if (found != null) {
return found
}
}
return null
}
To działa, ponieważ stopniowo zwiększać dystans dozwolony od węzła start: węzeł, który ma zdystansować a + 1 nie zostanie zbadana przed węzeł, który ma odległość A, z powodu limitu głębokości.
Powszechną obawą jest to, że węzły z odległością a zostaną ponownie odwiedzone (d - a + 1) razy, gdzie d jest głębokością najkrótszej ścieżki do celu. Zależy od wykresu lub drzewa wyszukiwania, jeśli chcemy mówić o wydajności. W drzewie wyszukiwania o dużym współczynniku rozgałęzienia, węzły generowane na głębokości d stają się dominującym terminem, więc nie ma większego problemu z ponownym przeglądaniem. BFS nie nadaje się do użytku w takim przypadku ze względu na zapotrzebowanie na wykładniczą powierzchnię, ale IDS użyje tylko przestrzeni wielomianowej.
To nie jest tutaj, także, jest duplikatem wpisu na stronie, który należy do http://cs.stackexchange.com/questions/4914/why-cant-dfs-be-used- to-find-shortest-paths-in-unweighted-graphs –