Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Kombinatorik & Graphentheorie » Optimale Vorgehensweise beim Schiebepuzzle
Autor
Kein bestimmter Bereich Optimale Vorgehensweise beim Schiebepuzzle
vertang
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 10.10.2021
Mitteilungen: 99
  Themenstart: 2022-01-24

Hallo, man kriegt es mit Ausprobieren hin, aber: Was ist eigentlich die optimale Vorgehensweise beim Schiebepuzzle Beispiel: Das https://matheplanet.de/matheplanet/nuke/html/uploads/b/55009_11_555555.png soll zu dem werden https://matheplanet.de/matheplanet/nuke/html/uploads/b/55009_999999.jpg


   Profil
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1388
Wohnort: Koblenz (früher: Berlin)
  Beitrag No.1, eingetragen 2022-01-24

Hi, Meinst du das Puzzle im allgemeinen (nxn) oder speziell die 4x4-Version? Eine optimale Zugfolge bekommt mit einer Breitensuche (wie auch im Artikel erwähnt). Dort steht auch, dass das allgemeine nxn-Problem NP-vollständig ist, also wird es vmtl. keine simple Regel zur Lösungsfindung geben. Man kann aber sicher eine gezieltere Suche auf Basis einer Schätzfunktion (wie beim A*-Algorithmus durchführen). Als Schätzfunktion z.B. die summierte Manhattandistanz der einzelnen Felder zur Zielposition. Was man schnell erkennen kann: ob das Puzzle überhaupt lösbar ist. Durch Vertauschen zweier benachbarter Steine überführt man eine lösbare in eine unlösbare Konfiguration und umgekehrt.


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3731
  Beitrag No.2, eingetragen 2022-01-24

optimal wäre noch zu definieren, schnellste lösung und wenigste züge sind durchaus nicht das selbe ich brauch hier 25 züge für die unterste reihe https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/35059_schiebe1.jpg notation könnte man jeweils das frei feld anführen, also d1;d4;b4;b1;d1...usw nach alter kindermanier würde ich danach die zweitunterste reihe herstellen ohne die unterste nochmal zu verändern und dann nur noch oben das karussel drehen und verbessern bis es passt das geht für die folgenden reihen sicher mit weniger zügen wenn man weiter vorraus verbessert, aber wird unübersichtlicher und eben nicht schneller andrerseits lagen hier die späteren a4; c4 und d4 bis zug 20 schon sehr nahe zu ihrer späteren position unsere masseinheit war "es mit luftanhalten" zu schaffen also wohl in unter ~40sec. und hier hätte ich damit keine chance weil ich die tierkreissymbole nicht gut genug kenne [Die Antwort wurde vor Beitrag No.1 begonnen.]


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3731
  Beitrag No.3, eingetragen 2022-01-24

entgegen dem artikel betrachtete ich bisher das verschieben von mehreren nebeneinanderliegenden steinen als einen zug


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3731
  Beitrag No.4, eingetragen 2022-01-24

erste reihe, um zwei züge verbessert https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/35059_schiebe2.jpg und nochmal zwei besser https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/35059_schiebe3.jpg


   Profil
vertang hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]