ampiezza primo o ricerca in profondità

Question

So come funziona l'algoritmo, ma posso decidere quando usare quale algoritmo?

Ci sono alcune linee guida, in cui uno migliore eseguire rispetto all'altro o ogni considerazione?

Grazie mille.

Answer 1

Se si vuole trovare una soluzione con il minor numero di passaggi o se il vostro albero ha infinita altezza (o molto grandi) si dovrebbe usare ampiezza prima.

Se si dispone di un albero finito e vuole percorrere tutte le possibili soluzioni utilizzando la più piccola quantità di memoria, allora si dovrebbe usare la profondità prima.

Se stai cercando il miglior mossa di scacchi per giocare si potrebbe usare iterativo approfondimento che è una combinazione di entrambi.

  

IDDFS combina in profondità di ricerca spazio-efficienza e ampiezza completezza di ricerca (quando il fattore di ramificazione è finito).

Answer 2

BFS è generalmente utile nei casi in cui il grafico ha qualche significativo "stratificazione naturale" (ad esempio, i nodi più stretti rappresentano più "vicino" risultati) e il risultato obiettivo rischia di essere situato più vicino al punto di partenza o nei punti di partenza sono " più conveniente per la ricerca".

Quando si desidera trovare il percorso più breve, BFS è una scelta naturale.

Se il grafo è infinito o pro grammaticalmente generato, si sarebbe probabilmente vuole cercare strati più stretti prima di avventurarsi lontano, in quanto il costo di esplorare nodi remoti prima di arrivare ai nodi più stretti è proibitivo.

Se l'accesso ai nodi più remote sarebbe più costoso a causa di / disco / problemi di località di memoria, BFS può ancora una volta essere migliore.

Answer 3

il metodo da utilizzare dipende solitamente applicazione (vale a dire il motivo per cui si deve cercare un grafico.) - ad esempio ordinamento topologico richiede ricerca in profondità, mentre algoritmo di Ford-Fulkerson per la ricerca di massima portata richiede ampiezza di ricerca <. / p>

Answer 4

Se si sta attraversare un albero, profondità primo ricordo uso volontà proporzionale alla sua profondità. Se l'albero è ragionevolmente equilibrato (o ha qualche altro limite sua profondità), può essere conveniente utilizzare ricorsiva attraversamento in profondità.

Tuttavia, non fare questo per attraversare un grafico generale; è probabile che causare un overflow dello stack. Per gli alberi illimitati o grafici generali, sarà necessario un qualche tipo di memoria ausiliaria che può espandersi ad una dimensione proporzionale al numero di nodi di ingresso. In questo caso, attraversamento in ampiezza è semplice e conveniente.

Se il problema fornisce un motivo per scegliere un nodo rispetto ad un altro, si potrebbe considerare l'utilizzo di una coda di priorità, invece di una pila (per la profondità-prima) o un FIFO (per ampiezza). Una coda di priorità sarà prendere O (log K) Tempo (dove K è l'attuale numero di differenti priorità) per trovare il miglior nodo ad ogni passo, ma l'ottimizzazione può essere valsa la pena.