depth-first search

loc. inglese (propr. prima ricerca in profondità) usata in italiano come sf. In informatica, tecnica di risoluzione di problemi consistente nel valutare, tra varie alternative, quella che può condurre alla soluzione. Se la scelta di questa alternativa comporta, a un livello di dettaglio maggiore, la scelta fra diverse alternative, si procede a compiere una scelta fra queste. In tale modo lo spazio delle soluzioni si presenta come un albero in cui a ogni nodo si procede a scegliere uno fra i rami possibili. Se alla fine di questo percorso non si perviene a una soluzione, si può ripartire mediante un'azione di backtracking ripristinando lo stato della computazione al momento dell'ultima scelta effettuata e scegliendo una diversa alternativa. Se tutte le alternative presenti a un nodo sono state esplorate senza avere raggiunto la soluzione, si può fare backtracking al nodo precedente e ripetere il procedimento. Il procedimento di depth-first search si arresta quando viene trovata una soluzione. Non garantisce quindi di trovare la soluzione migliore né che il procedimento abbia termine.