Differenza tra ricerca in ampiezza e approfondimento iterativo

Question

capisco BFS, e DFS, ma per la vita di me non riesco a capire la differenza tra iterativo approfondimento e BFS. A quanto pare approfondimento iterativo ha lo stesso utilizzo della memoria da DFS, ma non riesco a vedere come questo sia possibile, in quanto continua ad espandersi come BFS. Se qualcuno può chiarire che sarebbe fantastico.

albero di lavorare su se necessario:

    A
   / \
  B   C
 /   / \
D   E   F

Answer 1

Da quanto ho capito iterativo approfondire fa DFS fino alla profondità di 1 poi fa DFS fino alla profondità di 2 ... fino alla profondità di n, e così via fino a che non trova più livelli

per esempio penso che l'albero sarebbe stato letto

read                   visited               depth

A                      A                     1

ABC                    ABAC                  2

ABDCEF                 ABDBACECF             3

Credo che la sua praticamente facendo un DFS separate con limite di profondità per ogni livello e buttare via la memoria.

Answer 2

Dalla mia comprensione dell'algoritmo, IDDFS (iterativo-approfondimento ricerca in profondità) è semplicemente una ricerca in profondità eseguita più volte, approfondendo il livello dei nodi cercato ad ogni iterazione. Pertanto, i requisiti di memoria sono le stesse di ricerca in profondità perché l'iterazione profondità massima è solo la ricerca completa profondità.

Quindi, per l'esempio dell'albero hai dato, la prima iterazione avrebbe visitato il nodo A, la seconda iterazione avrebbe visitato nodi A, B, e C, e la terza iterazione sarebbe visitare tutti i nodi dell'albero.

Il motivo per cui è implementato come questo è in modo tale che, se la ricerca ha un vincolo di tempo, allora l'algoritmo almeno avere un'idea di ciò che un nodo "buon punteggio" è se raggiunge il termine prima di fare un pieno attraversamento della struttura.

Questo è diverso da una ricerca in ampiezza, perché ad ogni iterazione, i nodi vengono visitati proprio come lo sarebbero in una ricerca in profondità, non è come in una ricerca in ampiezza. In genere, IDDFS algoritmi probabilmente conservare la "miglior punteggio" nodo situato: ogni iterazione.

Answer 3

l'utilizzo della memoria è il numero massimo di nodi consente di risparmiare in qualsiasi punto. non il numero di nodi visitati.

in qualsiasi momento IDF ha bisogno di memorizzare solo i nodi nel ramo è expanding.only A e C, se stiamo espandendo C (in es). BFS deve salvare tutti i nodi della profondità si sta cercando. per vedere l'effetto prendere un albero con ramificazioni fattore 8 piuttosto che 2. per la ricerca ad una profondità di 3, BFS ha bisogno di memorizzare un massiccio 64 nodi. IDF ha bisogno solo 3.

Answer 4

In ogni iterazione iterativo-approfondimento ricerca, abbiamo un limite e attraversiamo il grafico utilizzando l'approccio DFS, tuttavia, per ogni passo di ogni iterazione, dobbiamo solo tenere traccia dei soli nodi all'interno del percorso dalla radice alla profondità d. Questo è il risparmio di memoria.

Per esempio, guardate l'ultima fila di foto qui sotto. Se abbiamo utilizzato BFS, abbiamo dovuto tenere traccia di tutti i nodi fino a profondità di 2. Ma poiché stiamo usando DFS, non abbiamo bisogno di tenere tutti in memoria dal momento che sia alcuni nodi sono già visitati in modo da non lo facciamo bisogno di loro, o non ancora visitati quindi dovremo aggiungere in un secondo momento. Dobbiamo solo continuare il nostro percorso alla radice (il percorso grigio).

L'immagine è da Artificial Intelligence libro di Peter Norvig e Stuart Russel