Tip:
Highlight text to annotate it
X
Her ser vi på en intuitiv måte for hvorfor
en optimistisk heuristisk funksjon, h, finner den laveste kostnadsruten.
Når A-stjerne avsluttes, returnerer den en rute p med en estimert kostnad c.
Det viser seg at c også er den faktiske kostnaden,
fordi h-komponenten er 0 ved målet.
Så rutekostnad er totalkostnad, som estimert av funksjonen.
Alle rutene på frontlaget
har en estimert kostnad som er større enn c,
og vi vet det fordi frontlaget er utforsked i billigste-først rekkefølge.
Hvis h er optimistisk, da er estimert kostnad
mindre enn virkelig kostnad,
slik at ruten p på ha en kostnad som er mindre enn virkelig kostnad
på enhver rute på frontlaget.
Ruter som går bortenfor frontlaget
må ha en kostnad som er større enn det
fordi vi er enige om at stegkostnaden alltid er 0 eller høyere.
Så det betyr at denne ruten p må være den minste kostnadsruten.
Denne argumentasjonen, må jeg si, går bare gjennom
slik for søketre.
For grafiske søk blir argumentasjonen litt mer komplisert,
men den samme intuisjonen holder generelt.