In Anbetracht des folgenden Bildes muss ich die optimalste Sequenz auf der Platine (die grüne Linie) ermitteln. Die blau / roten Linien repräsentieren mögliche, aber nicht die besten Züge.
Hier sind die Regeln:
- Du kannst auf jedes gleiche Plättchen gehen, das dein Nachbar ist (Diagonale ist gültig)
- Sobald Sie ein Plättchen besucht haben, können Sie es nicht mehr besuchen.
Ich habe darüber nachgedacht, jeden Knoten zu durchlaufen, seine Nachbarn zu betrachten und dann rekursiv durchzugehen. Sobald ich einen möglichen Zug gefunden habe, kann ich ihn in eine Struktur einfügen. Sobald alle möglichen Züge gefunden sind, wähle ich einfach den Zug mit der höchsten Anzahl von Knoten aus. Es wird schwieriger, wenn ein Knoten mehr als einen Nachbarn hat, der passt.
Gibt es einen Algorithmus, den ich verwenden kann? Ich dachte an eine Art Überflutung, aber das entspricht nicht den Regeln Nr. 2.
Auf Anfrage hier ein Video mit ähnlichem Gameplay. http://youtube.com/watch?v=eumnCTG0AE8
Antworten:
Sie können jede Gruppe verknüpfter identischer Symbole (und mit Verknüpfen meine ich, Sie können von einem Symbol zum nächsten wechseln) als separate Grafik betrachten . Wenden Sie für jedes dieser Diagramme eine Tiefensuche ( Depth First Search, DFS) an, die von jedem Knoten im Diagramm ausgeht , der nicht bereits Teil des längsten Pfads für dieses Diagramm ist . Überprüfen Sie jedes Mal, wenn Sie beim Anwenden einer DFS eine Sackgasse erreichen, ob der gerade zurückgelegte Pfad länger ist als das globale Maximum, das Sie bisher gefunden haben. Wenn dies der Fall ist, speichern Sie es als neuen längsten Pfad.
Sie werden feststellen, dass ich im vorherigen Absatz erwähnt habe, dass ein DFS für jedes Diagramm mehrmals angewendet wird. Ein einzelnes DFS, das in einem Diagramm ausgeführt wird, würde nicht ausreichen. Betrachten Sie diesen speziellen Fall:
Wenn Sie zufällig zuerst ein DFS für dieses Diagramm im obersten Knoten ausführen würden, würden Sie den längsten möglichen Pfad als vertikale Linie erkennen, aber das wäre nicht korrekt. Dies geschieht jedes Mal, wenn Sie den DFS-Algorithmus in einem Knoten starten, der sich irgendwo im resultierenden Pfad befindet oder überhaupt nicht dazu gehört. In diesem Beispiel müssen Sie außerdem einen DFS-Algorithmus vom äußersten linken Knoten in der zweiten Zeile starten. Das wird den richtigen Weg finden. Im Allgemeinen müssen Sie DFS-Algorithmen in jedem Knoten ausführen, der derzeit nicht zum längsten Pfad für dieses Diagramm gehört, wie oben angegeben.
Das absolut ungünstigste Szenario für diesen Algorithmus wäre ein Brett, das mit einem einzigen Symboltyp gefüllt ist oder größtenteils gefüllt ist, was jedoch im Spiel unwahrscheinlich ist. Achten Sie auch darauf, wie Sie die längsten Pfade für jedes Diagramm speichern. Wenn Sie dieses Bit nicht optimieren, ist es möglicherweise besser, nur ein DFS für jeden Knoten auf der Bühne aufzurufen. Angenommen, Sie arbeiten nicht mit sehr großen Boards und die Geschwindigkeit ist kein so großes Problem, sollte diese Lösung schnell genug sein.
Technisch gesehen ergeben sich durch die Zerlegung Ihres Boards in separate Diagramme mehrere " Probleme mit dem längsten Pfad ". Wie aus Ihrem Beispiel hervorgeht, können Sie Zyklen in Ihrem Diagramm haben (z. B. alle Symbole auf der Außenseite der Bühne desselben Typs). Dies bedeutet, dass Sie in diesem speziellen Problem den längsten Pfad finden müssen in mehreren zyklischen ungerichteten Graphen, was in polynomieller Zeit nicht möglich ist .
Wenn Sie feststellen, dass dies zu langsam ist, finden Sie in dieser Antwort auf StackOverflow weitere Informationen zum Optimieren der einzelnen "Probleme mit dem längsten Pfad".
quelle