Algorithmus zum Finden der Lösung eines Verschieberätsels
-
Das war keine Kritik meinerseits, sondern vielmehr ein ironischer Kommentar á la "scheinbar einfache Probleme sind viel komplizierter, als man denkt", und das nicht nur für Leute, die sich mit der Materie nicht so auskennen.
Ich denke, das Problem wird nur jemand in seiner Freizeit für lau (=40€) angehen, der ansonsten extrem unterfordert ist (was leider sehr selten vorkommt).
-
Och ich habs nicht so böse aufgenommen, im grunde genommen fühle ich mich wie penny bei the big bang theorie ^^
-
Furble Wurble schrieb:
Ein Paper habe ich dazu gefunden: How to Solve the Torus Puzzle
Na das ist ja schon mal ein vielversprechender Ansatz. Man könnte jetzt eine Nummerierung der Felder raten und den Algorithmus als Black Box draufwerfen. Das wiederholt man so lange, bis der Algorithmus eine hinreichend kurze Sequenz auswirft. Wenn man sich beim Raten der Nummerierung geschickt anstellt, kann ich mir gut vorstellen, dass das praktikabel ist.
-
Hier ist noch ein Paper, das Heuristiken behandelt: http://dl.acm.org/citation.cfm?id=2184526
-
Furble Wurble schrieb:
Ein Paper habe ich dazu gefunden: How to Solve the Torus Puzzle
Das ist nicht dasselbe. Dort sind keine identitätslosen Murmeln vorgegeben, sondern Zahlen. Man weiß also genau welches Feld wo landen muss und kann damit eine bessere Abschätzung vornehmen. Das hilft sicher.
@Topic: Ich würde folgendes vorschlagen. Eine Lösung muss jedes Feld der Eingabe auf ein Feld der Ausgabe verschieben. Die Anzahl der Schritte um ein Feld zu einem Zielfeld zu verschieben ist die Summe aus horizontalem und vertikalem Abstand (Torusstruktur beachten!). Wir suchen nun eine Zuordnung von Quellfeldern zu Zielfeldern, die die Summe all dieser Abstände minimiert, nennen wir diese Summe der Abstände X. In jedem Zug kommen bis zu 9 Felder ihrem eigentlichen Zielort um 1 näher. Eine untere Schranke für die Anzahl der nötigen Schritte ist also X/9. Das benutzt man nun für einen bidirektionalen A*-Algorithmus vom Start vorwärts und vom Ziel rückwärts.
-
Jodocus schrieb:
Edit: @ SeppJ: Na, immernoch für 40€ dabei?
Nach wie vor ist das Problem interessant genug, dass ich es eigentlich fast freiwillig machen würde. Wobei es immer mehr danach aussieht, dass ich vermutlich einfach nicht genug Freizeit hätte, um das in vernünftiger Zeit umzusetzen. Das Rätsel ist schwer.
iwona schrieb:
die frage von mir als unwissende. wieso ist eine beinahe annäherung an das ergebnis nicht praktisch wenn ich noch angenommen 20 züge übrig hätte und das muster so gut wie gelöst ist, kann ja der menschliche verstand den rest machen.
Eine aus den folgenden Gründen offensichtlich nicht gut taugliche, aber naheliegende, Heuristik wäre ja, dass man die Güte einer Stellung anhand der Anzahl übereinstimmender (oder nahezu* übereinstimmender) Pixel bestimmt.
Angenommen die Zielmatrix:### ### ######### ### ### # # # # # # ### ### ######### ### ####und zwischendurch schafft man es irgendwie, folgende Stellung zu erzeugen:
### ### ######### #### ### # # # # # # ### ### ######### ### ###Übereinstimmung fast überall. Die Heuristik wäre begeistert. Aber um von der einen Stellung zur anderen zu kommen ist nicht einfach. Ein Algorithmus, der in der (zugtechnischen) Nähe einer guten Stellung nach Verbesserungen sucht, würde wohl niemals von der einen Stellung zur anderen kommen, weil die Zwischenstellungen allesamt sehr viel schlechter bewertet würden als die fast perfekte Ausgangsstellung. (Ich habe nicht geprüft, ob diese Stellungen überhaupt ineinander überführbar wären. Dies ist nur ein Beispiel für zwei ähnliche Stellungen, die offensichtlich sehr schwer ineinander zu überführen wären)
*: Es gilt natürlich den Begriff "nahezu" in diesem Zusammenhang zu klären. Auch wenn ich durchaus Vorstellungen dazu hätte, will ich nicht weiter darauf eingehen, weil dieser Beitrag ja ohnehin ein Beispiel bringt, wieso die Technik an sich keine gute Idee sein könnte.
-
Nicht dass ich irgend eine Idee hätte, aber eine Frage dafür: ist die optimale Lösung gesucht, oder nur irgendeine Lösung, oder irgendeine Lösung mit <= N Zügen die aber nicht optimal sein muss?
-
hustbaer schrieb:
Nicht dass ich irgend eine Idee hätte, aber eine Frage dafür: ist die optimale Lösung gesucht, oder nur irgendeine Lösung, oder irgendeine Lösung mit <= N Zügen die aber nicht optimal sein muss?
Soweit ich das verstanden habe, eine Lösung mit <= N Zügen.
Wobei N anscheinend im zweistelligen Bereich ist, die Anzahl möglicher Kombinationen ist daher gigantisch.
-
Jester schrieb:
Furble Wurble schrieb:
Ein Paper habe ich dazu gefunden: How to Solve the Torus Puzzle
Das ist nicht dasselbe. Dort sind keine identitätslosen Murmeln vorgegeben, sondern Zahlen. Man weiß also genau welches Feld wo landen muss und kann damit eine bessere Abschätzung vornehmen.
Du hast recht. Allerdings behandeln die Autoren das Problem als Black-White Variante in Teil 4 der Abhandlung.
Darüberhinaus erleichtern ein paar Stichworte die Suche nach Arbeiten in die richtige Richtung.
Torus/Donut/toroid [sliding] puzzle oder ähnlich.
-
das ist korrekt. du hast nur eine begrenzte anzahl an zügen pro muster diese können aber im wert sich zwischen 1 und 3 zügen jeweils verändern.
also anstatt 45 züge habe ich dann 42 züge aber auch ein anderes geshuffelte feld.
-
ach jetzt war nicht eingeloggt, na gut steht ja oben was ich meinte. doch um das hier nochmal aufzugreifen
Eine aus den folgenden Gründen offensichtlich nicht gut taugliche, aber naheliegende, Heuristik wäre ja, dass man die Güte einer Stellung anhand der Anzahl übereinstimmender (oder nahezu* übereinstimmender) Pixel bestimmt.
Angenommen die Zielmatrix:ABCDEFGHI ### ### ######### ### ### # # # # # # ### ### ######### ### ####und zwischendurch schafft man es irgendwie, folgende Stellung zu erzeugen:
ABCDEFGHI ### ### Y ######### X #### ### V # # N # # M # # S ### ### J ######### K ### ### L !"§$%&/()Übereinstimmung fast überall. Die Heuristik wäre begeistert. Aber um von der einen Stellung zur anderen zu kommen ist nicht einfach. Ein Algorithmus, der in der (zugtechnischen) Nähe einer guten Stellung nach Verbesserungen sucht, würde wohl niemals von der einen Stellung zur anderen kommen, weil die Zwischenstellungen allesamt sehr viel schlechter bewertet würden als die fast perfekte Ausgangsstellung. (Ich habe nicht geprüft, ob diese Stellungen überhaupt ineinander überführbar wären. Dies ist nur ein Beispiel für zwei ähnliche Stellungen, die offensichtlich sehr schwer ineinander zu überführen wären)
Es ist aber recht einfach gelöst.
d, d, &, Y, Y, Y, $, F
*nochmal drüber schau* ... so sollte es richtig sein.
Na gut wir verdoppeln das Anfangsgebot. Ich biete nun 80 Euro.
-
iwona schrieb:
Es ist aber recht einfach gelöst.
d, d, &, Y, Y, Y, $, F
*nochmal drüber schau* ... so sollte es richtig sein.
Kann ich nicht nachvollziehen.
Schreib das bitte mal schrittweise auf, mit Zwischenstellungen und so.
-
Wie wäre es, wenn man das Feld als Graph auffassen würde.
Jedes Muster ist ein Knoten, die Nachbarn sind die, die durch diese elementaren Operationen erreichbar sind. Dann könnte man die Nähe mittels einer Abweichung ermitteln und eine AStern Heuristik drauf loslassen. Die liefert das beste Ergebnis, wenn auch die Zeit zur Berechnung ewig dauern könnte.
-
Bleibt "nur" noch, eine passende Abschätzungsfunktion zu formulieren.
-
Also als Matrix aufgefasst würde in der Nähe eine L1 Norm fast schon Sinn ergeben. Dass diese schlecht sein wird ist wohl klar. Man könnte es vielleicht mit einer Art Entropie versuchen. Also intuitiv würde ich als Heuristik Spalten und Zeilenentropie berechnen, und dann den euklidischen Abstand zur Spalten und Zeilenentropie der gesuchten Matrix nehmen. Ist aber nur ein spontaner Schuss ins Blaue.
-
Das Problem irgendwie zu lösen ist denke ich kein Problem, nur das Finden einer guten Lösung.
Man kann jedes Muster durch die Operationen auf eine Grundstruktur zurückführen.
Damit hat man ja schon direkt eine Lösung.
