Tip:
Highlight text to annotate it
X
Här ger vi dig en intuition om varför
en optimistisk heuristisk funktion, h, finner den billigaste vägen.
När A-stjärna slutar, returneras en stig, p, med uppskattad kostnad, c.
Det visar sig att C är också den faktiska kostnaden,
eftersom vid målet är H-komponenten 0,
och så är stigkostnaden den totala kostnaden som uppskattats av funktionen.
Nu, alla stigar vid frontlinjen
har en beräknad kostnad som är högre än C,
och vi vet det eftersom frontlinjen är utforskad i billigast-först-ordning.
Om h är optimistisk, då är den uppskattade kostnaden
lägre än den verkliga kostnaden,
så stigen p måste ha en kostnad som är lägre än den verkliga kostnaden
av någon av stigarna på frontlinjen.
Alla vägar som går bortom frontlinjen
måste ha en kostnad som är större än det
eftersom vi är överens om att stegkostnaden alltid är 0 eller mer.
Så det innebär att denna stig, p, måste vara den billigaste stigen.
Detta argument, som det är givet här,
är bara giltigt för trädsökning.
För grafsökning är argumentet något mer komplicerat,
men slutsatserna vi kan dra är desamma.