heuristic suite

Heuristische Suite

Wichtiger Hinweis

Das Projekt steht nicht mehr in der Wartung. Bitte besuchen Sie Linq zu A* für die neueste Version.

Überblick

Die Heuristische Suite ist eine experimentelle Implementierung einer Reihe heuristischer Algorithmen in der generischen Programmierung. Das Projekt soll eine Infrastruktur bereitstellen, die auf jedes Puzzle angewendet werden kann - solange das Puzzle mit dem Algorithmus gelöst werden kann.

Implementierte Algorithmen:

• A*
• Iterative Vertiefung a* (Ida*)
• Beste erste Suche
• Rekursive beste erste Suche (RBFs)

Die Implementierung ist vollständig objektorientiert und nimmt Vorteile des integrierten .NET-Framework-Vergleichsmechanismus wie Icparer (T) und IequalityComparer (T) ein, um eine hervorragende Kompatibilität mit .NET Standard und dem gesamten .NET-Ökosystem zu schaffen. Der Quellcode kann leicht auf andere Plattformen wie Einheit und Xamarin gebracht werden.

Rätsel mit Algorithmus lösen

Um den Algorithmus auf Puzzle anzuwenden, sind folgende Implementierungen erforderlich:

1. Schritt Definition Der Typ, der Schritt des Puzzles definiert, muss die ISTEP -Schnittstelle (TKY) implementieren. Die Key Eigenschaft dient zwei Zwecken:

   • Um zu testen, ob zwei Schritte gleichwertig sind. Zum Beispiel: Gleiche Position auf der Tafel.
   • Vergleichen Sie zwei Schritte, um festzustellen, welche eine bessere Punktzahl hat. Zum Beispiel: Der Abstand zwischen Position A und Ziel und die Entfernung zwischen Position B und Ziel, je näher einer ist.

2. Stufenvergleichsschritte werden basierend auf Key miteinander verglichen, um festzustellen, welche eine bessere Punktzahl hat. Der Vergleich kann auf eine der folgenden Arten durchgeführt werden:

   • Die iComparable (TKY) Implementierung.
   • Eine angepasste IComater (TKY) -Instanz.
   • Die explizit angegebene H (n) -Funktion, wobei der Parameter n der Key ist.

3. Die verfügbaren Schritte aus dem aktuellen Schritt Nächster Schritt Informationen können durch die Implementierung der Interface INextStepFactory(TKey, TStep) oder der Bereitstellung von NextStepFactory -Delegierten bereitgestellt werden.

Danach kann der Algorithmus durch Aufrufen FindSolution -Methode from und goal als Parameter ausgeführt werden. Wenn die Lösung vorhanden ist, kann jede Schritte durch Aufrufen Enumerate der Methode erhalten werden. Die Schritte können Reverse sein, bevor die Aufzählung beginnt.

Heuristischer Vergleich und diskreter heuristischer Vergleiche

Das Projekt bietet HeuristicComparer und DiscreteHeuristicComparer für verschiedene Szenarien für Schrittvergleiche.

• Wenn die Key ohne explizite H (n) -Funktion direkt miteinander verglichen werden kann, wird DiscreteHeuristicComparer standardmäßig für einen schnelleren Schrittvergleich verwendet.
• Wenn die H (n) -Funktion explizit benötigt wird, um jede Schritte zu vergleichen, wird der HeuristicComparer verwendet, um die herkömmliche Schätzung F (n) = g (n) + H (n) durchzuführen.

Heuristische Funktionpräferenz

Mit der HeuristicFunctionPreference -Aufzählung können Benutzer das Gleichgewicht der Schätzung f (n) = g (n) + h (n) ändern. Wenn zwei Schritte bewertet werden, wird die Aufzählung entscheidet, welche Funktion G (n) oder H (n) zuerst berücksichtigt wird. Das veränderte Gleichgewicht kann das Verhalten des heuristischen Algorithmus beeinflussen.

Beispiele

• Pfadfindung (Algorithmforce.example.Pathfinding)

  Das Beispiel zeigt das häufigste und traditionellste Puzzle, das heuristische Algorithmen verwendet, um zu lösen.

• 8-Puzzle (Algorithmforce.example.EightPuzzle)

  Das Beispiel zeigt, wie man die 8-Puzzle mit heuristischem Algorithmus löst. Die anfänglichen und Zielschritte des Puzzles sind unten dargestellt:

• Münzen Flipping Puzzle (algorithmforce.example.coinsflipping)

  Dieses Beispiel zeigt, wie das Spiel AI die Münzen löst, das das Puzzle dreht. Im Puzzle darf nur ein Paar benachbarte Münzen gleichzeitig umgedreht werden. Alle zehn Münzen, die Kopf sind, sind das Ziel. Das Puzzle ist von Brilliant.org inspiriert.

Weitere Beispiele werden in Zukunft hinzugefügt.

Plattform

Das Projekt zielt derzeit ab .NET Core und .NET Framework 4.5 oder höher.