Tip:
Highlight text to annotate it
X
Tu predostrieme intuitívne príčiny, prečo
optimistická heuristická funkcia, h, nájde najmenej nákladnou trasu.
Ak je A ukončená, vráti cestu, p, s odhadovanou cenou, c.
Ukáže sa, že c je tiež skutočná cena,
pretože v cieli má komponent h hodnotu 0
a teda cena cesty predstavuje celkový súčet odhadovaný funkcií.
Teraz majú všetky cesty na hranici
odhadovanú cenu, ktorá je vyššia ako c
a to vieme preto, že hranica je skúmaná v poradí "najlacnejšia najskôr".
Ak je h optimistická, potom je odhadovaná cena
nižšia než skutočná cena,
takže cesta p musí mať cenu nižšiu než je skutočná cena
ľubovoľnej z ciest na hranici.
Ľubovoľné cesty, ktoré zasahujú za hranicu
musia mať cenu vyššiu ako je táto hodnota,
pretože súhlasíme s tým, že cena kroku má vždy hodnotu 0 alebo viac.
To znamená, že cesta p musí byť cestou s minimálnou cenou.
Teraz by sme mali povedať, že toto platí len pre
stromové prehľadávanie.
Pri prehľadávaní v grafe je debata o niečo zložitejšia,
ale všeobecné poznatky sú rovnaké.