Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Iterative deepening depth-first search
Résumé
In computer science, iterative deepening search or more specifically iterative deepening depth-first search (IDS or IDDFS) is a state space/graph search strategy in which a depth-limited version of depth-first search is run repeatedly with increasing depth limits until the goal is found. IDDFS is optimal like breadth-first search, but uses much less memory; at each iteration, it visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited is effectively breadth-first.
The following pseudocode shows IDDFS implemented in terms of a recursive depth-limited DFS (called DLS) for directed graphs. This implementation of IDDFS does not account for already-visited nodes.
function IDDFS(root) is
for depth from 0 to ∞ do
found, remaining ← DLS(root, depth)
if found ≠ null then
return found
else if not remaining then
return null
function DLS(node, depth) is
if depth = 0 then
if node is a goal then
return (node, true)
else
return (null, true) (Not found, but may have children)
else if depth > 0 then
any_remaining ← false
foreach child of node do
found, remaining ← DLS(child, depth−1)
if found ≠ null then
return (found, true)
if remaining then
any_remaining ← true (At least one node found at depth, let IDDFS deepen)
return (null, any_remaining)
If the goal node is found, then DLS unwinds the recursion returning with no further iterations. Otherwise, if at least one node exists at that level of depth, the remaining flag will let IDDFS continue.
2-tuples are useful as return value to signal IDDFS to continue deepening or stop, in case tree depth and goal membership are unknown a priori. Another solution could use sentinel values instead to represent not found or remaining level results.
IDDFS combines depth-first search's space-efficiency and breadth-first search's completeness (when the branching factor is finite). If a solution exists, it will find a solution path with the fewest arcs.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.