Tip:
Highlight text to annotate it
X
Hier geben wir Ihnen eine Idee, warum
eine optimistische heuristische Funnktion, h, den billigsten Pfad findet.
Wenn A beendet wird, wurde Pfad p mit den geschätzten Kosten c errechnet.
Es ergibt sich, dass c den tatsächlichen Kosten entspricht,
weil die h-Komponente am Ziel gleich 0 ist.
Also entsprechen die berechneten Pfadkosten den absoluten Kosten.
Alle Pfade an der Grenze haben
höhere geschätzte Kosten als c,
was wir wissen weil die Grenze nach der Kostenrangfolge erforscht wird.
Wenn h optimistisch ist, dann sind geschätzte Kosten
niedriger als wirkliche Kosten,
also muss Pfad p geringere Kosten haben als die wirklichen Kosten
jedes der Pfade an der Grenze.
Alle Pfade jenseits der Grenze müssen
höhere Kosten als das aufweisen,
weil wir festlegen dass Schrittkosten immer 0 oder mehr betragen.
Das bedeutet, dieser Pfad p muss der billigste Pfad sein.
Ich sollte dazusagen, dass dieses Argument nur für
Baumsuchen gültig bleibt.
Für Graphsuchen ist das Argument etwas komplizierter,
aber die generellen Annahmen bleiben die selben.