L' A * Algorithm è ottimale (a condizione che la funzione euristica sia sottostimata), completa e amp; ammissibile (a condizione di alcune condizioni). Conosco le prove di ammissibilità e amp; ottimalità.
Ma come si dimostra che l'algoritmo A * è completo?
Per una dimostrazione di completezza, non è necessario guardare in modo specifico su A *. Qualsiasi algoritmo di ricerca di grafici finiti che utilizza una coda di nodi da cui si prende un elemento, genera tutti i figli di quel nodo grafico e li riporta in coda è completo, "A *" è solo un caso speciale di quel tipo di algoritmi.
Una volta ottenuto questo, è facile trovare una prova di completezza per la ricerca del grafico arbitario da parte di Google, ad esempio, questo:
La dimostrazione in sé non è molto complessa, ma IMHO è ancora troppo lungo per riassumere qui.
Leggi altre domande sui tag algorithms algorithm-analysis a-star