Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Wegfindung ohne Weg - z.B. Algorithmus zum Lösen von Unblock Me Puzzles
deerhunter
myCSharp.de - Member



Dabei seit:
Beiträge: 91

Themenstarter:

Wegfindung ohne Weg - z.B. Algorithmus zum Lösen von Unblock Me Puzzles

beantworten | zitieren | melden

Guten Abend!

Geht es euch auch so, dass ihr manchmal ein Denkspiel spielt und dabei unweigerlich darüber nachdenken müsst, wie man das wohl programmatisch lösen könnte?

So erging es mir letztens beim Spiel Unblock Me auf dem iPhone.
siehe Bild im Anhang bzw. Video (in schlechter Qualität) hier

Habt ihr eine Idee, wie man dieses Problem mit Hilfe eines Algorithmus angehen könnte? Ich könnte mir gut vorstellen, dass sich hierfür Dijkstra oder A* eignen. Mir fallen allerdings keine geeigneten Heuristiken ein, um die Kosten zu schätzen, die zum Ziel führen. Was sagt ihr dazu?

Ich würde mich über ein paar Anregungen von euch freuen. Leider kann ich nicht versprechen, zeitnah zu antworten, da ich gerade beruflich viel um die Ohren habe und bald im Urlaub bin.

VG, Florian
Attachments
private Nachricht | Beiträge des Benutzers
gfoidl
myCSharp.de - Team

Avatar #avatar-2894.jpg


Dabei seit:
Beiträge: 6.860
Herkunft: Waidring

beantworten | zitieren | melden

Hallo deerhunter,

unter dem "Originalnamen" Rush Hour findest du mehr als genug Lösungsmöglichkeiten -algorithmen.

Im Prinzip ist es eine Graphen-Suche wo die Kanten die möglichen Züge und die Knoten der Zustand vom "Spielbrett" ist. Wie das auf zB A* angewandt werden kann entnimm obigen Link oder allen anderen Alogrithmen zur Puzzle-Lösung.


mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"
private Nachricht | Beiträge des Benutzers
deerhunter
myCSharp.de - Member



Dabei seit:
Beiträge: 91

Themenstarter:

beantworten | zitieren | melden

Hallo gfoidl!

Vielen Dank für diese Information. Das ist glaube ich genau das, was ich gesucht habe.

Gute Nacht!
private Nachricht | Beiträge des Benutzers
can320
myCSharp.de - Member



Dabei seit:
Beiträge: 151

beantworten | zitieren | melden

Zitat von deerhunter
Geht es euch auch so, dass ihr manchmal ein Denkspiel spielt und dabei unweigerlich darüber nachdenken müsst, wie man das wohl programmatisch lösen könnte?

Eindeutig -> nein
private Nachricht | Beiträge des Benutzers

Moderationshinweis von gfoidl (15.07.2011 - 00:11)

Auch wenn danach gefragt wurde: bitte nicht beantworten. Versteht es als rhetorische Frage. Danke.

solick
myCSharp.de - Member



Dabei seit:
Beiträge: 56

beantworten | zitieren | melden

Eine Möglichkeit wäre, mit logischer Programmierung (z.B. Prolog zu arbeiten).

Dort beschreibst Du die Fakten und Regeln und durch Backtracking wird dann der Lösungsraum durchsucht. Ich habe mal ein Beispiel gesehen, wie das Spiel die Türme von Hanoi damit gelöst wurde.

Grüße solick
private Nachricht | Beiträge des Benutzers
gfoidl
myCSharp.de - Team

Avatar #avatar-2894.jpg


Dabei seit:
Beiträge: 6.860
Herkunft: Waidring

beantworten | zitieren | melden

Hallo solick,
Zitat
Ich habe mal ein Beispiel gesehen, wie das Spiel die Türme von Hanoi damit gelöst wurde.
Das ist aber kein gutes Plädoyer für logische Programmiersprachen. Die Türme von Hanoi wurden wohl schon mit jeder Programmiersprache gelöst. :-)

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

Hallo gfoidl,
Zitat
Die Türme von Hanoi wurden wohl schon mit jeder Programmiersprache gelöst. :-)
klar, der Unterschied bei Prolog ist aber, dass man nur die Regeln des Spiels (und die Ausgangslage) beschreibt. Das "Programm" ist also rein deklarativ. Man muss nicht implementieren, wie man Türme von Hanoi löst. Man ruft dann das Programm mit der gewünschten Endstellung als Parameter auf und Prolog sucht dann selber den Lösungsweg. Mit anderen Worten: Das Backtracking steht nicht im Programm, sondern ist wesentlicher Teil des Prolog-Interpreters. Deshalb ist Prolog keine schlechte Wahl, wenn es um Probleme geht, die Backtracking erfordern. Das Backtracking muss man dann nicht ausprogrammieren, sondern bekommt es quasi vom Interpreter geschenkt.

Ob sich allerdings der Aufwand lohnt, wenn C# schon kann, aber Prolog erst lernen müsste und wenn man nur ein bestimmtes (Backtracking-)Problem lösen will, steht auf einen anderen Blatt.

herbivore
private Nachricht | Beiträge des Benutzers