Tip:
Highlight text to annotate it
X
Her giver vi dig en fornemmelse for hvorfor
en optimistisk heuristisk funktion, h, finder stien med den laveste omkostning.
Når A slutter, returnerer den en sti, p, med en estimeret omkostning, c.
Det viser sig at c også er den faktiske omkostning,
fordi komponenten h er 0 ved målet,
og så er stiens omkostning lig med den samlede omkostning estimeret af funktionen.
Nu har alle stierne på grænsen
en estimeret omkostning, der er større end c,
og det ved vi fordi grænselaget udvides med den billigste node først.
Hvis h er optimistisk, så er den estimerede omkostning
mindre end den faktiske omkostning,
så stien p må have en omkostning der er mindre end den faktiske omkostning
ved enhver af stierne på grænsen.
Enhver sti der går videre end grænselaget
må have en omkostning der er større end det,
fordi vi har vedtaget at trin-omkostningen altid er 0 eller større.
Så det betyder at denne sti, p, må være stien med den mindste omkostning.
Men jeg bør sige, at dette argument kun holder
som det står, for træsøgning.
For grafsøgning er argumentet en anelse mere indviklet,
men de overordnede formodninger