Komplexität eines zufällig gereisten N * M Gitters mit Backtracking

Question

Ich habe einen Algorithmus erstellt, der einen Zufallspfad über ein N * M Gitter mit Backtracking berechnet. Sie beginnt bei [N/2] [0] und endet bei [N/2] [M - 1]. Bei jeder Iteration wählt er eine zufällige Richtung (Links, Rechts, Vorwärts) und geht rekursiv weiter. Die ausgewählte Richtung wird im Speicher gehalten, so dass sie nicht von jedem Knoten zweimal verwendet wird. Wenn der Knoten einen bereits verwendeten Knoten oder die Grenze des Gitters trifft und jede Richtung getestet wurde, wird er auf dem Stapel zurück gezogen.

Es funktioniert perfekt, aber ich frage mich, wie man die Komplexität des Problems in Abhängigkeit von der Größe des Gitters berechnen.

Es tut mir leid für mein schlechtes Englisch, wenn ich vergessen habe, etwas zu sagen, dann bitte fragen Sie mir die Informationen, die Sie brauchen.

Vielen Dank!

Answer 1

Ich habe das Gefühl, dass man hier nicht über deterministische Laufzeit sprechen kann, weil theoretisch, wenn man einmal in einer Schleife steckt (zB wenn man einen bereits besuchten Knoten trifft), der Zufall für immer in die gleiche Richtung zurückkehrt die Wahrscheinlichkeit dafür ist sehr gering). Mit anderen Worten, Sie beschreiben das, was wir randomized algorithm nennen (ungefähr jeder Algorithmus, der zufällige Bits verwendet, um seine Ausführung zu steuern; das bedeutet, dass die Laufzeit eine zufällige Variable ist).

Stattdessen können Sie über expected running time sprechen, dh die erwartete Anzahl von Vorgängen, bevor der Algorithmus einen zufälligen Pfad zurückgibt.

Denken Sie darüber nach, einen Arbeitscode für den Algorithmus bereitzustellen, damit wir eine konkretere Antwort geben können.

Answer 2

Das klingt wie Dijkstra-Algorithmus ohne die Pfadlänge. Von diesem Standpunkt aus ist Ihr Problem kein allgemeiner Graph, Sie können also seine Struktur ausnutzen.

Speziell, da Sie Ihre Knoten markieren, so dass Sie sie nicht wiederholen, und jeder Knoten nicht mehr als 4 Kanten hat, ist der ungünstigste Fall proportional zur Anzahl der Knoten: O (MN). Auf der anderen Seite wäre der beste Fall (unwahrscheinlich wie er ist) zufällig einen kürzesten Pfad zu wählen, der O (M) wäre.

Da Sie Richtungen nach dem Zufallsprinzip wählen, sollte es für jedes gegebene M und N eine gut definierte Verteilung der Ausführungszeiten geben. Leider scheint eine genaue Analyse schwierig zu sein: leicht analysierbare Fälle, wie etwa ein zufälliger Durchlauf, gelten hier nicht, weil das Markieren von Knoten die Statistik bei jedem Schritt ändert und weil Ihre rechteckige Arena aus Sicht der Analyse eine komplexe Form ist.

Ich werde meine Hände winken und sagen, dass Sie erwarten können, dass die meisten Ihrer Verteilung näher an O (MN) sein sollte, da Sie die ungeraden self-avoiding walk erwarten, dass die Ergebnisse in der Regel nicht in die richtige Richtung führen; Dies würde Ihre erwartete Ausführungszeit ebenfalls auf O (MN) setzen. Es wird eine kleine Anzahl von Fällen geben, in denen es in die richtige Richtung geht und das Ziel trifft, bevor es einen signifikanten Anteil aller Knoten überprüft; Ich würde erwarten, dass der Anteil dieser glücklichen Fälle ~ 1/M der Gesamtverteilung sein sollte, und sollte etwas wie O (M^p) Schritte nehmen, wobei p ein gebrochener Exponent zwischen 1 und 2 ist. Laufzeiten nähern sich dem besten Fall wird von dieser Region aus exponentiell nach unten tendieren.

Wenn N < < M, dann könnten glückliche Fälle eher ~ 1/N der Gesamtverteilung sein; und wenn MN < < M^p wäre der exponentielle Schwanz alles, was vom "glücklichen" Fall übrig ist ...

Allerdings ist dies nur Ratesraten, keine richtige Analyse.