Zulässige Heuristik
Im Informatik, speziell in Algorithmen im Zusammenhang mit Wegfindung, a Heuristische Funktion wird gesagt, dass zulässig Wenn es nie die Kosten für das Erreichen des Ziels überschätzt, d. H. Die Kosten, die es schätzt, um das Ziel zu erreichen, sind nicht höher als die niedrigsten Kosten aus dem aktuellen Punkt im Pfad.[1]
Es bezieht sich auf das Konzept von konsequente Heuristik. Während alle konsistenten Heuristiken zulässig sind, sind nicht alle zulässigen Heuristiken konsistent.
Suchalgorithmen
Eine zulässige Heuristik wird verwendet, um die Kosten für das Erreichen des Zielstatus in einem abzuschätzen Informierter Suchalgorithmus. Damit eine Heuristik für das Suchproblem zulässig ist, müssen die geschätzten Kosten immer niedriger sein als oder gleich den tatsächlichen Kosten für das Erreichen des Zielzustands. Der Suchalgorithmus verwendet die zulässige Heuristik, um einen geschätzten optimalen Weg zum Zielstatus aus dem aktuellen Knoten zu finden. Zum Beispiel in Eine Suche die Bewertungsfunktion (wo ist der aktuelle Knoten) ist:
wo
- = die Bewertungsfunktion.
- = die Kosten vom Startknoten zum aktuellen Knoten
- = Geschätzte Kosten vom aktuellen Knoten zum Ziel.
wird mit der heuristischen Funktion berechnet. Mit einer nicht zulässigen Heuristik könnte der A* -Algorithmus die optimale Lösung für ein Suchproblem aufgrund einer Überschätzung in übersehen .
Formulierung
- ist ein Knoten
- ist eine Heuristik
- ist die Kosten angezeigt durch ein Ziel zu erreichen von
- sind die optimalen Kosten, um ein Ziel zu erreichen
- ist zulässig, wenn,
Konstruktion
Eine zulässige Heuristik kann von a abgeleitet werden entspannt Version des Problems oder nach Informationen aus Musterdatenbanken, die genaue Lösungen für Unterprobleme des Problems oder durch Verwendung speichern induktives Lernen Methoden.
Beispiele
Zwei verschiedene Beispiele für zulässige Heuristiken gelten für die Fünfzehn Puzzle Problem:
Das Hamming -Entfernung ist die Gesamtzahl der fehlgeleiteten Fliesen. Es ist klar, dass diese Heuristik zulässig ist, da die Gesamtzahl der Bewegungen, um die Kacheln korrekt zu bestellen, mindestens die Anzahl der fehlgeleiteten Fliesen beträgt (jede nicht vorhandene Fliese muss mindestens einmal bewegt werden). Die Kosten (Anzahl der Bewegungen) für das Ziel (ein geordnetes Puzzle) sind mindestens das Hamming -Entfernung des Puzzles.
Die Manhattan -Distanz eines Puzzles ist definiert als:
Betrachten Sie das Puzzle unten, in dem der Spieler jede Kachel so bewegen möchte, dass die Zahlen bestellt werden. Die Distanz von Manhattan ist in diesem Fall eine zulässige Heuristik, da jede Fliese mindestens die Anzahl der Stellen zwischen sich und seiner korrekten Position bewegt werden muss.[2]
43 | 61 | 30 | 81 |
72 | 123 | 93 | 144 |
153 | 132 | 14 | 54 |
24 | 101 | 111 |
Die Einbilder zeigen die Distanz von Manhattan für jede Kachel. Der gesamte Manhattan -Abstand für das gezeigte Puzzle ist:
Optimaler Beweis
Wenn eine zulässige Heuristik in einem Algorithmus verwendet wird, der per Iteration nur den Weg der niedrigsten Bewertung (aktuelle Kosten + Heuristik) mehrerer Kandidatenpfade voranschreitet, endet der Moment, in dem ihre Erforschung das Ziel erreicht und vor allem niemals alle optimalen Wege vor dem Ende schließt enden (etwas, das mit möglich ist Ein* Suchalgorithmus Wenn besondere Sorgfalt nicht erledigt wird[3]), dann kann dieser Algorithmus nur auf einem optimalen Weg enden. Um zu sehen, warum, betrachten Sie Folgendes Beweis durch Widerspruch:
Angenommen, ein solcher Algorithmus gelang es, mit echten Kosten auf einem Pfad t zu enden TStimmt größer als der optimale Pfad s mit echten Kosten SStimmt. Dies bedeutet, dass vor der Beendigung die bewerteten Kosten von T kleiner oder gleich den bewerteten Kosten von S (oder S wären ausgewählt worden wären). Bezeichnen diese bewerteten Kosten Tbewerten und Sbewerten beziehungsweise. Das obige kann wie folgt zusammengefasst werden,
- SStimmt < TStimmt
- Tbewerten ≤ Sbewerten
Wenn unsere Heuristik zulässig ist, folgt dies bei diesem vorletzten Schritt Tbewerten = TStimmt Weil jede Erhöhung der wahren Kosten der Heuristik auf T unzulässig wäre und die Heuristik nicht negativ sein kann. Andererseits würde eine zulässige Heuristik das erfordern Sbewerten ≤ SStimmt die kombiniert mit den oben genannten Ungleichheiten gibt uns Tbewerten < TStimmt und genauer gesagt Tbewerten ≠ TStimmt. Wie Tbewerten und TStimmt Kann nicht gleich und ungleich sein, dass unsere Annahme falsch gewesen sein muss, und daher muss es unmöglich sein, auf einem teureren als optimalen Weg zu enden.
Als Beispiel,[4] Nehmen wir an, wir haben Kosten wie folgt: (Die Kosten oben/unter einem Knoten sind die Heuristik, die Kosten bei einer Kante sind die tatsächlichen Kosten)
0 10 0 100 0 Start ---- O ----- Ziel | | 0 | | 100 | | O ------- o ------ o 100 1 100 1 100
Also würden wir den oberen mittleren Knoten eindeutig besuchen, da die erwarteten Gesamtkosten, d.h. , ist . Dann wäre das Ziel ein Kandidat mit gleicht . Dann würden wir eindeutig die unteren Knoten nacheinander auswählen, gefolgt vom aktualisierten Ziel, da sie alle haben niedriger als die des aktuellen Ziels, d. h. ihre ist . Obwohl das Ziel ein Kandidat war, konnten wir es nicht auswählen, weil es da draußen immer noch bessere Wege gab. Auf diese Weise kann eine zulässige Heuristik eine Optimalität gewährleisten.
Beachten Sie jedoch, dass eine zulässige Heuristik zwar die endgültige Optimalität garantieren kann, dies jedoch nicht unbedingt effizient ist.
Verweise
- ^ Russell, S.J.; Norvig, P. (2002). Künstliche Intelligenz: ein moderner Ansatz. Prentice Hall. ISBN 0-13-790395-2.
- ^ Korf, Richard E. (2000), "Jüngste Fortschritte bei der Gestaltung und Analyse zulässiger heuristischer Funktionen" (PDF)in Choueiry, Berthe Y.; Walsh, Toby (Hrsg.), Abstraktion, Umformulierung und Näherung: 4. Internationales Symposium, Sara 2000 Horseshoe Bay, USA, 26. bis 29. Juli 2000 Proceedings, vol. 1864, Springer, S. 45–55, Citeseerx 10.1.1.124.817, doi:10.1007/3-540-44914-0_3, ISBN 978-3-540-67839-7, abgerufen 2010-04-26
- ^ Holte, Robert (2005). "Häufige Missverständnisse in Bezug auf heuristische Suche". Verfahren des dritten jährlichen Symposiums über kombinatorische Suche (SOCS).
- ^ "Warum zulässt [sic] Heuristik garantiert Optimalität? ".Algorithmus. Paketüberfluss. Abgerufen 2018-12-11.