Busca en profunditat llimitada

En ciències de la computació, la busca en profunditat llimitada és un algoritme per a explorar els vèrtiços d'un grafo. És una modificació de la busca en profunditat i s'usa, per eixemple, en l'algoritme de busca en profunditat iterativa.

General

Com la busca en profunditat normal, la busca en profunditat llimitada és una busca sense informació. Funciona igual que la busca en profunditat simple, pero evita els inconvenients respecte a la completitud, imponent un llímit màxim de profunditat de busca. Inclús encara que la busca poguera expandir un vèrtiç més allà d'eixa profunditat, no ho farà, per lo que no continuarà per camins de profunditat infinita ni s'atollarà en cicles. Per lo tant, la busca en profunditat llimitada trobarà una solució si esta es troba dins del llímit de profunditat, lo que garantisa completitud en tots els grafos.

Algoritme (informal)

1. Determinar el vèrtiç a on la busca deu escomençar i assignar la màxima profunditat
2. Comprovar si el vèrtiç actual és l'estat objectiu
   • Si no: No fer res
   • Si sí: tornar
3. Comprova si el vèrtiç actual està dins de la profunditat màxima
   • Si no: No fer res
   • Si sí:
     1. Expandir el vèrtiç i guardar tots els seus successors en una pila
     2. Cridar a BPL recursivamente per a tots els vèrtiços de la pila i tornar al pas 2