Approfondimento iterativo vs ricerca profondità

Question

Continuo a leggere approfondimento iterativo, ma non capisco come differisca da Ricerca profondità.

Ho capito che la prima ricerca di profondità continua ad andare sempre più in profondità.

Nell'approfondimento iterativo stabilisci un valore di un livello, se non c'è soluzione a quel livello, si aumenta quel valore e ricomincia da zero (la radice).

Non sarebbe la stessa cosa della prima ricerca?

Voglio dire, continueresti ad incrementare e incrementare, andando più in profondità fino a trovare una soluzione. Lo vedo come la stessa cosa! Sarei giù per lo stesso ramo, perché se ricominciassi da zero scenderei lo stesso ramo di prima.

Answer 1

In una prima ricerca, inizi in qualche nodo nel grafico ed esplora continuamente sempre più in profondità nel grafico mentre puoi trovare nuovi nodi che non hai ancora raggiunto (o fino a quando non trovi la soluzione). Ogni volta che il DFS si esaurisce dalle mosse, si ritrova all'ultimo punto in cui potrebbe fare una scelta diversa, quindi esplora da lì. Questo può essere un problema serio se il tuo grafico è estremamente grande e c'è solo una soluzione, poiché potresti finire per esplorare l'intero grafico lungo un percorso DFS solo per trovare la soluzione dopo aver guardato ogni nodo. Peggio ancora, se il grafico è infinito (forse il tuo grafico è costituito da tutti i numeri, per esempio), la ricerca potrebbe non terminare. Inoltre, una volta trovato il nodo che stai cercando, potresti non avere il percorso ottimale per esso (avresti potuto loop su tutto il grafico alla ricerca della soluzione anche se era proprio accanto al nodo iniziale!)

Una potenziale soluzione a questo problema sarebbe quella di limitare la profondità di qualsiasi percorso intrapreso dal DFS. Ad esempio, potremmo fare una ricerca DFS, ma fermare la ricerca se mai prendiamo un percorso di lunghezza maggiore di 5. Ciò assicura che non esploriamo mai nessun nodo che sia a distanza maggiore di cinque dal nodo iniziale, il che significa che non esploriamo mai fuori infinitamente o (a meno che il grafico non sia estremamente denso) non cerchiamo l'intero grafico. Tuttavia, ciò significa che potremmo non trovare il nodo che stiamo cercando, dal momento che non esploriamo necessariamente l'intero grafico.

L'idea alla base dell'approfondimento iterativo è quella di utilizzare questo secondo approccio ma di continuare ad aumentare la profondità ad ogni livello. In altre parole, potremmo provare a esplorare usando tutti i percorsi di lunghezza uno, quindi tutti i percorsi di lunghezza due, quindi la lunghezza tre, ecc. Fino a quando non finiamo per trovare il nodo in questione. Ciò significa che non finiamo mai per esplorare lungo i percorsi infiniti, poiché la lunghezza di ciascun percorso è limitata da una certa lunghezza ad ogni passaggio. Significa anche che troviamo il percorso più breve possibile verso il nodo di destinazione, poiché se non abbiamo trovato il nodo a profondità D ma lo abbiamo trovato in profondità D + 1, non ci può essere un percorso di lunghezza D (o noi lo avrebbe preso), quindi il percorso di lunghezza d + 1 è davvero ottimale.

Il motivo per cui questo è diverso da un DFS è che non si imbatte mai nel caso in cui impiega un percorso estremamente lungo e tortuoso attorno al grafico senza mai terminare. Le lunghezze dei percorsi sono sempre limitate, quindi non finiamo mai per esplorare rami inutili.

Il motivo per cui questo è diverso da BFS è quello in un BFS, devi tenere tutti i nodi marginali in memoria contemporaneamente. Questo richiede memoria o (b^d), dove B è il fattore di ramificazione. Confronta questo con l'utilizzo della memoria O (d) dall'approfondimento iterativo (per trattenere lo stato per ciascuno dei nodi D nel percorso corrente). Naturalmente, BFS non esplora mai lo stesso percorso più volte, mentre l'approfondimento iterativo può esplorare qualsiasi percorso più volte in quanto aumenta il limite di profondità. Tuttavia, asintoticamente i due hanno lo stesso tempo di esecuzione. BFS termina in O (B^d) passaggi dopo aver considerato tutto O (B^d) nodi a distanza d. Usi di approfondimento iterativo O (B^d) tempo per livello, che riassume fino a O (B^d) nel complesso, ma con un fattore costante più elevato.

In breve:

• DFS non è garantito per trovare un percorso ottimale; L'approfondimento iterativo è.
• DFS può esplorare l'intero grafico prima di trovare il nodo target; L'approfondimento iterativo lo fa solo se la distanza tra il nodo iniziale e finale è il massimo nel grafico.
• BFS e approfondimento iterativo corrono entrambi in O (B^d), ma l'approfondimento iterativo ha un fattore costante più elevato.
• BFS usa O (B^d) Memoria, mentre l'approfondimento iterativo usa solo O (d).

Spero che sia di aiuto!

Answer 2

C'è una pagina decente su Wikipedia a questo proposito.

L'idea di base che penso che ti sia mancato che l'approfondimento iterativo è principalmente un euristico. Quando è probabile che una soluzione sia trovata vicino all'approfondimento iterativo della radice, lo troverà relativamente veloce mentre la profondità di profondità dritta-prima potrebbe prendere una decisione "sbagliata" e passare molto tempo a un ramo profondo infruttuoso.

(Ciò è particolarmente importante quando l'albero di ricerca può essere infinito. In questo caso sono ancora meno equivalenti Poiché DFS può rimanere bloccato per sempre mentre BFS o approfondimento iterativo troveranno sicuramente la risposta un giorno se esiste)

Answer 3

Basta aggiungere a ciò che è già qui, ma ecco alcuni video del Moving AI Lab dell'Università di Denver che mostrano le differenze.

http://movingai.com/dfid.html

Puoi vedere nei loro esempi che approfondisce le vittorie iterative quando l'obiettivo è superficiale (profondità della soluzione 3, profondità dell'albero) e la soluzione è sulla destra, ma DFS vince, qualunque cosa se la soluzione sia nell'ultima riga.

Sono entrato in questa lettura sulla programmazione degli scacchi, il prossimo per me stava pensando Ricerca di quiescenza Dai un'occhiata se vuoi saperne di più sulle strategie di ricerca per la programmazione dell'IA.