Labyrinth - Lösungsalgorithmen

M

marcotesoalli

0
Hallo, ich suche spezielle Lösungsalgorithmen für Labyrinthe

Im Speziellen geht es nicht nur um einfache Labyrinthe, sondern um beliebige (d.h. ich habe eine "Figur", die sich nach vorne, links, rechts bewegen kann, sowie Zeichen auf den Boden schreiben, diese auch auslesen und je nachdem andere Regeln anwenden. Des Weiteren kann ich ähnlich bei einer Turingmaschine verschiedene Zustände annehmen)
Die Figur soll alle Felder in einem Labyrinth besuchen können (die Gänge im Labyrinth können beliebig breit sein, d.h. es kann auch "Plätze" geben)

Ich bin mir ziemlich sicher, dass ich schon mal von Lösungsalgorithmen für solche Labyrinthe gehört habe, mir fällt jetzt aber der Name nicht mehr ein.
Kann mir wer ein paar Stichworte liefern, nach was genau ich suchen muss?

greets Marco
 
Es reicht doch in der Regel einfach eine Breiten- oder Tiefensuche zu machen um den Ausgang zu finden bzw zu schauen ob alles besuchbar ist(das geht dann auch noch damit, obwohl es bessere Möglichkeiten gibt...).
Je nachdem wie mächtig deine Figur ist muss man das möglicherweise einfach entsprechend abbilden.

Ansonsten schon mal gegoogelt?
Lösungsalgorithmen für Irrgärten
 
das was du suchst sind routing algorithmen... (oder förmlich: Algorithmen zur Suche von Pfaden auf Graphen)

Wiki Kategorie:Graphsuchalgorithmus

deine karte oder das labyrinth wird dabei in einen graphen überführt...

beispielsweise werden nur betretbare felder betrachtet und diese werden zu knoten des graphen ... sind 2 felder benachbart, so dass man von einem auf das andere gehen kann, wird zwischen den zugehörigen knoten eine kante in den graphen gesetzt ...

fertig ist der graph...
 
Der (wenn auch nicht gerade effizienteste) "Klassiker" wäre wohl Backtracking:
Annahme: Positionen sind 2D Koordinaten (x,y)
Code: 
solver(start):
 if solve(start, start):
    print "yea!"
 else:
    print "there is no solution! :("

solve(pos : 2d, visited : set of 2d):
 if pos == finish:
    return True
 if is_a_wall_or_invalid(pos) or pos in visited:
    return False

 for next in [(0,1),(0,-1),(1,0),(-1,0)]
    if not solve(pos + next, visited \/ pos):
       continue
    else: return True
  return False
So in etwa müsste es gehen.
Das dürfte sich auch relativ einfach überführen lassen:
Bei einem Schritt setzt z.B Zeichen "v" für visited, die Richtung, aus der man kam sowie die aktuelle gewählte nächste Schrittrichtung.
Kommt man in eine Richtung nicht weiter, wird zuerst nachgeschaut ob noch andere Richtungen ausprobiert werden können(Markierung für nächste Schrittrichtung) - wenn nicht, entfernt man alle Markierungen und macht einen Schritt zurück (Markierung für die Richtung, aus der man kam).

Edit: das wäre dann eine Tiefensuche. Die Laufzeit ist natürlich "unter aller Sau" - exponentiell.
Imho wäre eine Umsetzung der itertativen Tiefensuche oder der Breitensuche hier schon ausreichen (auch wenn man sich bei der Überführung wohl mehr Gedanken machen müsste ;))
 
Außerdem sei angemerkt, dass sich diese Algorithmen *wunderbar* parallelisieren lassen. Gibts verschiedene Ansätze für, am einfachsten dürfte es per fork on branch sein, auch wenn dann die Workload für jeden fork stark variieren kann...

Wenn dich das interessiert, kannste dir mal Computerschach anschauen, da wird DFS seit Ewigkeiten parallelisiert...
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben