Wir haben ein Schulprojekt, wo wir ein 8x8 Spielbrett mit Stücken haben. Das Ziel ist es, jedes Stück auf ein beliebiges Quadrat der gegenüberliegenden hinteren Reihe zu bringen. Die Teile können sich nur vorwärts bewegen, aber in jeder Vorwärtsrichtung (vorwärts-links, vorwärts oder vorwärts-rechts).Gibt es einen besseren Pfadfindungsalgorithmus als A *, wenn Sie mehrere Quellen und mehrere Ziele haben?
Wir konnten das Board als gerichteter azyklischer Graph darstellen, und mit den verschiedenen Spielregeln konnten wir auch an jeder Kante ein Gewicht setzen. Kurz gesagt, wir sind wegweisend, mit jedem Stück als möglichem Ursprung, zu irgendeinem der hinteren Reihenquadrate, um den Weg des geringsten Widerstands von jedem Stück zu finden, um zu beenden. Außerdem wird am meisten Widerstand in der Nähe der Ziellinie getroffen werden.
Unser Programm verbringt jedoch viel Zeit damit. Wir glauben, dass dies daran liegt, dass viele Wege extrem ähnlich schwer sind, vor allem, da jeder mögliche Schritt zum Sieg führen wird (da es nur möglich ist vorwärts zu gehen und alle hinteren Reihen sind Ziele). Es gibt keine Hindernisse auf diesem Board, nur Kanten, die schwerer sind, so dass wir viele offene Knoten haben, die alle "gut aussehen".
Unsere heuristische Funktion ist sehr einfach:
movement_cost = # movement cost here #
def heuristic(node):
return node.cost + node.distanceToFinish * movement_cost
Wo node.cost die Summe der Gewichte der verfahrenen Kanten sowie movement_cost mal die Anzahl der durchquerten Kanten.
Gibt es einen Algorithmus, der effizienter als A * für Fälle mit mehreren Ursprüngen und mehreren Zielen ist? Das Board wird auch nie größer als 8x8 sein, daher sind wohl auch platzhungrige Algorithmen willkommen.
EDIT Wir dachten an den Stücken von Finish Wegfindung, aber das macht eine Menge Komplexität der heuristischen Funktion, da wir jetzt den Überblick über jedes Stück eher zu halten als nur verfolgen, wie weit wir sind aus die letzte Zeile.
Ich bin daran interessiert, etwas ähnliches zu tun. Insbesondere bin ich daran interessiert, einen Pfad zu finden, der einen bestimmten Punkt enthält - zum Beispiel die Wegbeschreibung zu einem Ziel, das auch einen Halt an einer Tankstelle enthält. Weißt du, ob es möglich ist, A * anzupassen, um das zu tun? – EJoshuaS
@EJoshuaS, klingt, als ob du versuchst, eine Version des Problems des Geschäftsreisenden zu lösen. – zneak
Guter Punkt - es scheint etwas eingeschränkter zu sein als das "klassische" Travelling-Salesman-Problem, an das ich mich aus der KI-Klasse erinnere, weil man die Punkte in einer bestimmten Reihenfolge besuchen muss (wenn ich mich richtig erinnere, verlangt die Originalversion das nur Sie enden dort, wo Sie angefangen haben), aber das ist immer noch eine legitime Variante davon. Würde das bedeuten, dass A * eine schlechte Wahl ist? Muss ich dies noch als TSP-Variante behandeln, wenn es nur zwei Punkte gibt? – EJoshuaS