Konzistentní heuristika - Consistent heuristic

Při studiu problémů hledání cesty v umělé inteligenci se o heuristické funkci říká, že je konzistentní nebo monotónní , pokud je její odhad vždy menší nebo roven odhadované vzdálenosti od jakéhokoli sousedního vrcholu k cíli, plus náklady na dosažení ten soused.

Formálně, pro každý uzel N a každé nástupce P z N , odhadované náklady na dosažení cíle z N není vyšší než náklady na stupni dostává k P plus odhadované náklady na dosažení cíle z P . To je:

${\ Displaystyle h (N) \ leq c (N, P) + h (P)}$ a

${\ displaystyle h (G) = 0. \,}$

kde

• h je konzistentní heuristická funkce
• N je libovolný uzel v grafu
• P je potomek N
• G je jakýkoli uzel cíle
• c (N, P) je cena za dosažení uzlu P z N

Neformálně každý uzel i dá odhadnout, že účtování nákladů k dosažení další uzel, je vždy nižší než odhad na uzel i + 1 .

Rovněž je přípustná konzistentní heuristika , tj. Nikdy nadhodnocuje náklady na dosažení cíle ( konverzace však není vždy pravdivá). To se dokazuje indukcí .

Nechť je odhadovaná cena pro uzel cíle. To znamená, že základní podmínka je triviálně platí jako 0 ≤ 0. Protože je heuristický je konzistentní . Uvedené podmínky se rovnají skutečné ceně, takže je přípustná i jakákoli konzistentní heuristika, protože je překonána skutečnou cenou. ${\ displaystyle h (N_ {0}) = 0}$${\ Displaystyle h (N_ {i + 1}) \ leq c (N_ {i + 1}, N_ {i}) + h (N_ {i}) \ leq c (N_ {i + 1}, N_ {i }) + c (N_ {i}, N_ {i-1}) + h (N_ {i-1}) \ leq c (N_ {i + 1}, N_ {i}) + c (N_ {i} , N_ {i-1}) + ... + c (N_ {1}, N_ {0}) + h (N_ {0})}$${\ displaystyle \ sum _ {i = 1} ^ {n} c (N_ {i}, N_ {i-1})}$

Konverzace zjevně není pravdivá, protože vždy můžeme sestavit heuristiku, která je vždy pod skutečnou cenou, ale je nekonzistentní, například zvýšením heuristického odhadu od nejvzdálenějšího uzlu, jak se přibližujeme, a když se odhad stane maximálně skutečné náklady , vyděláváme . ${\ displaystyle h (N_ {i})}$${\ displaystyle h ^ {*} (N_ {i})}$${\ displaystyle h (N_ {i-1}) = h (N_ {i}) - c (N_ {i}, N_ {i-1})}$

Důsledky monotónnosti

Srovnání přípustné, ale nekonzistentní a konzistentní heuristické hodnotící funkce.

Konzistentní heuristiky se nazývají monotónní, protože odhadované konečné náklady na částečné řešení monotónně neklesají podél nejlepší cesty k cíli, kde jsou náklady na nejlepší cestu od počátečního uzlu k . Aby byl heurista konzistentní, je nutné dodržovat nerovnost trojúhelníku . ${\ displaystyle f (N_ {j}) = g (N_ {j}) + h (N_ {j})}$${\ displaystyle g (N_ {j}) = \ součet _ {i = 2} ^ {j} c (N_ {i-1}, N_ {i})}$${\ displaystyle N_ {1}}$${\ displaystyle N_ {j}}$

V konzistentním heuristickém algoritmu A * znamená použití konzistentní heuristiky, že jakmile se uzel rozbalí, cena, o kterou byl dosažen, je nejnižší možná za stejných podmínek, jaké vyžaduje Dijkstrův algoritmus při řešení problému s nejkratší cestou (žádné negativní hrany nákladů ). Ve skutečnosti, pokud je vyhledávacímu grafu dána cena za konzistentní , pak A * je ekvivalentní nejlepšímu prvnímu vyhledání v tomto grafu pomocí Dijkstrova algoritmu. V neobvyklém případě, že přípustná heuristika není konzistentní, bude uzel potřebovat opakovanou expanzi pokaždé, když pro něj bude dosažena nová nejlepší (dosud) cena. ${\ displaystyle c '(N, P) = c (N, P) + h (P) -h (N)}$${\ displaystyle h}$

Pokud je daná heuristika přípustná, ale není konzistentní, lze uměle přinutit heuristické hodnoty podél cesty, aby byly monotónně neklesající pomocí ${\ displaystyle h}$

${\ Displaystyle h '(P) \ dostane \ max (h (P), h' (N) -c (N, P))}$

jako heuristická hodnota pro místo , kde je uzel bezprostředně předcházející na cestě a . Tato myšlenka je zásluhou László Mero a je nyní známá jako pathmax. Na rozdíl od obecné víry, pathmax nezmění přípustnou heuristiku na konzistentní heuristiku. Například pokud A * používá pathmax a heuristiku, která je přípustná, ale není konzistentní, není zaručeno, že bude mít optimální cestu k uzlu při prvním rozbalení. ${\ displaystyle P}$${\ displaystyle h (P)}$${\ displaystyle N}$${\ displaystyle P}$${\ displaystyle h '(start) = h (start)}$

Viz také

• Přípustná heuristika

Reference