Aus Labyrinth fliehen

[striker159]

Kurze Amerkung zu b): Man muss backtracking nicht rekursiv implementieren. Das geht auch ganz einfach iterativ, wenn man sich die Konfigurationen manuell abspeichert.

 

[Piktogramm]

Man könnte einen deterministischen Algorithmus implementieren, der im präzise abschätzbarem Intervall von {min, max} garantiert zum gewünschtem Ergebnis kommt, oder

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...

Wirklich nachgedacht hast du nicht oder? Stell deinem Algorithmus bzw. Ansatz im Kopf einfach mal simpelste Testfälle. In einem Labyrinth wäre das Imho: Eine lange (gerade) Passage, eine simple Abfolge von Kreuzungen, das Behandeln von Sackgassen. Danach eine Kombination aus diesen (also quasi ein mini Labyrinth). Sowas sollte ein Algo zuverlässig bewältigen können. Dein Ansatz mit Zufall:
Es werde eine lange, gerade Passage durchlaufen, dabei ist n die Anzahl an Schritten, zu der zufällig die Richtung geändert wird. x sei die Länge der Passage und es ist zu prüfen was bei x<n; x=n und x>>n (hint: x geht gegen unendlich) passiert.

Ernsthaft, geh es es im Kopf durch und überschlage mal mit Bierdeckelstatistik, wie erfolgreich der Ansatz da sein kann!

 

[BeBur]

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.

Die Kantenlängen des Labyrinthes sind irrelevant. Wie du dem Wikipedia Artikel entnehmen kannst lässt sich ein Labyrinth als ein ungerichteter Graphen beschreiben. Meine Erfahrungen mit Graphen sind begrenzt, aber ich gehe davon aus, dass der Ansatz darin besteht, den Graphen zusammen mit der angedachten Lösungsstrategie als Markov-Kette zu kodieren. Diese wird einen stationären Zustand (steady state distribition) einnehmen, da du vom Ziel aus nie mehr raus gehen wirst.
Damit kannst du dann die entsprechenden Fragen auch korrekt formulieren und die Antworten ausrechnen z.B.:

1. Wie viele Schritte musst du machen, damit du mit einer Wahrscheinlichkeit von mindestens 95% das Ziel erreichst? Oder:
2. Wie hoch ist die Wahrscheinlichkeit das Ziel innerhalb von 100 Schritten zu erreichen?

Lässt sich bestimmt irgendwie verallgemeinern, ich weiß grad aber spontan nicht wie.

Ist sicherlich keine schlechte Feiertagsbeschäftigung.

Man könnte einen deterministischen Algorithmus implementieren, der im präzise abschätzbarem Intervall von {min, max} garantiert zum gewünschtem Ergebnis kommt

Hinweis: Viele haben den ersten Satz nicht richtig gelesen:

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?

Hervorhebung durch mich. Ebenfalls nicht erlaubt:

Nicht erlaubte Aktionen: Orientierung/ Position erfragen.

 

[CyborgBeta]

Kurze Amerkung zu b): Man muss backtracking nicht rekursiv implementieren. Das geht auch ganz einfach iterativ, wenn man sich die Konfigurationen manuell abspeichert.

Jap, es sei denn, es gibt in der Sprache auch keine dynamischen Strukturen bzw. Speicher/Behälter...

 

[Piktogramm]

Hinweis: Viele haben den ersten Satz nicht richtig gelesen:

Viele haben eben jene Aufgaben in ihrem Grundlagen Informatik, Algorithmik 1, Programmieren 1 oder ähnlichen Kursen/Fächern gelöst...

Zudem, wenn wir einfach mal pedantisch sind, das Merken der abgelaufenen Anzahl an Schritten ist ja bereits ein Speichern eines Attributes des abgelaufenen Weges. Bei Krümelkackern, wäre die Lösung also bereits laut Regel unzulässig.

Wenn das ganze locker gesehen wird, bleibt bei einem Algorithmus mit randomisiertem Richtungswechsel immer noch die Betrachtung von x>>n wobei x die mögliche Weglänge im Labyrinth ist und n die Schrittlänge bis zur Randomisierung der Richtung. Allein wenn ich da im Kopf eine Gerade baue und einen entsprechenden Algo die Gerade abwandern lasse bekommt mit bei der Überschlagsrechnung für das Laufzeitverhalten schon eine grobe Idee wie "gut" der Ansatz ist.
Einfach mal selber machen

PS: Vor allem, hier wurden die Lösungen schon verlinkt -.-

 

[BeBur]

Zudem, wenn wir einfach mal pedantisch sind, das Merken der abgelaufenen Anzahl an Schritten ist ja bereits ein Speichern eines Attributes des abgelaufenen Weges.

Nein, weil das macht nicht der Lösungsalgorithmus selber, das geschieht außerhalb, wenn man zufällig durch das Labyrinth läuft, dann kann ich mir das zwar notieren, das ist aber nicht Teil der Lösungsstrategie.

Ich habe nochmal bisschen recherchiert und wenn man über ein unbekanntes Labyrinth/Graph spricht, dann gibt es spannende Erkenntnisse zu solchen Fragen im Bereich des "Random Walk". Die Frage wie lange es dauert das Labyrinth zu lösen scheint mir z.B. recht nah an dem "Speed of a random walk" zu sein, siehe z.B. hier oder hier. Es gibt auch biased random walk das geht dann in die Richtung von alternativen Lösungsstrategien.
Das scheint sich jedoch alles auf Bäume zu beziehen, zu allgemeineren Graphenstrukturen habe ich nichts gefunden.

Wäre mir persönlich etwas zu theoretisch für meine Freizeitgestaltung, aber konkrete Labyrinthe samplen und dann mit Markov-Ketten Durchschnittswerte zu berechnen und zu sehen, welchen Einfluss gewisse Paramter bei der Generierung des Labyrinthes haben klingt recht spannend.

 

[Piktogramm]

Nein, weil das macht nicht der Lösungsalgorithmus selber, das geschieht außerhalb, wenn man zufällig durch das Labyrinth läuft, dann kann ich mir das zwar notieren, das ist aber nicht Teil der Lösungsstrategie.

Ich befürchte ich kann dir an der Stelle nicht folgen. Hättest du bitte mal einen Ansatz Pseudocode, der nach n Schritten randomisiert, ohne n selbst zu verwenden?!

 

[BeBur]

nach n Schritten randomisiert

Achso, jetzt verstehe ich dich, mir war nicht klar, dass du dich in dem Absatz darauf beziehst. In dem Fall stimme ich dir zu.

 

[CyborgBeta]

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

Bei manchen Antworten fragt man sich schon... ob der Antwortende schon mal eine Uni von innen gesehen hat.

 

[CyborgBeta]

Würde sich viel ändern, seien die Anforderungen anders, und die Größe (Dimensionen) des Labyrinths sowie die Anzahl der gegangenen Schritte bekannt?

 

[Piktogramm]

Ein Algorithmus sollte grundlegend zu einer Lösung kommen können, auch wenn die Größe des Problems variiert. Die reelle Implementierung läuft dann natürlich gegen Laufzeit- und Speicherbeschränkungen.

Und wie viel sich ändert, kommt immer drauf an wie viel sich von den Anforderungen ändert. Ob sich konkret etwas ändert, wenn die Anzahl der gegangenen Schritte bekannt ist. Wieso stellst du da nicht wenigstens mal deine eigenen Gedanken zur Diskussion. Die Meisten hier im Thread haben schon mehr Gedanken dargelegt als du als TE..

 

[CyborgBeta]

Na gut, hier wäre mein "naiver" randomisierter Ansatz in Pseudocode:

c ← 0;

While True {
    If vornExit() {
        Exit;
    }
    If c == 10 {
        c ← 0;
        richtung ← zufall(0, 2);
        If richtung == 0 {
            geheLinks();
            If Not vornFrei() {
                geheLinks();
                geheLinks();
                If Not vornFrei() {
                    geheLinks();
                }
            }
        } Else {
            geheRechts();
            If Not vornFrei() {
                geheRechts();
                geheRechts();
                If Not vornFrei() {
                    geheRechts();
                }
            }
        }
    }
    While Not vornFrei() {
        geheLinks();
    }
    c ← c+1;
    geheVor();
}

 

[Iqra]

Hm? Lösungsansätze gibt es doch, auch hier im Thread verlinkt. Ich will nicht sagen, daß das Problem ein triviales ist... aber es ist zumindest gut erforscht. So in etwa wie "denk dir ne Zahl zwischen 1 und 1000, wieviele fragen brauchst du mindestens um die richtige Zahl zu ermitteln?" .

Nein, egal ob als Implementierung für den PC oder fürs wahre Leben: im Labyrinth herumsuchen ist nicht der richtige Ansatz.

Bei manchen Antworten fragt man sich schon... ob der Antwortende schon mal eine Uni von innen gesehen hat.

Yeah, well, nach dem LEsen des Threads will ich das definitiv nicht mehr. Anscheinend lernt man dort nix mehr. Hoffe mal daß das nur die eine Uni ist und nicht exemplarisch. 🤔

 

[titanskin]

Ja... der Zufall ist so eine Sache. Überlege dir ob dein Verfahren in allen Problem Instanzen (= Irrgärten) determiniert, d.h. überhaupt das Ende findet, wenn du deinen Randomisierer bestimmen könntest. Diese Aussage bei deinem Vorgehen ist schon ordentlich schwer zu beantworten.

Ohne sich etwas zu merken und Polygonen mit Löchern/Hosen gegeben zu haben, ist es nicht möglich ein Verfahren zu entwickeln, welches immer hält.
Beweise dies und du bist schon ganz gut dabei!

 

[BeBur]

So in etwa wie "denk dir ne Zahl zwischen 1 und 1000, wieviele fragen brauchst du mindestens um die richtige Zahl zu ermitteln?" .

Ganz und gar nicht so in etwa. Wie ich schon dargelegt habe, ist die Fragestellung weit davon entfernt, trivial zu sein und jemand ohne zufällig passende Spezialkenntnisse in Graphentheorie wird sich schwer tun auch nur simple Aussagen über ein zufälliges Durchlaufen des Labyrinthes herzuleiten. Die Antwort auf deine Frage lautet übrigens: "Mindestens eine einzelne Frage", nur falls du etwas anderes gedacht haben solltest.

Die Problematik und Tragweite der Fragestellung wird ganz im Gegenteil hier weit unterschätzt, zum Teil weil die Aufgabenstellung (erster Satz) nicht richtig gelesen wird.

Ich finde das Thema aber nicht unspannend und vielleicht liege ich ja ganz falsch, also wenn du mir vielleicht die folgende simple Frage beantworten kannst:

Gegeben sei ein Labyrinth der Größe 12x12. Es gibt keine Kreise/Zyklen darin und jedes Feld in dem Labyrinth ist von der Startposition aus erreichbar. Es gibt genau ein Ziel. Ohne mir zu merken wo ich langlaufe gehe ich an jeder Kreuzung in eine zufällige Richtung. Wie lange muss ich im Durchschnitt laufen um ans Ziel zu gelangen?
Ggf. fehlende Angaben (Anzahl der Kreuzungen u.ä.) können selber in einem sinnvollen Rahmen festgelegt werden.

Ohne sich etwas zu merken und Polygonen mit Löchern/Hosen gegeben zu haben, ist es nicht möglich ein Verfahren zu entwickeln, welches immer hält.

Ich will meinen für jede vorgegebene Wahrscheinlich ϵ gibt es einen Zeitpunkt t für den gilt, dass die Wahrscheinlichkeit, dass der Algorithmus angehalten hat kleiner als ϵ ist. Das ist so viel wie man bei zufallsbasierten Verfahren prinzipiell nur erreichen kann.

Überlege dir ob dein Verfahren in allen Problem Instanzen (= Irrgärten) determiniert, d.h. überhaupt das Ende findet, wenn du deinen Randomisierer bestimmen könntest. Diese Aussage bei deinem Vorgehen ist schon ordentlich schwer zu beantworten.

Das vermute ich ist vergleichsweise einfach zu beweisen, denn es reicht zu beweisen, dass das Verfahren jede Stelle eines Labyrinthes erreichen kann.

 

[Piktogramm]

Na gut, hier wäre mein "naiver" randomisierter Ansatz in Pseudocode:

Und jetzt noch die Betrachtung, wie erfolgreich das Ganze wenn gilt: x sei die mittlere, zu laufende Strecke (im Zweifelsfall schätzen) und es gilt x >>10

Und ich muss zugeben, ich habe selber einen Denkfehler gehabt. Es gibt Labyrinthe, bei denen die simpelsten Lösungsansätze dazu führen, dass im Kreis gelaufen wird. Da gibt es einen randomisierten Ansatz, der an der Stelle besser funktioniert, der randomisiert aber nicht(!) nach gelaufener Wegstrecke.

 

[Iqra]

Ganz und gar nicht so in etwa.

Heh, okay, Analogie schlecht gewählt. 😅 ich meinte nur, Probleme wie dieses erfordern keine besondere Forschung insbesondere durch Studienanfänger. Natürlich habe ich grad eher das Gefühl von … wie nenne ich es… wissenschaftlicher Faulheit? Also einen Mangel an Wissenwollen. Und das ist für studis glaub ich eine sehr unglückliche Eigenschaft, bis zum Punkt wo ich frage, ist Studium wirklich der beste Weg?

Aber das ist nur meine Interpretation der Sachlage. Ohne Anspruch auf Richtigkeit.

 

[BeBur]

Also einen Mangel an Wissenwollen. Und das ist für studis glaub ich eine sehr unglückliche Eigenschaft, bis zum Punkt wo ich frage, ist Studium wirklich der beste Weg?

Abgesehen vom eigentlichen Thema finde ich es krass, wie weit du dich aus dem Fenster lehnst und einfach mal nach ein paar Beiträgen die Eignung zum Studium in Frage stellst von jemandem der sich hier in seiner Freizeit austauscht zu einem Thema mit dem er sich freiwillig gedanklich auseinander setzt.

 

[CyborgBeta]

Da gibt es einen randomisierten Ansatz, der an der Stelle besser funktioniert, der randomisiert aber nicht(!) nach gelaufener Wegstrecke.

Das stimmt. Man betrachte mal folgendes Labyrinth:

Der Hamster würde das Korn=Ausgang nicht finden, weil er nicht aus dem unteren Gang herauskommen kann.


Damit würde es jedoch funktionieren:

void main() {
    int r = algorithm_1(5, 15);
    schreib("" + r);
}

int algorithm_1(int min, int max) {
    int r = 0;
    int c = 0;
    while (true) {
        if (kornDa()) return r;
        if (c >= 10) {
            c = (int) (Math.random() * (max-min)) + min;
            int z = (int) (Math.random() * 2);
            if (z == 0) {
                linksUm();
                linksUm();
            }
            linksUm();
            if (!vornFrei()) {
                linksUm();
                linksUm();
                if (!vornFrei()) {
                    linksUm();
                }
            }
        }
        while (!vornFrei()) linksUm();
        r++;
        c++;
        vor();
    }
}

Ich denke, ist nur die Frage, wie man min, max wählt...

Ergänzung (19. Dezember 2022)

Hier noch der Link zum Hamsterchen: https://www.java-hamster-modell.de/simulator.html

 

[Piktogramm]

Das wäre zwei der wichtigsten Randbedingungen überhaupt, dass der Ausgang des Labyrinths nicht an einer Außenkante liegt, sonder mittig in einem größerem Feld und, dass es eben diese Felder überhaupt gibt.
Um solche Felder abzuschreiten, ist die Anwendung von Zufall wirklich empfehlenswert. Wobei ich da auch keine Abhängigkeit nach zurückgelegter Strecke empfehlen würde. Mein Ansatz:

• Einmal Logik bauen, die bei Gängen mit einer Breite von 1 diese Gänge abschreitet und zufällig an Kreuzungen verzweigt.
• Wird festgestellt, dass ein Feld beschritten wird, dann wird dieses systematisch abgerastert. Zufällig wird bestimmt, ob das Feld mit einem initialem Rechts- oder Linksabbiegen durchschritten wird.
  • Nach dem Abrastern Außenkanten des Feldes ablaufen bis Ausgang des Feldes gefunden wurde. Zufällig bestimmen ob der Ausgang genutzt wird.

Ein anderer Ansatz wäre, simple Staubsogerroboter nachzubauen. Also ein Kantenkuschler, der zufällig entscheidet immer mal wieder Versuche zu unternehmen eine Fläche abzurastern. Wobei da zu empfehlen ist die Anzahl an Schritten bis es zum Rasterversuch kommt in einem sinnvollem Ausmaß zu randomisieren. Wobei sinnvolle Maße so ein Ding ist, weiß der Hamster wie groß das Labyrinth ist? Dann wäre ein sinnvolles maximales Maß für rand(min,max) die längste Kante des Gebildes.

edit: Namen von Variablen, Funktionen, Klassen etc. in Deutsch zu benennen ist mMn schlechter Stil. Die meisten Programmiersprachen lehnen sich an einer natürlichen Sprache an und das ist meist Englisch. Es wäre zu empfehlen, die freie Benennung also auch ans Englische anzulehnen (und etwaige Dokumentation auch in Englisch zu schreiben)