Verifica dell'ottimizzazione dell'algoritmo A * quando l'euristica sottovaluta sempre

Question

Capisco perché l'algoritmo A * fornisce sempre il percorso più ottimale per uno stato obiettivo quando l'euristica sottovaluta sempre, ma non posso creare una dimostrazione formale per esso.

Per quanto ho capito, per ogni percorso considerato man mano che si va sempre più in profondità, la precisione di f(n) aumenta fino allo stato dell'obiettivo, dove è preciso al 100%. Inoltre, nessun percorso errato viene ignorato, poiché la stima è inferiore al costo effettivo; portando così al percorso ottimale. Ma come dovrei creare una prova per questo?

Answer 1

L'idea principale della dimostrazione è che quando A * trova un percorso, ha trovato un percorso che ha una stima inferiore alla stima di qualsiasi altro percorso possibile. Poiché le stime sono ottimistiche, gli altri percorsi possono essere tranquillamente ignorati.

Inoltre, A * è ottimale soltanto se sono soddisfatte due condizioni:

1. L'euristica è ricevibile , come sarà mai sovrastimare il costo.

2. L'euristica è monotona, cioè, se h (n _i) < h (n _{i + 1}), allora reale costo (n _i) < reale costo (n _{i + 1}).

---

È possibile dimostrare l'ottimalità essere corretti assumendo l'opposto, ed espandendo le implicazioni.

Si supponga che il percorso da dare A * è non ottimale con un'euristica ammissibile e monotona, e pensare a ciò che significa in termini di implicazioni (presto vi ritroverete raggiungendo una contraddizione), e, quindi, la vostra l'ipotesi originale è ridotta ad assurdo.

Da ciò si può concludere che l'ipotesi originaria era falsa, cioè A * è ottimale con le condizioni di cui sopra. Come volevasi dimostrare

Answer 2

Considerare l'ultimo passaggio, quello che completa il percorso ottimale.

Perché A * deve scegliere quel percorso? O, in altre parole, perché A * evita di scegliere un percorso non ottimale che raggiunge l'obiettivo?

Suggerimento: questo è il motivo per l'euristica deve essere ricevibili. Si noti che è giusto scegliere un percorso sub-ottimale, a condizione che non completi il ​​percorso (perché?).

Questo dovrebbe darvi un'idea di come modellare una prova.