Aus Labyrinth fliehen

[CyborgBeta]

Nabend... Gibt es einen (einfachen, prozeduralen und iterativen) Algorithmus, um immer den Ausgang aus einem Labyrinth zu finden, ohne sich dabei den gelaufenen Weg zu merken? Labyrinth: Quadratisches Gitternetz beliebiger Größe. Erlaubte Aktionen: Vor, zurück, 90° links oder 90° rechts, Ausgang gefunden ja/nein. Nicht erlaubte Aktionen: Orientierung/ Position erfragen. Needs: Deterministisch, endlich, anhaltend, optimal (nach Möglichkeit), also zyklen- und kreisfrei. Falls nicht erfüllbar: Probabilistischer Polynomialzeitalgorithmus gesucht.

 

[Sahit]

@CyborgBeta Darüber gibts sogar nen Wiki Artikel https://de.wikipedia.org/wiki/Lösungsalgorithmen_für_Irrgärten

 

[BeBur]

So viele tolle Fachbegriffe und gestochene Formulierungen, aber hast du mal auf Wikipedia geschaut?

 

[M-X]

Hausaufgaben ?

 

[BeBur]

Hausaufgaben ?

Dafür ist imHo die Beschreibung zu wirr.

 

[CyborgBeta]

@CyborgBeta Darüber gibts sogar nen Wiki Artikel https://de.wikipedia.org/wiki/Lösungsalgorithmen_für_Irrgärten

Dabei gibt es Algorithmen, die einer in einem Irrgarten gefangenen Person ins Freie helfen können, ohne dass sie etwas über den Irrgarten weiß: die zufällige Wegwahl, die Rechte-Hand-Methode, der Pledge-Algorithmus und der Trémaux-Algorithmus

Das klingt tatsächlich schon mal vielversprechend... dann muss ich nur noch herausfinden, welche davon "ohne Weg-Gedächtnis" wären und in welcher Zeit die laufen.

Ergänzung (18. Dezember 2022)

Hausaufgaben ?

Nein, hatte Professor nur mal mündlich als Denksportaufgabe in einer Vorlesung als Einstieg gegeben. (Ohne Punkte dafür)

 

[BeBur]

Schreib gerne hier rein, wenn du was hast, es übersteigt gerade meine Fantasie, wie das gehen soll wenn der Irrgarten nicht gerade frei von Zyklen ist, aber deinen probabilistischen Polynomialzeitalgorithmus solltest du eigentlich irgendwo finden.

 

[Gnah]

Nein, hatte Professor nur mal mündlich als Denksportaufgabe in einer Vorlesung als Einstieg gegeben. (Ohne Punkte dafür)

Na wenn dein erster Reflex bei ner Denksportaufgabe darin besteht nicht zu denken sondern andere zu fragen wird das sicher was mit dem Studium.

 

[Maviapril2]

Entweder immer nach rechts laufen oder immer nach links laufen. Damit kommt man immer ans Ziel ohne sich etwas merken zu müssen

 

[CyborgBeta]

Zugegeben, ich hab das ungenau formuliert, denn der Ausgang kann auch "in der Mitte" sein... Und das Subjekt kann auch merken, wenn es gegen eine Wand läuft.

Na wenn dein erster Reflex bei ner Denksportaufgabe darin besteht nicht zu denken sondern andere zu fragen wird das sicher was mit dem Studium

Liegt schon länger zurück, und es gab, wie erwähnt, keine Punkte dafür.

Hm, scheint so, als wenn die Anfänge dazu bis zur Antike bzw. vordynastischen Zeit zurückreichen...

Wahrscheinlich alles alter Käse.

 

[Bumba-Bobby]

an der linken wand eine Markierung mit Kreide setzen und nur dieser wand folgen egal wohin sie geht. Wenn an der Kreidenmarkierung wieder angekommen, ist diese Wand ein Zyklus/Kreis. In diesem Fall die Wand wechseln (auf die andere Seite gehen, viele Seiten sinds glaub nicht außer man startet an einer kreuzung ), Markierung setzen und dieser anderen Wand strikt auch um ecken herum folgen, auch wenn diese vermeintlich an der sackgassenwand entlang führt.

 

[BeBur]

Hm, scheint so, als wenn die Anfänge dazu bis zur Antike bzw. vordynastischen Zeit zurückreichen...

Ja sicher, was auch sonst. Graphentheorie andererseits ist noch nicht ganz so alt.
Ich finde aber die Frage legitim, wie man in einem Labyrinth mit n Abzweigungen und k Zyklen am besten vorgeht. [Natürlich weiterhin ohne das man sich den zurück gelegten Weg merken darf]

Das erste woran man denkt ist 'die meiste Zeit' der simplen Strategie zu folgen immer rechts abzubiegen, aber manchmal dann stattdessen links-rechts in der Hoffnung, dass man das genau an der Stelle tut die einen aus dem Zyklus raus holt.

 

[Corpus Delicti]

Ich denke da zuerst an: Backtracking.

Kurz und knackig rekrusiv programmierbar.

 

[BeBur]

Ich denke da zuerst an: Backtracking.

Dabei speicherst du Informationen über bereits besuchte Pfade.

 

[Maviapril2]

Spricht etwas gegen die von mir genannte Lösung? Die beinhaltet, dass man sich beim Stoßen auf eine Wand natürlich umdreht. Würde zumindest das Problem lösen, oder nicht?

 

[Piktogramm]

@Maviapril2
Umzudrehen bei einer Sackgasse und immer nur in eine Richtung abzubiegen, sorgt für Probleme. Mit einer stumpfen 180° Wende würde man so ja den bereits gelaufenen (aber nicht gespeicherten Weg) wieder zurück laufen, bis zur nächsten Sackgasse.
Der Trick ist ähnlich, aber eben auch kein "immer nur in eine Richtung abbiegen"

Klingt mir auch zu sehr nach Hausaufgabe, der wird es nicht konkreter

 

[BeBur]

Würde zumindest das Problem lösen, oder nicht?

Siehe den Wikipedia Artikel dazu: https://de.wikipedia.org/wiki/Lösungsalgorithmen_für_Irrgärten#Rechte-Hand-Methode

 

[florian.]

einfach immer einen zufälligen weg nehmen.
Wir haben doch rechenleistung ohne ende, dauert auch nur 0,1s zum berechnen

 

[HITCHER_I]

Ohne sich den gelaufenen Weg zu merken?
Bei einem solchen Computerprogramm zeichnet man normalerweise den gelaufenen Weg im Labyrinth ein als Lösung.

Computerphile auf youtube hat ein solches Programm erklärt.

 

[CyborgBeta]

Danke, gelegentlich zufällig die Richtung zu wechseln, zum Beispiel alle 10 Schritte, also ein semi-randomisierter Ansatz, scheint mir eine kluge Wahl zu sein... Dadurch sollten in vertretbarer Zeit alle Felder erreicht werden, und somit auch der Ausgang gefunden werden.

Wäre nur die Frage, wie viele Schritte dann bei einem i x j=n Labyrinth gebraucht werden. Also was dabei optimale Parameter wären.

Und ja, beim Backtracking wird sich a) implizit der Weg gemerkt (Call-Stack) und b) ist Backtracking nicht in allen Programmiersprachen möglich; also, es gibt Compiler, die Backtracking nicht erlauben (weil zum Beispiel der Speicher des Geräts sehr klein ist).

Schönen Advent euch!