Astar-ähnlicher Algorithmus mit unbekanntem Endstatus

Question

A-Stern wird verwendet, um den kürzesten Pfad zwischen einem Startknoten und einem Endknoten in einem Graphen zu finden. Welcher Algorithmus wird verwendet, um etwas zu lösen, wenn der Zielzustand nicht spezifisch bekannt ist und wir stattdessen nur Kriterien für den Zielzustand haben?

Zum Beispiel kann ein Sudoku-Rätsel mit einem Astar-ähnlichen Algorithmus gelöst werden? Wir wissen nicht, wie der Endzustand aussehen wird (welche Nummer ist wo), aber wir kennen die Regeln von Sudoku, ein Kriterium für einen Gewinnerstaat. Also Ich habe einen Startknoten und nur ein Kriterium für den Endknoten, welchen Algorithmus zu verwenden?

Answer 1

Sie müssen nicht den genauen Ziel-Endzustand kennen. Es kommt alles auf die heuristische Funktion an, wenn Sie 0 zurückgeben, können Sie annehmen, dass Sie (mindestens) einen der gültigen Endzustände gefunden haben.

So überprüfen Sie während des a *, ob current_node == target_node, ob current_node.h() 0 zurückgibt. Wenn dies der Fall ist, sollte es unendlich nahe sein und/oder das Ziel/Endstate überlappen.

Answer 2

A * erfordert eine Grafik, eine Kostenfunktion für die Traversierung dieses Graph einer Heuristik, ob ein Knoten in dem Graphen ist näher an das Ziel als die anderen, und einen Test, ob das Ziel erreicht ist. nur eine global Kosten (die Anzahl der ungelösten Quadrate), so dass alle Traversierungen wären gleich Kosten, also A * nicht wirklich helfen

einen Lösungsraumes Sudoku Suche wirklich keine Traversal Kosten zu minimieren, hat - jedes Zelle, die Sie Kosten eine Bewegung zuweisen und Sie einen näher an das Ziel bewegt, so wäre A * nicht besser, als den nächsten Schritt zufällig zu wählen.

Es könnte möglich sein, eine A * Suche basierend auf den geschätzten/gemessenen Kosten der Anwendung der verschiedenen Techniken an jedem Punkt anzuwenden, die dann versuchen würden, einen Weg durch den Lösungsraum mit den geringsten Berechnungskosten zu finden. In diesem Fall wäre der Graph nicht nur der Lösungszustand des Puzzles, sondern Sie würden zwischen den Techniken wählen, die zu diesem Zeitpunkt anzuwenden sind - Sie würden eine Schätzung der Kosten eines Übergangs kennen, aber nicht, wo dieser Übergang stattfindet. geht ', außer dass es, wenn es erfolgreich ist, dem Ziel einen Schritt näher ist.

Answer 3

Ja, A * kann verwendet werden, wenn ein bestimmter Zielzustand nicht identifiziert werden kann. (Pete Kirkham's answer impliziert dies, betont es aber nicht sehr.)

Wenn ein bestimmter Zielzustand nicht identifiziert werden kann, ist es manchmal schwieriger, eine nützliche heuristische Untergrenze für die verbleibenden Kosten zu finden, die für die Fertigstellung eines Teilziels erforderlich sind Lösung - und die Effizienz von A * hängt von der Wahl einer effektiven Heuristik ab. Aber es bedeutet nicht, dass es nicht angewendet werden kann. Beliebiges Problem, das auf einem Computer gelöst werden kann, kann mit einer Breitensuche und einer Reihe von Flags gelöst werden, die anzeigen, ob ein Zustand vorher gesehen wurde; Das ist das gleiche wie A * mit einer heuristischen Untergrenze, die immer Null ist. (Natürlich ist dies nicht der effizienteste Algorithmus zum Lösen vieler Probleme.)