Tip:
Highlight text to annotate it
X
Qui vi diamo una intuizione del perché
una funzione di euristica ottimista, h, trova il percorso con minor costo.
Quando A star termina, restituisce un percorso, p, con costo stimato, c.
Risulta che c è anche il costo effettivo,
perché al goal la componente h è pari a 0,
e così il costo del percorso è il costo totale stimato dalla funzione.
Ora, tutti i percorsi sulla frontiera
hanno un costo stimato che è maggiore di C,
e lo sappiamo perché la frontiera è espansa nell'ordine minor costo prima.
Se h è ottimista, il costo stimato
è meno del costo reale,
quindi il percorso p deve avere un costo inferiore al costo reale
di ogni altro percorso nella frontiera.
Ogni percorso che va oltre la frontiera
deve avere un costo più grande
perché sappiamo che il costo di ogni passo è sempre zero o positivo.
Tutto ciò significa che questo percorso p deve avere il costo minore.
Ora devo dire che questo ragionamento funziona solo
nella ricerca ad albero.
Per la ricerca a grafo il ragionamento è leggermente più complicato.
ma l'intuizione generale resta la stessa.