Aus Labyrinth fliehen

[CyborgBeta]

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)

Der Hamster-Simulator ist nicht von mir, jemand anderes hat diese API geschrieben (für Unterrichtszwecke).

Ich hatte den Hamster-Simulator jetzt nur verwendet, weil ich damit am schnellsten das Problem nachstellen konnte.

Staubsauger-Raster-Abtastung klingt super.

 

[Corpus Delicti]

Ja isses!

Den Hamster hab ich zu meiner Schulzeit vor >30 Jahren kennen gelernt, und er lebt immer noch. :-)

 

[CyborgBeta]

Hier noch schnell die rekursive Variante:

void main() {
    backtracking(150);
}

boolean backtracking(int moves) {
    if (kornDa()) {
        return true;
    }
    if (moves == 0) {
        return false;
    }
    if (Math.random() < 0.2) {
        linksUm();

        // links
        if (vornFrei()) {
            vor();
            if (backtracking(moves - 1)) {
                return true;
            }
            linksUm(); linksUm(); vor(); linksUm(); linksUm();
        }
        linksUm(); linksUm();

        // rechts
        if (vornFrei()) {
            vor();
            if (backtracking(moves - 1)) {
                return true;
            }
            linksUm(); linksUm(); vor(); linksUm(); linksUm();
        }
        linksUm();

        // geradeaus
        if (vornFrei()) {
            vor();
            if (backtracking(moves - 1)) {
                return true;
            }
            linksUm(); linksUm(); vor(); linksUm(); linksUm();
        }
    } else {
        // geradeaus
        if (vornFrei()) {
            vor();
            if (backtracking(moves - 1)) {
                return true;
            }
            linksUm(); linksUm(); vor(); linksUm(); linksUm();
        }
        linksUm();

        // links
        if (vornFrei()) {
            vor();
            if (backtracking(moves - 1)) {
                return true;
            }
            linksUm(); linksUm(); vor(); linksUm(); linksUm();
        }
        linksUm(); linksUm();

        // rechts
        if (vornFrei()) {
            vor();
            if (backtracking(moves - 1)) {
                return true;
            }
            linksUm(); linksUm(); vor(); linksUm(); linksUm();
        }
        linksUm();
    }
    return false;
}

Dabei wäre es natürlich interessant zu wissen, wie man 150 und 0.2 wählen muss... moves darf nicht kleiner sein als die minimale Länge zum Ziel...

Edit: Ich hab mir das ausgedacht, das heißt aber nicht, dass es das nicht schon gibt. 😃

 

[CyborgBeta]

-

 

[titanskin]

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:



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.


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

Ich bin mal so frei und antworte, da hier ein wenig was durcheinandergekommen ist, in probilistischen/randomisierten Algorithmen unterscheidet wird meistens zwischen der

• erwartete Laufzeit eines Algorithmus und
• die worst-case Laufzeit eines Algorithmus unterschieden.

Ich spare mir jetzt auf deine weitere Aussage einzugehen. Den Fehler darfst du selbst erkennen.
Für den WC gilt folgendes:
Angenommen wir haben ein Polygon ohne Löcher (*), d.h. ein geschlossenes Labyrinth ohne eingebettete Labirinthe, etc.. Zusätzlich dürfen wir uns nichts merken (), folglich gilt:
Für den WC sieht es so aus, dass sich das ganze auf die binäre Entscheidung an einer Weggabelung zurückführen lässt. Ein Weg ist eine Sackgasse, der andere führt zum Ziel, hinter uns liegt eine Sackgasse. Da wir im WC der Zufall gegen uns Spielt, entscheidet er auf die Sackgasse. Kommen wir allerdings erneut an dieser Gabelung an, wird der Zufall wieder gegen uns spielen und uns wieder in die alte Sackgasse schicken. (***)

Folglich - entgegen deiner Aussage - gilt, dass der Algorithmus nicht halten muss!

Die erwartete Laufzeit ist eine andere und kann dort determinieren. Hier kann das Labirinth als Baum aufgefasst werden und das Ganze wird dadurch geringfügig leichter. Die Laufzeit kann dann in der Anzahl der Wegteilungen/Entscheidungen/Knoten entschieden werden (ist eine schöne Übungsaufgabe).
Es ist immer so etwas wie, ich spiele Tombola und der erwartete Gewinn ist beispielsweise 1€ pro Einsatz, aber Nieten ziehe ich trotzdem .

Folglich determinisitisch ohne was zu merken gibt es das schon sehr schnell gesagte Verfahren "ich laufe an einer Wand entlang bis ich mein Ziel finde".
Bei Polygonen mit Löchern wird meistens eine Farbmarkierung (für jedes Loch) in den Beweisen genutzt um das Problem auf ein Polygon ohne Loch zu reduzieren (mir ist auch kein anderes Beweisschema bekannt). Da die Anzahl der Löcher nicht konstant groß sein muss (wenn doch konstant geht's) und wir immer noch die Speicher Beschränkung haben ist es nicht möglich dort determinisitsch für den WC etwas mit den Restriktionen zu erstellen.
Auch hier propabilistisch sieht es wieder anders aus und der Zufall ist unser Freund was die erwartete Erfüllbarkeit angeht.

@CyborgBeta : Btw. Backtracking ist äquivalent zu "sich dabei den gelaufenen Weg zu merken".

(*) für die Einfachheit hier ist "nichts" leichter als "konstant viel", aber dennoch äquivalent (der besonne Leser fragt sich warum).
(**) in der Literatur wird auch manchmal anstatt von Löchern von Hosen geredet
(***) Man mache sich klar warum man keine Kreise/Ringe hat, wie in Problem-Instanz von CyborgBeta.

 

[BeBur]

Folglich - entgegen deiner Aussage - gilt, dass der Algorithmus nicht halten muss!

Das ist nicht entgegen meiner Aussage.