Ich weiß, dass eine heuristische Funktion, die die tatsächliche Entfernung zum Ziel nie überschätzt, als zulässig bezeichnet wird. Ich habe in der Praxis eine heuristische Funktion gefunden, aber ich weiß nicht, wie man einen formellen Beweis gibt. Wie kann ich beweisen, dass eine heuristische Funktion zulässig ist? Zum Beispiel: Manhattan Entfernung Heuristik.Wie beweisen Zulässigkeit einer heuristischen Funktion
Wenn Sie die tatsächliche Entfernung vom Ziel formell definieren können, können Sie eine Einschränkung einfach eliminieren, um eine zulässige Heuristik zu entwickeln.
Zum Beispiel: Der Manhattan-Abstand von einem Punkt (x1, y1) zu Punkt (x2, y2) gleich | x1-x2 | + | Y1-Y2 |. Sie können einen Begriff einfach eliminieren, um eine Heuristik zu erstellen. Zum Beispiel h = | x1-x2 |. Um zu beweisen, dass dies eine zulässige Heuristik ist, zeigen Sie, dass | x1-x2 | ist kleiner oder gleich | x1-x2 | + | y1-y2 |
... für alle x1, x2, y1, y2.
Eine andere zulässige Heuristik wäre die geradlinige Entfernung, und Sie können beweisen, dass das immer weniger als die Manhattan-Entfernung ist.
Im Allgemeinen werden relaxierende Bedingungen zu zulässigen Heuristiken führen.
Wenn Sie mit Entfernungen arbeiten, wird die gerade Linie immer eine zulässige Heuristik sein, denn das wird niemals eine Überschätzung sein.
Lassen Sie mich wissen, ob dies Ihre Frage beantwortet :)