Busca en profunditat iterativa

Plantilla:Revisar traducció Una busca en Profunditat Iterativa (BPI) és un algoritme de busca no informada utilisat per a una estratègia de busca en l'espai d'estats en la que es realisen successives busques en profunditat llimitada incrementant el llímit de profunditat en cada iteración fins a alcançar $d$, la profunditat de l'estat objectiu de menor profunditat. BPI és equivalent a la busca en esgambi, pero usa molta menys memòria; en cada iteración, visita els nodos de l'arbre de busca en el mateix orde que una busca en profunditat, pero l'orde en el que els nodos són visitats finalment es correspon en la busca en esgambi.

Propietats

BPI combina l'eficiència de l'espai d'estats de la busca en profunditat i la completitud de la busca en esgambi (quan el factor de ramificació és finito). És òptima quan el cost del camí és una funció no decreixent de la profunditat del nodo.

La complexitat en espai de la BPI és $O(bd)$, a on $b$ és el factor de ramificació i $d$ és la profunditat de la solució més superficial. Ya que BPI visita els estats múltiples voltes, pot semblar extremadament costós, pero no ho és, ya que la major part dels nodos es troben en el nivell més profunt de l'arbre, per lo tant no té molta importància que es visiten els nivells superiors vàries voltes.

La principal ventaja de BPI en busques en arbres de jocs és que les busques anteriors tenen a millorar la heurística usada, com a heurística assessina o la poda alfa-beta, de manera que es pot obtindre una estimació més precisa de la puntuació de varis nodos en l'última busca i la busca es completa més ràpidament ya que es fa en un orde millor. Per eixemple, la poda alfa-beta és més eficient si es busca el primer moviment millor.

Una segona ventaja és la complexitat en temps de l'algoritme. Perque les primeres iteraciones usa valors menuts per a $d$, és dir, s'eixecuten extremadament ràpit. Açò permet a l'algoritme proporcionar indicacions sobre el resultat casi immediatament, refinant-les segons $d$ aumenta. Quan s'utilisa en un entorn interactiu, com en un programa per a jugar al escacs, esta facilitat permet al programa jugar en qualsevol moment en la millor solució trobada fins al moment en la busca realisada.

La complexitat en temps en un arbre equilibrat és la mateixa en en busca en profunditat: $O(b^d)$.

En una busca en profunditat iterativa, els nodos en el nivell més inferior s'expandixen una sola volta, els de el nivell anterior dos voltes i aixina fins a la raïl de l'arbre, que s'expandix $d+1$ voltes. Per lo tant, el número total d'expansions és

$(d+1)1+(d)b+(d-1)b^2+\cdots +3b^{d-2}+2b^{d-1}+b^d$

$\sum _{i=0}^d(d+1-i)b^i$

Per a $b=10$ i $d=5$ el número d'expansions és

6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456

En resum, una BPI de profunditat 1 a profunditat $d$ expandix, aproximadament, un 11% més de nodos que una busca en esgambi simple o una busca en profunditat llimitada de profunditat $d$, quan $b=10$. Quant major és el factor de ramificació, menor és la sobrecàrrega d'estats expandits múltiples voltes, pero inclús per a un factor de ramificació 2, la BPI solament necessita el doble que una busca en esgambi. Açò significa que la complexitat de la BPI és encara $O(b^d)$, i la complexitat en espai és $O(d)$ com una busca en profunditat simple. En general, BPI és el método de busca principal quan hi ha un espai d'estats gran i la profunditat de la solució és desconeguda.

Eixemple

Archiu:Graph.traversal.example.svg

Una busca en profunditat escomençant en A, assumint que els costats esquerres del gràfic es prenen abans que els drets i assumint que la busca recorda els nodos visitats prèviament i no els repetix (ya que açò és un chicotet grafo), visitarà els nodos en el següent orde: A, B, D, F, I, C, G.

Realisant la mateixa busca sense recordar els nodos prèviament visitats, el resultat no tindrà fi: A, B, D, F, I, A, B, D, F, I, etc., açò ocorre pel cicle entre A, B, D, F i I, lo que no permet alcançar C o G.

La busca en profunditat iterativa nos soluciona estos bucles i alcançarà els nodos dels següents nivells. Assumint que procedix d'esquerra a dreta com abans:

• 0: A
• 1: A (repetit), B, C, I

(Note's que BPI ha visitat C, lo que no ocorre en la busca en profunditat.)

• 2: A, B, D, F, C, G, I, F

(Note's que encara visita C, pero apareix més vesprada. També visita I per un camí distint, pero torna a F dos voltes.)

• 3: A, B, D, F, I, C, G, I, F, B

Per a este grafo, quanta més profunditat s'afig, els cicles "ABFE" i "AEFB" simplement s'allarguen ans que l'algoritme abandone i intente una atra branca. Pot recórrer vàries voltes al mateix nodo sempre i quan no siga la solució