Autor |
Beitrag |
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Di 23.12.14 17:33
Hallo,
das nachfolgende Programm ist als Ergänzung zur Adventsrätselaufgabe vom 22.12.2014 gedacht.
Dieses Puzzle wurde erstmals 1878 von Sam Loyd beschrieben und wird daher auch Loyd's 15 genannt.
Es besteht aus 15 Quadraten, welche die Ziffern 1 bis 15 enthalten, die in einem 4 x 4-Quadrat angeordnet sind. Das 16. Feld bleibt frei.
Aufgabe ist es, die 15 zunächst unsortierten Quadrate durch Verschieben jeweils eines Quadrats auf die leere Position numerisch zeilenweise von links nach rechts zu ordnen.
In diesem Programm können auch andere Spielfeldgrößen untersucht werden.
Um die Spielfelder zu mischen, klickt man entweder auf den Schalter "Spielfeld mischen" oder markiert das Feld "Klick und Verschieben tauscht Felder". Im zweiten Fall kann man ein Spielfeld mit der Maus anklicken und an die von Ihnen gewünschte Position verschieben. Wird nach einer solchen Änderung ein Feld rot markiert, so ist das Puzzle nicht lösbar.
Ist das Feld "Mausklick bewegt auf freies Feld" markiert, kann man versuchen, das Puzzle selbst zu lösen.
Außerdem sucht das Programm auch nach einer optimalen Lösung.
Der Lösungsalgorithmus gehört zu den NP-Problemen, deren Laufzeit mit mehr Ausgangsdaten sehr schnell ansteigt. Findet das Programm eine Lösung, wird diese dargestellt und die Schrittfolge in einer Liste angezeigt.
Das Programm basiert auf der Lösung von Gary Darby ( www.delphiforfun.org...ograms/15puzzle.htm). Ich habe nur ein paar Änderungen durchgeführt.
Viel Spaß beim Puzzlen.
Mathematiker
Einloggen, um Attachments anzusehen!
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Di 23.12.14 21:18
Hallo,
ich wollte doch mal wissen, ob der kürzeste Weg gefunden wird.
Es sind ja 16! = 2E13 Anordnungen bei einem 4x4 Feld.Das passt ja in keinen PC rein.
Ich habe dazu 2000 Zufallszüge fürs mischen verwendet.
Dank dem Knopf "Anfangstellung" kann man das ja gut testen.
Bei einer Suchtiefe von -> Züge/Laufzeit ergibt sich folgendes bei mir:
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9:
| 100->134 / 0 s 75-> 90 / 0 s 50-> 82 / 0 s 33-> 66 / 0 s 23-> 62 / 1 s
22-> 54 / 2 s 20-> 54 / 6 s 17-> 54 / 46 s |
Andere "Mischungen" hatten bei Suchtiefe 37 die wenigsten Schritte, immerhin 74. ( 28 ergab 78 Schritte )
Das ist doch ganz gut.
Wenn ich daran denke, das ich bestimmt 172-mal vor mich hin geklickt habe.
Apropos mischen, warum nicht einfach Fisher-Yates-Mischen, wenn man über 100 ( 74 Schritte war bisher das höchste, aber das Bedarf mehr Untersuchungen ) bei Mischen eingibt.
Gruß Horst
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Di 23.12.14 22:18
Hallo,
der Algorithmus von Gary Darby zur Suche nach möglichst wenigen Zügen ist ziemlich gut, aber nicht optimal.
U.a. durch Ralph Udo Gasser wurde nachgewiesen, dass bei jeder Ausgangsstellung maximal 80 Züge notwendig sind. Er gab neun Konfigurationen in "Harnessing Computational Resources for Efficient Exhaustive Search" mit 80 Zügen an. 2 weitere fand Adrian Brüngger und im Juni 2009 mein Kollege Siegfried Beyer fünf weitere derartige Ausgangssitutationen. Diese sind (_ ist das freie Feld):
Zitat: | _ 12 10 13 15 11 14 9 7 8 6 2 4 3 5 1
_ 12 14 13 15 11 9 10 8 3 6 2 4 7 5 1
_ 12 9 13 15 11 10 14 7 8 6 2 4 3 5 1
_ 12 9 13 15 11 10 14 3 7 5 6 4 8 2 1
_ 12 9 13 15 11 10 14 8 3 6 2 4 7 5 1
_ 12 9 13 15 11 10 14 3 7 6 2 4 8 5 1
_ 12 10 13 15 11 9 14 7 3 6 2 4 8 5 1
_ 15 9 13 11 12 10 14 3 7 6 2 4 8 5 1
_ 12 9 13 15 11 14 10 3 8 6 2 4 7 5 1
_ 12 9 13 15 11 10 14 7 8 5 6 4 3 2 1
_ 12 9 13 15 8 10 14 11 7 6 2 4 3 5 1
_ 12 14 13 15 11 9 10 3 7 6 2 4 8 5 1
_ 12 9 13 15 11 10 14 3 7 2 5 4 8 6 1
_ 12 10 13 15 11 14 9 3 7 6 2 4 8 5 1
_ 12 10 13 15 11 14 9 3 7 2 5 4 8 6 1
_ 11 9 13 12 15 10 14 3 7 6 2 4 8 5 1 |
Für die Stellung
findet das Programm minimal 104 bzw. 106 Züge und nicht die 80.
Die kürzeste Zugfolge wäre
Zitat: | 15, 7, 4, 3, 5, 1, 2, 9, 13, 10, 12, 15, 7, 4, 3, 5, 1, 2, 9, 13, 10, 12, 15, 7, 4, 11, 8, 1, 2, 9, 13, 10, 14, 15, 7, 8, 11, 3, 1, 2, 9, 13, 10, 14, 15, 11, 2, 6, 11, 7, 8, 4, 3, 1, 5, 9, 13, 10, 14, 15, 12, 8, 4, 3, 1, 5, 9, 13, 10, 14, 15, 12, 8, 4, 3, 2, 6, 10, 14, 15 |
Beste Grüße
Mathematiker
Einloggen, um Attachments anzusehen!
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Zuletzt bearbeitet von Mathematiker am Fr 26.12.14 19:53, insgesamt 1-mal bearbeitet
Für diesen Beitrag haben gedankt: Horst_H
|
|
gerd8888
Beiträge: 205
Erhaltene Danke: 3
Win7
Delphi 10.1 Starter (kostenlos) Lazarus
|
Verfasst: Mi 24.12.14 15:57
Es gibt 1*2*3 ... *15*16 Möglichkeiten (Leerfeld mit berücksichtigt) das Spielfeld zu bestücken.
Interessant waere vielleicht zu wissen, bei welcher Konstellation, wieviel Schritte max. benötigt werden.
Mit Brute Force langsam die Schrittzahl um 1 erhöhen, würde ein sicheres und das schnellste Vorgehen gewährleisten.
Denn wenn man nur die Zahlen der Reihenfolge anordnet dauert das evt. länger.
Wie sollte man sonst vorghen, wenn einem der Darby Algorithmus nicht ausreicht? Gibt's da noch andere Lösungsmöglichkeiten?
Gerd
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 25.12.14 10:15
Hallo und O Du fröhliche,
Mathematiker hat doch oben mehrere Stellungen in seinem Zitat angegeben.
Man beginnt oben links und macht bei erreichnen des rechten Randes in der Zeile darunter weiter.
Die oberste Stellung ist darunter als 4x4-Bild dargestellt
Wenn den ganzen Beitrag nochmals in Ruhe durchliest, dem Link folgst und nach "Harnessing Computational Resources for Efficient Exhaustive Search" suchst, sind zum Großteil Deine Fragen beantwortet,
80 Züge scheint ein oberes Limit zu sein.
Gruß Horst
Für diesen Beitrag haben gedankt: gerd8888, Mathematiker
|
|
gerd8888
Beiträge: 205
Erhaltene Danke: 3
Win7
Delphi 10.1 Starter (kostenlos) Lazarus
|
Verfasst: Fr 26.12.14 12:57
Diese 80 Schritte, wo Mathematiker mehrere Stellungen angibt, sind also amtlich. Kuerzer wird es nicht gehen!?
Ein Kollege sagte zu mir damals: "Warum das Rad neu erfinden". So ist das bei dem Rätsel letztendlich doch auch?
Eine Frage habe ich noch zu der hashunit. Diese Zeile finde ich immer am interessantesten:
Delphi-Quelltext 1: 2: 3: 4:
| begin result:=1; for i:=1 to length(s) do result:=((result shl 4)+ ord(s[i])) mod maxhash; end; |
Hat Aehnlichkeiten mit dem Elfhash, nur ist obiger kürzer. Ob er auch besser ist?
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14:
| Function elfhash(Const Value: String): Cardinal; Var i: Integer; x: Cardinal; Begin Result := 0; For i := 1 To Length(Value) Do Begin Result := (Result Shl 4) + Ord(Value[i]); x := Result And $F0000000; If (x <> 0) Then Result := Result Xor (x Shr 24); Result := Result And (Not x); End; End; |
Gerd
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Fr 26.12.14 19:49
Hallo,
die Speicherbelastung durch das Programm ist etwas merkwürdig.
Der Speicher wird nicht freigegeben, wohl nur als "deleted" markiert, aber auch nicht vollständig neu benutzt.
Beispielsweise habe ich bei 200.000 Schritten abgebrochen und dann nochmals gemischt und neu suchen lassen.Nach 100.000 Suchschritten nimmt der Speicher wieder zu.
Die entstehende Datenmenge ist gewaltig, da wäre Feinschliff nötig, aber das andere Programm soll ja 2000-fach schneller sein. Das lohnt wohl kaum
Gruß Horst
|
|
Horst_H
Beiträge: 1652
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: So 28.12.14 10:04
Hallo,
auf wikipedia wurde auch dies verlinkt:
Large-Scale Parallel Breadth-First Search
Dort wurden 2004 alle Lösungen zu dem Loyd Puzzle 15 in 30 Tagen gefunden mit Beschreibung der entsprechenden Hardware Probleme.
Interessant wäre, wie lange die vollständige Überprüfung heute mit SSDs dauern würde.
Im Kapitel "Efficient Permutation Encoding" wird die Bestimmung der Nummer einer lexikografischen Permutation in linearer Zeit gezeigt, die nur eine relativ ( n! ) dazu eine sehr kleine Tabelle ( 2^n) braucht.
Das kann man ja als Ausgangspunkt für den Hash-Wert nehmen.
Ein Problem vom vorgestellten Programm ist auch der enorme Speicherbedarf für jeden neuen Knoten, max.85 MB für 2E5 Knoten.
Bei 2 GB war bei mir Schluß.
Gruß Horst
|
|
|