Tip:
Highlight text to annotate it
X
Zde naleznete poznatky proč
optimistická heuristická funkce, h, nalezne nejméně nákladnou trasu.
Pokud je A ukončena, vrátí cestu, p, s odhadovanou cenou, c.
Ukáže se, že c je také skutečná cena,
protože v cíli má komponenta h hodnotu 0
a tudíž cena cesty představuje celkový součet odhadnutý funkcí.
Nyní mají všechny cesty na hranici
odhadovanou cenu, která je vyšší než c
a to víme proto, že hranice je zkoumána v pořadí "nejlevnější nejdřív".
Pokud je h optimistická, pak je odhadovaná cena
nižší než skutečná cena,
takže cesta p musí mít cenu nižší než je skutečná cena
libovolné z cest na hranici.
Libovolné cesty, které zasahují za hranici
musí mít cenu vyšší než je tato hodnota,
protože souhlasíme s tím, že cena kroku má vždy hodnotu 0 nebo více.
Takže to znamená, že cesta p musí být cestou s minimální cenou.
Nyní bychom měli říct, že takto to platí pouze pro
stromové prohledávání.
Při prohledávání v grafu je debata o něco složitější,
ale obecné poznatky jsou stejné.