Formulazione corretta dell'algoritmo A *

Question

Sto esaminando le definizioni dell'algoritmo di ricerca del percorso A * e sembra che sia definito in modo leggermente diverso in luoghi diversi.

La differenza sta nell'azione eseguita quando si passa attraverso i successori di un nodo e si scopre che un successore è nell'elenco chiuso.

• Un approccio (suggerito da Wikipedia e questo articolo ) dice: se il successore è nella lista chiusa, ignoralo
• Un altro approccio (suggerito qui e qui , ad esempio) dice: se il successore è nella lista chiusa, esaminane il costo. Se è superiore al punteggio attualmente calcolato, rimuovere l'elemento dall'elenco chiuso per un esame futuro.

Sono confuso: quale metodo è corretto? Intuitivamente, il primo ha più senso per me, ma mi chiedo la differenza di definizione. Una delle definizioni è sbagliata o sono in qualche modo isomorfi?

Answer 1

Il primo approccio è ottimale solo se il percorso ottimale verso uno stato ripetuto è sempre il primo da seguire. Questa proprietà è valida se la funzione euristica ha la proprietà di coerenza (chiamata anche monotonia ). Una funzione euristica è coerente se, per ogni nodo n e ogni successore n ' di n , il costo stimato per raggiungere l'obiettivo da n non è maggiore del costo del passaggio per arrivare a n ' da n più il costo stimato per raggiungere l'obiettivo da n .

Il secondo approccio è ottimale se la funzione euristica è semplicemente ammissibile, cioè non sopravvaluta mai il costo per raggiungere l'obiettivo.

È ammessa anche ogni funzione euristica coerente. Sebbene la coerenza sia un requisito più rigoroso della ricevibilità, è necessario impegnarsi a fondo per creare funzioni euristiche ammissibili ma non coerenti.

Pertanto, anche se il secondo approccio è più generale in quanto funziona con un sottogruppo strettamente più ampio di funzioni euristiche, il primo approccio è generalmente sufficiente nella pratica.

Riferimento: sottosezione A * ricerca: Riduzione al minimo del costo totale stimato della soluzione nella sezione 4.1 Strategie di ricerca (euristiche) informate del libro Intelligenza artificiale: A Approccio moderno .