Geschichte
Indiana Jones erkundete eine Höhle, in der sich ein kostbarer Schatz befindet. Plötzlich ereignete sich ein Erdbeben.
Als das Erdbeben endete, bemerkte er, dass einige Steine, die von der Decke gefallen waren, ihm den Weg zum Schatz versperrten. Er bemerkte auch, dass er einen Stein schieben konnte, aber da Steine sehr schwer waren, konnte er nicht zwei aufeinanderfolgende Steine schieben .
Ihr Ziel ist es, Indiana Jones dabei zu helfen, den Schatz zu finden. Da es sehr schwer ist, auch nur einen Stein zu schieben, ist die Anzahl der Schübe sehr wichtig.
Problem
Finde den besten Weg (wo Indiana Jones so wenig wie möglich Steine drückt), um den Schatz zu finden.
Karte (Eingabe)
Die Karte ist ein m
durch n
(beide größer als 1) Matrix , welche fünf Arten von Zellen enthalten kann:
0
was bedeutet, die leere Zelle,1
was bedeutet, die Wand,2
in dem sich Indiana Jones befindet (es gibt nur einen),3
in dem sich der Schatz befindet (nur einer existiert),- und
4
, was einen Stein bedeutet.
In der ersten Zeile der Karte wird die Abmessung der Karte wie folgt angegeben 4 6
, und von der zweiten bis zur letzten Zeile der Karte wird die Struktur der Höhle wie folgt angegeben.
110131
104040
100101
200000
Daher ist die vollständige Karte:
4 6
110131
104040
100101
200000
was bedeutet
Die Karte wird durch stdin, eine Datei (Sie können den Namen der Datei angeben) oder ein Array im Code angegeben, das nur die oben genannten Informationen enthält.
Ausgabe
Der Mindestbetrag, den Indiana Jones pushen sollte. Wenn dies nicht möglich ist, wird ausgegeben X
.
In obigem Fall kann er einen Stein nach links nach oben schieben, dann kann er einen Stein nach rechts nach rechts schieben, um den Schatz zu erhalten. Daher ist die Ausgabe in diesem Fall 2
.
Jedoch. in diesem Fall :
4 6
111131
104040
100101
200000
(siehe Abschnitt unten) Er kann keinen richtigen Stein schieben, da dies den Schatz zerstören wird. Auch das Drücken des linken Steins nach rechts ändert nichts. Daher ist die Ausgabe X
.
Regeln
- Er kann sich nur in vier Richtungen bewegen, nach oben, unten, links und rechts.
- Er kann nicht zwei aufeinanderfolgende Steine schieben .
- Er kann keinen Stein ziehen und er kann einen Stein nur in eine Richtung ('vorwärts') schieben.
- Er kann nicht durch Wände gehen. Nur Orte, an die er gehen kann, sind leere Zellen und die Schatzzelle.
- Der Stein kann nicht auf den Schatz gelegt werden. Das wird den Schatz zerstören. :(
- Er kann die Karte nicht verlassen.
Tore
Programm, das die meisten Karten (im Abschnitt 'Beispiel' und andere) in einer angemessenen Zeit (insbesondere 10 Sekunden) verarbeiten kann und die richtige Antwort ausgibt, gewinnt.
Hier bedeutet "andere" Beispieleingaben, die in Antworten bereitgestellt werden. Dies bedeutet, dass Sie einen intelligenten Algorithmus erstellen sollten, damit andere Programme Karten, die Ihr Programm lösen kann, nicht lösen können, und von anderen Programmen gelöste Karten von Ihrem Programm gelöst werden können. Das Einfügen von Lösungen in den Code wird jedoch nicht als gültig angesehen.
Hinweis
Dies war ursprünglich ein Zwischenprojekt einer KI-Klasse, das ich mir angehört habe. Nur eines war anders: Es wurde gesagt, dass es nur zwei Felsen gab.
Es wurde gesagt, dass dieses Problem NP ist, aber es wurde auch gesagt, dass ein guter heuristischer Algorithmus das Problem ziemlich effizient lösen kann. Ich habe einige Ideen und Heuristiken verwendet, um das Problem effizient zu lösen, und mein Code konnte alle Lösungen von Beispielen sehr schnell finden (weniger als eine Sekunde).
Wenn es jedoch mehr als zwei Steine gab, gab es einige Fälle, in denen der Code die Antwort nicht in angemessener Zeit fand. Ich hatte einige Ideen, aber einige davon waren „falsch“ und ich konnte dem Code keine anderen Ideen mitteilen. Ich wollte sehen, welche intelligenten Algorithmen existieren, um dieses Problem zu lösen, und schrieb dies.
Da ich das Projekt bereits abgeschlossen habe (Bilder sind übrigens nicht meine - ich habe sie gegoogelt), müssen Sie sich darüber keine Gedanken machen.
Beispiele
Beispiele finden Sie hier. Sie können auch Beispiele sehen und testen Sie Ihre Ergebnisse bei hier (dies in modernen Browsern funktionieren sollte). Sie können die Karte in dem oben beschriebenen Format abrufen, indem Sie sie whatisthis()
in die JS-Konsole eingeben .
http://bit.sparcs.org/~differ/sokoban/#0 ~ http://bit.sparcs.org/~differ/sokoban/#19 enthält Beispiele, die ursprünglich von der Klasse bereitgestellt wurden.
Ergebnis
Entschuldigung, ich war spät dran. Eigentlich ziemlich viel. : P (Ich war zu faul, um ein Tor zu erzielen. Entschuldigung.)
Unten ist das Ergebnis. (X: falsch, O: richtig,?: Dauert mindestens 10s, angehalten)
Map#: 0 1 2 3 4 5 12 15 19 T1 T2 T3 T4 T5 T6 T7
Ruby: X O O ? O O O X ? ? O ? ? ? ? ?
Java: O O X O X X O O ? ? O O O X O O
(Java 19: dauerte 25s, das Ergebnis war korrekt.) (Ich habe Ruby 1.9.3 und Javac 1.7.0_13 verwendet.)
Es scheint, dass der Java-Algorithmus in der Tat besser war. (Übrigens habe ich mir eine ähnliche Methode überlegt, aber mir ist aufgefallen, dass es Karten wie die Testkarte 5 gibt.)
quelle
Antworten:
Java - Ein bisschen schlauer / schneller
Da ist ein bisschen Code. Ich versuche, schneller zu sein, indem ich die Schübe in der Reihenfolge auswerte, "wie wahrscheinlich es ist, dass dies einen Weg zum Schatz freigibt", die auf zwei Dijkstra-Durchgängen basiert (einer stoppt, wenn er auf Felsen stößt, der andere ignoriert Felsen). Es funktioniert ziemlich gut, und das eine Beispiel aus dem Pastebin, das für den Autor problematisch zu sein scheint, wird durch diese Implementierung in ca. 2 Sekunden gelöst. Einige andere Beispiele dauern bis zu 30-40 Sekunden, was ich immer noch zu lange finde, aber ich konnte keinen Weg finden, dies zu verbessern, ohne das Zeug zu zerbrechen :)
Ich habe meine Sachen in mehrere Dateien aufgeteilt, um eine bessere Struktur herauszufinden (auch, warum ich von Ruby auf Java umgestiegen bin):
Einstiegspunkt:
Direction-Helfer-Aufzählung:
Eine abstrakte Klasse, die einen lokalisierten Teil des "Labyrinths" darstellt:
Und schließlich das Labyrinth selbst:
quelle
Ruby - Riesig und blostered
Etwas naive Umsetzung, die den Weg durch das Labyrinth bahnt. In einigen (nicht so) seltsamen Fällen ist es nicht superschnell. Es kann verbessert werden, indem bessere Heuristiken gefunden werden als nur "Wenn es näher am Schatz ist, wollen wir zuerst nachforschen", aber die allgemeinen Ideen sind da.
Es wird Ihnen auch zeigen, wie Indiana den Schatz in die Hände bekommen hat, falls er kann, das ist ein Bonus.
Bearbeiten: Ich überlege mir Möglichkeiten, die Leistung in nicht offensichtlichen Situationen (in denen es derzeit grüne Eier saugt) erheblich zu verbessern, indem ich eine einfache Bewegungsbewertung fallen lasse (z. B. nur darauf achten, wann Indy Steine schiebt und / oder zum Schatz gelangt). Ich werde den Code wahrscheinlich später aktualisieren, sobald ich Zeit zum Implementieren hatte.
quelle
C ++ 14 von 16
Der Algorithmus ist ineffizient und speicherhungrig. Außerdem konnte ich mir die Zeit zum Aufräumen nicht leisten, werde es aber tun, wenn ich mehr Zeit habe;) Ein interessanter Punkt ist, dass mein Algorithmus bei denselben Testkarten wie der des Fragestellers versagt. Auf meinem alten Notizbuch beginnt der Prozess, für die Karten T4 und T6 zu tauschen. Map 3 dauert ziemlich lange, ist aber rechtzeitig gelöst. Alle anderen werden fast augenblicklich gelöst. Also muss ich herausfinden, wie man T4 und T6 löst und den Algorithmus auf einer Maschine mit mehr Speicher ausprobieren. Schließlich kann ich dort T4 und T6 lösen. Ich werde den Beitrag auf dem Laufenden halten ...
Unten ist das Ergebnis. (X: falsch, O: richtig,?: Dauert mindestens 10s, angehalten)
Da der Quellcode ziemlich lang und nicht wirklich schön zu lesen ist ... Im Grunde sucht er nur nach allen Steinen, die Indiana Jones erreichen kann. Für die zu erreichenden Felsen werden die Informationen gespeichert, in welche Richtungen sie bewegt werden können. So wird eine Liste möglicher Züge für die aktuelle Karte erstellt. Für jede dieser möglichen Bewegungen wird eine Kopie der Karte erstellt und die Bewegung angewendet. Für die neu erstellten Karten prüft der Algorithmus erneut, welche Züge angewendet werden können ... Dies geschieht, bis entweder keine weiteren Züge mehr möglich sind oder ein Weg zur Schatzkiste gefunden wird. Da der Algorithmus zuerst alle Bewegungen versucht, die nur eine Bewegung benötigen, um zur Brust zu gelangen, dann alle, die zwei benötigen, und so weiter ... Der erste gefundene Weg ist automatisch auch der kürzeste. Um Schleifen zu vermeiden, merkt sich der Algorithmus für jede Karte, welche Bewegungen angewendet werden könnten. Wenn eine andere Karte erstellt wird, die eine Liste der zuvor bereits gefundenen Züge enthält, werden diese stillschweigend gelöscht, da sie bereits verarbeitet werden. Leider ist es nicht möglich, jede Bewegung nur einmal auszuführen, da es Karten geben kann, bei denen ein Stein mehrmals über dasselbe Feld bewegt werden muss. Ansonsten könnte ich viel Speicher sparen. Um auch Karten wie Karte 3 rechtzeitig zu lösen, ignoriert der Algorithmus alle Steine, die herumlaufen können ... Auf Karte 3 wird der Stein also mitten im Nirgendwo bewegt, aber nur so lange, bis keine Wände mehr um ihn herum sind. Der Code kann mit g ++ --std = c ++ 0x mit g ++ Version 4.4.3 oder neuer kompiliert werden. Es ist nicht möglich, jede Bewegung nur einmal auszuführen, da es Karten geben kann, bei denen ein Stein mehrmals über dasselbe Feld bewegt werden muss. Ansonsten könnte ich viel Speicher sparen. Um auch Karten wie Karte 3 rechtzeitig zu lösen, ignoriert der Algorithmus alle Steine, die herumlaufen können ... Auf Karte 3 wird der Stein also mitten im Nirgendwo bewegt, aber nur so lange, bis keine Wände mehr um ihn herum sind. Der Code kann mit g ++ --std = c ++ 0x mit g ++ Version 4.4.3 oder neuer kompiliert werden. Es ist nicht möglich, jede Bewegung nur einmal auszuführen, da es Karten geben kann, bei denen ein Stein mehrmals über dasselbe Feld bewegt werden muss. Ansonsten könnte ich viel Speicher sparen. Um auch Karten wie Karte 3 rechtzeitig zu lösen, ignoriert der Algorithmus alle Steine, die herumlaufen können ... Auf Karte 3 wird der Stein also mitten im Nirgendwo bewegt, aber nur so lange, bis keine Wände mehr um ihn herum sind. Der Code kann mit g ++ --std = c ++ 0x mit g ++ Version 4.4.3 oder neuer kompiliert werden. aber nur bis es keine Mauern mehr gibt. Der Code kann mit g ++ --std = c ++ 0x mit g ++ Version 4.4.3 oder neuer kompiliert werden. aber nur bis es keine Mauern mehr gibt. Der Code kann mit g ++ --std = c ++ 0x mit g ++ Version 4.4.3 oder neuer kompiliert werden.
Bearbeiten: Das Programm nimmt seine Eingabe von stdin entgegen und ignoriert die erste Zeile, die die Größe der Karte enthält. Es wird überprüft, ob nur zulässige Zeichen in der Karte verwendet werden, es wird jedoch nicht überprüft, ob nur ein Indiana Jones und eine Schatztruhe vorhanden sind. Es ist also möglich, mehr als eine Bewegung zu platzieren, und die geringste Bewegung, die erforderlich ist, um eine der Truhen zu erreichen, wird auf Standard gedruckt. Ungültige Zeichen in der Karte werden übersprungen und das Programm versucht, die geringste Anzahl von Zügen für die resultierende Karte zu berechnen. Die Berechnung startet, wenn stdin geschlossen ist (auf meinem System Strg + d).
quelle