Quali sono le differenze tra A * e greedy best-first search?

Entrambi gli algoritmi rientrano nella categoria della “ricerca migliore” algoritmi, che sono algoritmi che possono utilizzare sia le conoscenze acquisite fino ad ora durante lesplorazione dello spazio di ricerca, indicate con $ g (n) $ e una funzione euristica, indicata con $ h (n) $ , che stima la distanza dal nodo obiettivo, per ciascun nodo $ n $ nello spazio di ricerca (spesso rappresentato come un grafico).

Ciascuno di questi algoritmi di ricerca definisce una “funzione di valutazione”, per ogni nodo $ n $ nel grafico (o spazio di ricerca), indicato da $ f (n) $ . Questa funzione di valutazione viene utilizzata per determinare quale nodo, durante la ricerca, viene “espanso” per primo, ovvero quale nodo viene rimosso per primo dalla “frangia” (o “frontiera”, o “confine”) , in modo da “visitare” i suoi figli. In generale, la differenza tra gli algoritmi nella categoria “best-first” sta nella definizione della funzione di valutazione $ f (n) $ .

Nel caso di lalgoritmo BFS avido , la funzione di valutazione è $ f (n) = h (n) $ , ovvero lalgoritmo greedy BFS espande prima il nodo la cui distanza stimata dallobiettivo è la più piccola. Quindi, greedy BFS non usa la “conoscenza passata”, ad esempio $ g (n) $ . Da qui la sua connotazione “golosa”. In generale, lalgoritmo BST avido è non completo , cioè cè sempre il rischio di prendere un percorso che non lo fa portare alla meta. Nellalgoritmo BFS avido, tutti i nodi sul confine (o margine o frontiera) sono tenuti in memoria, ei nodi che sono già stati espansi non hanno bisogno di essere immagazzinati in memoria e possono quindi essere scartati. In generale, il BFS avido è anche non ottimale , ovvero il percorso trovato potrebbe non essere quello ottimale. In generale, la complessità temporale è $ \ mathcal {O} (b ^ m) $ , dove $ b $ è il fattore di ramificazione (massimo) e $ m $ è la profondità massima dellalbero di ricerca. La complessità dello spazio è proporzionale al numero di nodi ai margini e alla lunghezza del percorso trovato.

Nel caso di la A * algoritmo , la funzione di valutazione è $ f (n) = g (n) + h (n) $ , dove $ h $ è una funzione euristica ammissibile . La “stella”, spesso indicata da un asterisco, *, si riferisce al fatto che A * utilizza una funzione euristica ammissibile, il che significa essenzialmente che A * è ottimale , ovvero trova sempre il percorso ottimale tra il nodo iniziale e il nodo obiettivo. Un * è anche completo (a meno che non ci siano infiniti nodi da esplorare nello spazio di ricerca). La complessità temporale è $ \ mathcal {O} (b ^ m) $ . Tuttavia, A * deve tenere in memoria tutti i nodi durante la ricerca, non solo quelli marginali, perché A *, essenzialmente, esegue una “ricerca esaustiva” (che è “informata”, nel senso che utilizza una funzione euristica ).

In sintesi, greedy BFS non è completo, non ottimale, ha una complessità temporale di $ \ mathcal {O} (b ^ m) $ e una complessità spaziale che può essere polinomiale. A * è completo, ottimale e ha una complessità temporale e spaziale di $ \ mathcal {O} (b ^ m) $ . Quindi, in generale, A * utilizza più memoria di greedy BFS. Un * diventa poco pratico quando lo spazio di ricerca è enorme. Tuttavia, A * garantisce anche che il percorso trovato tra il nodo iniziale e il nodo obiettivo è quello ottimale e che lalgoritmo alla fine termina. Greedy BFS, daltra parte, utilizza meno memoria, ma non fornisce le garanzie di ottimalità e completezza di A *. Quindi, quale algoritmo è il “migliore” dipende dal contesto, ma entrambi sono i “migliori” per le prime ricerche.

Nota: in pratica, non puoi utilizzare nessuno di questi algoritmi: potresti ad es. utilizza, invece, IDA * .

Commenti

• I commenti non sono per discussione estesa; questa conversazione è stata spostata nella chat .

Secondo il libro Intelligenza artificiale: A Modern Approach (3a edizione), di Stuart Russel e Peter Norvig, in particolare, sezione 3.5.1 Greedy best-first search (p. 92)

La ricerca avida al meglio cerca di espandere il nodo più vicino allobiettivo, sulla base del fatto che questo è probabile che porti a una soluzione rapidamente. Pertanto, valuta i nodi utilizzando solo la funzione euristica; ovvero $ f (n) = h (n) $ .

In questo Nella stessa sezione, gli autori forniscono un esempio che mostra che la ricerca avida best-first non è né ottimale né completa.

Nella sezione 3.5.2 Ricerca A *: Riducendo al minimo il costo totale stimato della soluzione dello stesso libro (p. 93), si afferma

A * la ricerca valuta i nodi combinando $ g (n) $ , il costo per raggiungere il nodo e $ h (n) $ , il costo per andare dal nodo allobiettivo $$ f (n) = g (n) + h (n). $$

Poiché $ g (n) $ fornisce il costo del percorso dal nodo iniziale al nodo $ n $ e $ h (n) $ è il costo stimato del percorso più economico da $ n $ allobiettivo, abbiamo $ f (n) $ = costo stimato della soluzione più economica tramite $ n $ .

Quindi, se stiamo cercando di trovare la soluzione più economica, una cosa ragionevole da provare prima è il nodo con il valore più basso di $ g (n) + h (n) $ . Si scopre che questa strategia è più che ragionevole: a condizione che la funzione euristica $ h (n) $ soddisfi determinate condizioni, la ricerca A * è sia completa che ottimale. Lalgoritmo è identico alla ricerca a costo uniforme tranne per il fatto che A * utilizza $ g + h $ invece di $ g $

Quello che hai detto non è “totalmente sbagliato, ma lalgoritmo A * diventa ottimale e completo se la funzione euristica h è ammissibile, il che significa che questa funzione non sovrastima mai il costo per raggiungere lobiettivo. In tal caso, lalgoritmo A * è di gran lunga migliore dellalgoritmo di ricerca greedy.

Commenti

• caro puoi elaborare la tua risposta. scusami ma non ho capito il tuo punto.
• @IramShah – TemmanRafk sta parlando della prova che A * è sia ottimale che completo. Per fare ciò si dimostra a causa della disuguaglianza del triangolo che leuristica che stima la distanza rimanente allobiettivo non è una sovrastima. Per vedere una spiegazione più completa vedi en.wikipedia.org/wiki/Admissible_heuri stic