Tip:
Highlight text to annotate it
X
Burada size, olumlu bir sezgisel "h" fonksiyonunun
neden en düşük maliyetli yolu verdiğini göstereceğiz.
A-Yıldız araması sona erdiğinde, "p" yolunu ve "c" tahmini maliyetini döndürür.
Aslında "c" aynı zamanda gerçek maliyete eşittir;
çünkü hedef için "h" bileşeni 0'dır,
ve böylece yol maliyeti fonksiyon tarafından hesap edilen toplam maliyete eşittir.
Şimdi, sınırda bulunan bütün yollar
"c" değerinden daha büyük bir tahmini maliyete sahiptir,
ve bunun böyle olduğunu biliyoruz, çünkü sınır en düşük maliyet öncelikli olarak keşfedilir.
Eğer "h" olumluysa, o zaman
tahmini maliyet gerçek maliyetten daha düşüktür.
Yani "p" yolu sınırdaki herhangi bir yol için
gerçek maliyetten daha düşük bir maliyete sahiptir.
Sınırdan sonraki herhangi bir yolun
daha yüksek bir maliyeti olması gerekir
çünkü adım maliyeti her zaman 0 veya daha fazla olarak hesaplanır.
Demek oluyor ki, "p" yolu, asgari maliyet yoludur.
Ancak bu ispatın yalnızca "ağaç yapılı arama"
için geçerli olduğunu söylemeliyim.
Çizge yapılı arama için ispat biraz daha karmaşık,
ancak demin gördüğümüz genel kurallar aynıdır.