(Dies ist nicht genau das Problem, das ich habe, aber es ist isomorph, und ich denke, dass diese Erklärung für andere am einfachsten zu verstehen sein wird.)
Angenommen, ich habe eine Menge von Punkten in einem n -dimensionalen Raum. Verwenden Sie zum Beispiel 3 Dimensionen:
%Vor%Ich habe auch eine Reihe von Vektoren, die mögliche Bewegungen in diesem Raum beschreiben:
%Vor%Nun, da ich einen Punkt dest habe, muss ich einen Anfangspunkt finden p und eine Reihe von Vektoren bewegt , die mich dazu bringen werden dest auf die effizienteste Weise. Effizienz ist definiert als "möglichst wenige Züge", nicht unbedingt "kleinste lineare Entfernung": Es ist zulässig, ein p zu wählen, das weiter von dest entfernt ist als andere Kandidaten, wenn der Zug gesetzt wurde ist so, dass du mit weniger Zügen dahin kommen kannst. Die Vektoren in moves müssen eine strikte Teilmenge der verfügbaren Vektoren sein; Sie können den gleichen Vektor nicht mehr als einmal verwenden, es sei denn, er erscheint mehr als einmal im Eingabe-Set.
Meine Eingabe enthält ~ 100 Startpunkte und vielleicht ~ 10 Vektoren, und meine Anzahl an Dimensionen ist ~ 20. Die Startpunkte und verfügbaren Vektoren werden für die Lebensdauer der App festgelegt, aber ich werde Pfade für viele, viele verschiedene dest Punkte finden. Ich möchte auf Geschwindigkeit und nicht auf Speicher optimieren. Es ist akzeptabel, dass der Algorithmus fehlschlägt (um keine möglichen Pfade zu dest zu finden).
Ich habe eine Lösung angenommen, die der nachstehend als "akzeptiert" sehr ähnlich ist. Ich iteriere über alle Punkte und Vektoren und erstelle eine Liste aller erreichbaren Punkte mit den Routen, um sie zu erreichen. Ich konvertiere diese Liste in einen Hash von & lt; em> Ziel , p + Vektoren & gt; und wähle den kürzesten Satz von Vektoren für jeden Zielpunkt aus. (Es gibt auch ein wenig Optimierung für die Hash-Größe, die hier nicht relevant ist.) Nachfolgende dest Abfragen finden in konstanter Zeit statt.
Wenn man bedenkt, dass Sie ungefähr 10 Vektoren haben, können Sie für einen gegebenen Ziel Punkt nur die 1024 "Ziele" aus der Teilmenge von Vektoren berechnen - zB jeder erreichbare Raum, mit der Information darüber, was für eine Bewegung erreicht wird. Das kann je nach Kontext "langsam" oder "schnell" sein (es ist absurd schnell, wenn es auf einem parallelen Computergerät wie der GPU implementiert wird).
Mit allen Sets, die dorthin kommen, können Sie die Pfade viel schneller berechnen, dann können Sie den Punkt auswählen, von dem Sie zu dest in den wenigsten Zügen gelangen, indem Sie aus der Teilmenge der Einsen wählen das sind entweder Ihre Anfrage oder weiter.
(Danke an Strilanc)
Sie möchten also eine Teilmenge Ihrer Vektoren so finden, dass die Teilmenge zu einem bestimmten Wert addiert wird. In 1 Dimension wird dies als Subset-Summenproblem bezeichnet und ist NP-Complete.
Zum Glück haben Sie nur ~ 10 Vektoren, also ist Ihre Problemgröße eigentlich ziemlich klein und handlich. Beginnen Sie damit, alle 2 ^ 10 Zugkombinationen für jeden Startpunkt auszuprobieren und den besten auszuwählen. Dann arbeite von dort nach einfachen Optimierungen.
Einige einfache Optimierungen, die funktionieren könnten:
Wenn Sie die Startpunkte und einen festen Vektorsatz haben, können Sie die Liste aller erreichbaren Ziele berechnen und dann einfach nach einem bestimmten Ziel suchen?
Wie Kornel sagt, haben Sie höchstens 2 ^ 10 = 1024 erreichbare Ziele. Sie können also alle erreichbaren Ziele in 2 ^ N Zeit (wobei N die Anzahl der Vektoren ist) durch eine einfache rekursive Generierung erzeugen. Das wird natürlich schnell genug sein. Nehmen wir an, Sie wollten es dehnen.
Sie könnten es auf 0 (2 ^ (N / 2 + 1)) Zeit optimieren, indem Sie eine Meet-in-the-Middle-Lösung verwenden. Sie teilen den Vektorsatz in zwei Teilmengen auf und generieren unabhängig voneinander alle erreichbaren Ziele für jede Teilmenge. Sie durchlaufen dann einen Satz erreichbarer Ziele und finden für jeden Ort den Unterschied zwischen dem Ziel und dem Ziel. Wenn sich dieser Differenzvektor in der anderen Gruppe erreichbarer Ziele befindet, haben Sie eine Lösung: Kombinieren Sie die beiden und Sie sind fertig. Die Schwierigkeit hierbei besteht darin, effizient abzufragen, ob Sie den erforderlichen Vektor in der anderen Menge haben: Dies kann in O (1) -Zeit unter Verwendung einer Hash-Tabelle erfolgen.
Das ist O (2 ^ (N / 2)) Zeit pro Teilmenge, mal geben zwei Teilmengen O (2 ^ (N / 2 + 1)). Um die beiden zu verbinden, ist es O (2 ^ (N / 2)) Zeit. Das gibt uns insgesamt O (2 ^ (N / 2 + 1)) Zeit.
Tags und Links algorithm language-agnostic path-finding