15

Betrachten Sie ein Quadrat-n-n-Gitterdiagramm, das so aussieht.

Gittergraph

Es ist wichtig zu beachten, dass dieses Diagramm 11 mal 11 ist .

An einem bestimmten Punkt steht ein Mann an einer Kreuzung und bewegt sich immer nur um jeweils einen Schritt vertikal oder horizontal zur nächsten Kreuzung. Leider hat er etwas zu viel getrunken und wählt die Richtung, in die er sich bewegt, zufällig aus den bis zu 4 möglichen Richtungen (oben, unten, links, rechts). Das sind bis zu 4, als ob er an einer Wand steht, er hat natürlich nur 3 Möglichkeiten und in einer Ecke hat er nur 2.

Er startet in der unteren linken Ecke und sein Ziel ist es, nach Hause zu kommen, das ist die obere rechte Ecke. Die Zeit ist einfach die Anzahl der Schritte, die er benötigt.

Sie sind jedoch ein böswilliger Gegner, der möchte, dass er so langsam wie möglich nach Hause kommt. Sie können während des Gehens jederzeit eine beliebige Anzahl von Kanten aus der Grafik löschen . Die einzige Einschränkung ist, dass Sie ihm immer einen Weg lassen müssen, um nach Hause zu kommen, und Sie eine Kante, die er bereits verwendet hat, nicht löschen können.

Die Herausforderung besteht darin, einen so böswilligen Gegner wie möglich zu finden und ihn dann mit einem zufälligen betrunkenen Spaziergänger auf einem ~~100 x 100~~ 20 x 20-Diagramm zu testen . Ihre Punktzahl ist einfach die durchschnittliche Zeit, die der Zufallsläufer benötigt, um über 10 1000 Läufe nach Hause zu kommen .

Sie können eine beliebige Sprache und Bibliothek verwenden, sofern diese frei verfügbar und unter Linux leicht zu installieren sind.

Was muss ich implementieren?

Sie sollten Code für den Zufallsläufer und auch für den Gegner implementieren und den Code so kombinieren, dass die Ausgabe bei Ausführung einfach der Durchschnitt von 1000 Läufen unter Verwendung Ihres gegnerischen Codes ist. Der Zufalls-Walker-Code sollte sehr einfach zu schreiben sein, da er nur (x-1, y), (x + 1, y), (x, y-1) und (x, y + 1) auswählt, um dies sicherzustellen Keines davon wurde gelöscht oder liegt außerhalb des gültigen Bereichs.

Der Code des Gegners ist natürlich schwieriger und muss sich auch merken, welche Kanten der Betrunkene bereits durchlaufen hat, damit er keine davon löschen und sicherstellen kann, dass für den Betrunkenen noch eine Route nach Hause besteht, was etwas schwieriger ist schnell zu tun.

Nachtrag 10 Läufe ist nicht genug, aber ich wollte keine Leute bestrafen, die es geschafft haben, wirklich lange Spaziergänge zu machen. Auf vielfachen Wunsch habe ich es jetzt auf 1000 erhöht. Wenn Ihr Marsch jedoch so lang ist, dass Sie nicht in realistischer Zeit 1000 Läufe ausführen können, geben Sie einfach die maximale Anzahl von Läufen an.

Highscore-Tabelle für 100 mal 100.

976124.754 von Optimizer.
103000363.218 von Peter Taylor.

Bearbeiten 1. Die Diagrammgröße wurde auf 20 mal 20 geändert, um die Laufzeit der Tests zu verbessern. Ich werde einen neuen High-Table-Score für diese Größe erstellen, wenn Leute die Scores einreichen.

Highscore-Tabelle für 20 mal 20.

230,794.38 (100k runs) by justhalf
227,934 by Sparr 
213,000 (approx) by Peter Taylor
199,094.3 by stokastic
188,000 (approx) by James_pic
 64,281 by Geobits

code-challenge graph-theory
quelle

2

Ich verstehe nicht Können Sie nicht einfach alle Kanten am Anfang löschen, mit Ausnahme derjenigen, die den längsten Pfad bilden?

Peter Olson

3

Ich sehe keine Regel, die besagt, dass der Betrunkene nicht zweimal dieselbe Kante zurückgehen kann. Wenn er den gleichen Weg zwischen zwei Punkten zweimal nehmen kann und willkürlich Wendungen wählt, ist dann logischerweise nicht ein Graph mit dem längsten durchschnittlichen (zufälligen) Durchlauf derjenige mit den meisten Kanten? Das heißt, wäre nicht der optimale (längste) Graph derjenige ohne gelöschte Kanten?

Millinon

3

Ich bin kein Fan von der Forderung, dass jeder Eintrag das Rad neu erfindet (Walker). Wenn jemand ein Testgeschirr / Framework veröffentlicht, werde ich es bewerten und verwenden.

Sparr

1

Der Vorteil, einen Teil eines Pfades zu entfernen, damit er zurückkehrt, um den weiten Weg zurückzulegen, geht völlig verloren, wenn sein Pfad zufällig ist. angeblich ist es genauso wahrscheinlich, dass er sich irgendwann umdreht, ohne dass Sie eine Kante entfernen müssen. Ich würde gerne einige Testdaten sehen, die die durchschnittliche Zeit ohne entfernte Kanten und dann mit bestimmten entfernten Kanten zeigen, wie Sie vermuten. Was diese Herausforderung betrifft, halte ich es für viel interessanter, wenn der Weg des Betrunkenen deterministisch wäre.

Millinon

3

10 Runden sind bei weitem nicht genug. Selbst bei einem statischen Labyrinth von 10 x 10, geschweige denn bei einem intelligenten Gegner und einem Labyrinth von 100 x 100, beträgt die Standardabweichung etwa 50% des Durchschnittsfalls. Ich laufe 10000 Runden und würde die Ergebnisse immer noch nicht für vergleichenswert halten.

Sparr

10

230.794,38 auf 20x20, 100k Läufen

Letztes Update: Ich habe endlich eine perfekte dynamische 2-Pfad-Lösung erstellt. Ich sagte perfekt, da die vorherige Version eigentlich nicht symmetrisch ist, war es einfacher, einen längeren Weg zu finden, wenn der Betrunkene einen Weg über den anderen nahm. Die aktuelle ist symmetrisch, sodass eine höhere erwartete Anzahl von Schritten möglich ist. Nach wenigen Versuchen scheint es sich um 230.000 zu handeln, eine Verbesserung gegenüber der vorherigen, die sich auf etwa 228.000 beläuft. Aber statistisch gesehen liegen diese Zahlen immer noch innerhalb ihrer enormen Abweichung, daher behaupte ich nicht, dass dies wesentlich besser ist, aber ich glaube, dass dies besser sein sollte als die vorherige Version.

Der Code befindet sich am Ende dieses Beitrags. Es wurde so aktualisiert, dass es viel schneller als die Vorgängerversion ist und 1000 Läufe in 23 Sekunden erledigt.

Unten ist ein Probelauf und ein Probelabyrinth:

Perfekter Walker
Durchschnitt: 230794,384
Max: 1514506
Min: 25860
Fertiggestellt in 2317.374s
 _ _ _ _ _ _ _ _ _ _ _ _. 
| | | | | | | | | | | | | | | _ _ _ _  
| | | | | | | | | | | | | | | | _ _ _ _  
| | | | | | | | | | | | | | | _ _ _ _ |
| | | | | | | | | | | | | | | | _ _ _ _  
| | | | | | | | | | | | | | | _ _ _ _ |
| | | | | | | | | | | | | | | | _ _ _ _  
| | | | | | | | | | | | | | | _ _ _ _ |
| | | | | | | | | | | | | | _ | | _ _ _ _  
| | | | | | | | | | | | | _ _ _ _ _ _ |
| | | | | | | | | | | | | | _ _ _ _ _ _  
| | | | | | | | | | | | | _ _ _ _ _ _ |
| | | | | | | | | | | | | | _ _ _ _ _ _  
| | | | | | | | | | | | | _ _ _ _ _ _ |
| | | | | | _ | | _ | | _ | | _ | | _ _ _ _ _ _  
| | | | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | | | | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _  
| | | | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ | | _ | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _  
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Vorherige Einsendungen

Endlich kann ich mit Sparrs Ergebnis mithalten! = D

Basierend auf meinen vorherigen Experimenten (siehe unten in diesem Beitrag) besteht die beste Strategie darin, einen doppelten Pfad zu haben und einen zu schließen, wenn der Betrunkene einen von ihnen erreicht Erhöhen Sie die Chance, dass er in einen längeren Pfad gerät.

Ausgehend von meiner DOUBLE_PATHStrategie baute ich eine andere, die das Labyrinth (mein DOUBLE_PATHLabyrinth war leicht zu ändern) in Abhängigkeit von der Trunkenheiterbewegung verändert. Da er einen Pfad mit mehr als einer verfügbaren Option nimmt, werde ich die Pfade schließen, um nur zwei mögliche Optionen zu belassen (eine, von der er gekommen ist, eine, die nicht gereist ist).

Dies klingt ähnlich wie das, was Sparr erreicht hat, wie das Ergebnis zeigt. Der Unterschied zu seinem ist zu gering, um als besser angesehen zu werden, aber ich würde sagen, dass mein Ansatz dynamischer ist als der von ihm, da mein Labyrinth modifizierbarer ist als der von Sparr =)

Das Ergebnis mit einem Musterlabyrinth:

EXTREME_DOUBLE_PATH
Durchschnitt: 228034,89
Max: 1050816
Min: 34170
Fertiggestellt in 396.728s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ | | _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Experimente Abschnitt

Das Beste ist die gleiche Strategie wie Stokastic. Ich bin stolz darauf, mit verschiedenen Strategien zu experimentieren und schöne Ergebnisse zu drucken :)

Jedes der unten abgebildeten Labyrinthe ist das letzte Labyrinth, nachdem der Betrunkene zu Hause angekommen ist. Aufgrund der Zufälligkeit der Betrunkenenbewegung und der Dinamizität des Gegners können sie sich daher von Lauf zu Lauf geringfügig unterscheiden.

Ich werde jede Strategie beschreiben:

Einzelner Pfad

Dies ist der einfachste Ansatz, bei dem ein einziger Pfad vom Eingang zum Ausgang erstellt wird.

SINGLE_PATH
Durchschnitt: 162621,612
Max: 956694
Min: 14838
Fertiggestellt in 149.430s
 _ _ _ _ _ _ _ _ _ _
| | _ | | _ | | _ | | _ | | _ | | _ | | _ | | _ | | _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Insel (Stufe 0)

Dies ist ein Ansatz, der versucht, den Betrunkenen auf einer fast einsamen Insel zu fangen. Funktioniert nicht so gut wie ich erwartet hatte, aber dies ist eine meiner ersten Ideen, also füge ich sie hinzu.

Es gibt zwei Wege, die zum Ausgang führen, und wenn der Säufer sich einem nähert, schließt der Gegner ihn und zwingt ihn, den anderen Ausgang zu finden (und wird möglicherweise wieder auf der Insel gefangen).

INSEL
Durchschnitt: 74626.070
Max: 428560
Min: 1528
Fertiggestellt in 122.512s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _   
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Doppelter Pfad

Dies ist die am häufigsten diskutierte Strategie, bei der zwei gleichlange Pfade zum Ausgang führen und einer davon geschlossen wird, wenn sich der Betrunkene einem von ihnen nähert.

DOUBLE_PATH
Durchschnitt: 197743.472
Max: 1443406
Min .: 21516
Fertiggestellt in 308.177s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
 _ _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Insel (Stufe 1)

Inspiriert von den vielen Pfaden der Insel und der hohen Anzahl von Spaziergängen auf einem Pfad verbinden wir die Insel mit dem Ausgang und machen ein Labyrinth auf der Insel, wodurch insgesamt drei Wege zum Ausgang entstehen und ähnlich wie im vorherigen Fall jeder der beiden Wege geschlossen wird Verlasse den Raum, wenn der Säufer näher kommt.

Dies funktioniert etwas besser als ein reiner Einzelpfad, besiegt jedoch den doppelten Pfad nicht.

INSEL
Durchschnitt: 166265.132
Max: 1162966
Min: 19544
Fertiggestellt in 471.982s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ | _
| | | _ | | _ | | _ | | _ | | _ | | _ | | _ | | _ | |  
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Insel (Stufe 2)

Bei dem Versuch, die vorherige Idee zu erweitern, habe ich eine verschachtelte Insel mit insgesamt fünf Pfaden erstellt, aber es scheint nicht so gut zu funktionieren.

INSEL
Durchschnitt: 164222,712
Max: 927608
Min: 22024
Fertiggestellt in 793.591s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _
| | _ _ _ _ _ _ _ _ | _ |  
| | | | _ | | _ | | _ | | _ | | _ | | _ | | _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| _ | _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Insel (Stufe 3)

Wenn wir feststellen, dass der doppelte Pfad tatsächlich besser funktioniert als der einzelne Pfad, machen wir die Insel im doppelten Pfad!

Das Ergebnis ist eine Verbesserung gegenüber Island (Level 1), aber es schlägt immer noch nicht den doppelten Weg.

Zum Vergleich ergibt sich für den doppelten Weg der Inselgröße ein Mittelwert von 131.134,42 Zügen. Dies führt zu einer beachtlichen Anzahl von Zügen (ca. 40.000), die jedoch nicht ausreichen, um den Doppelpfad zu schlagen.

INSEL
Durchschnitt: 171730,090
Max: 769080
Min: 29760
Fertiggestellt in 587.646s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |  
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Insel (Stufe 4)

Wieder experimentieren mit verschachtelten Inseln, und wieder funktioniert es nicht so gut.

INSEL
Durchschnitt: 149723.068
Max: 622106
Min: 25752
Fertiggestellt in 830.889s
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _    
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _ |
| | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | _ |  
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | |
| | | _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| | _ _ _ _ _ _ _ | | _ _ _ _ _ _ _ | |
| | _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | | |
| _ | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ | |
| _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ |

Fazit

Alles in allem beweist dies, dass ein einziger langer Weg von der aktuellen Position des Trunkenboldes zum Ausgang am besten funktioniert, was durch die Doppelpfadstrategie erreicht wird, da der Trunkenbold nach dem Schließen eines Ausgangs die maximal mögliche Entfernung zurücklegen muss, um zum Ausgang zu gelangen der Ausgang.

Dies deutet weiter darauf hin, dass die grundlegende Strategie immer noch ein doppelter Pfad sein sollte, und wir können nur ändern, wie dynamisch die Pfade erstellt werden, was von Sparr getan wurde. Ich glaube, seine Strategie ist der richtige Weg!

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.TreeSet;

public class Walker {

    enum Strategy{
        SINGLE_PATH,
        ISLAND,
        DOUBLE_PATH,
        EXTREME_DOUBLE_PATH,
        PERFECT_DOUBLE_PATH,
    }

    int width,height;
    int x,y; //walker's position
    int dX,dY; //destination
    Point[][] points;
    int stepCount = 0;

    public static void main(String[]args){
        int side = 20;
//      runOnce(side, Strategy.EXTREME_DOUBLE_PATH, 0);
        runOnce(side, Strategy.PERFECT_DOUBLE_PATH, 0);
//      for(Strategy strategy: Strategy.values()){
//          runOnce(side, strategy, 0);
//      }
//      runOnce(side, Strategy.ISLAND, 1);
//      runOnce(side, Strategy.ISLAND, 2);
//      Scanner scanner = new Scanner(System.in);
//      System.out.println("Enter side, strategy (SINGLE_PATH, ISLAND, DOUBLE_PATH, EXTREME_DOUBLE_PATH), and level:");
//      while(scanner.hasNext()){
//          side = scanner.nextInt();
//          Strategy strategy = Strategy.valueOf(scanner.next());
//          int level = scanner.nextInt();
//          scanner.nextLine();
//          runOnce(side, strategy, level);
//          System.out.println("Enter side, strategy (SINGLE_PATH, ISLAND, DOUBLE_PATH, EXTREME_DOUBLE_PATH), and level:");
//      }
//      scanner.close();
    }

    private static Walker runOnce(int side, Strategy strategy, int level) {
        Walker walker = null;
        long total = 0;
        int max = 0;
        int min = Integer.MAX_VALUE;
        double count = 1000;
        long start = System.currentTimeMillis();
        for(int i=0; i<count; i++){
            walker = new Walker(0,0,side,side,side-1,side-1, strategy, level, false);
            total += walker.stepCount;
            max = Math.max(walker.stepCount, max);
            min = Math.min(walker.stepCount, min);
//          System.out.println("Iteration "+i+": "+walker.stepCount);
        }
        System.out.printf("%s\nAverage: %.3f\nMax: %d\nMin:%d\n",strategy, total/count, max, min);
        System.out.printf("Completed in %.3fs\n", (System.currentTimeMillis()-start)/1000.0);
        walker.printPath();
        return walker;
    }

    private void createIsland(int botLeftX, int botLeftY, int topRightX, int topRightY){
        for(int i=botLeftY+1; i<topRightY; i++){
            if(i>botLeftY+1) deletePath(points[botLeftX][i].right());
            if(i<topRightY-1) deletePath(points[topRightX][i].left());
        }
        for(int i=botLeftX+1; i<topRightX; i++){
            if(i>botLeftX+1) deletePath(points[i][botLeftY].up());
            if(i<topRightX-1) deletePath(points[i][topRightY].down());
        }
    }

    private void createSinglePath(int botLeftX, int botLeftY, int topRightX, int topRightY){
        for(int i=botLeftY; i<topRightY; i++){
            if(i==topRightY-1 && (topRightY+1-botLeftY)%2==0){
                for(int j=botLeftX; j<topRightX; j++){
                    if(j==topRightX-1 && (j-botLeftX)%2==0){
                        deletePath(points[topRightX][topRightY].down());
                    } else {
                        deletePath(points[j][topRightY-1+((j-botLeftX)%2)].right());
                    }
                }
            } else {
                for(int j=botLeftX+(i-botLeftY)%2; j<topRightX+((i-botLeftY)%2); j++){
                    deletePath(points[j][i].up());
                }
            }
        }
    }

    private void createDoublePath(int botLeftX, int botLeftY, int topRightX, int topRightY){
        for(int i=botLeftY; i<topRightY; i++){
            if(i>botLeftY && (width%4!=1 || i<topRightY-1)) deletePath(points[width/2-1][i].right());
            if(i==topRightY-1 && (topRightY+1-botLeftY)%2==1){
                for(int j=botLeftX; j<topRightX; j++){
                    if((j-botLeftX)%2==0 || j<topRightX-1){
                        deletePath(points[j][topRightY-1+((j-botLeftX)%2)].right());
                    } else {
                        deletePath(points[topRightX-1][topRightY-1].right());
                    }
                }
            } else {
                if((i-botLeftY)%2==0){
                    for(int j=botLeftX+1; j<topRightX; j++){
                        deletePath(points[j][i].up());
                    }
                } else {
                    for(int j=botLeftX; j<topRightX+1; j++){
                        if(j!=width/2 && j!=width/2-1){
                            deletePath(points[j][i].up());
                        }
                    }
                }
            }
        }
    }

    public Walker(int startingX,int startingY, int Width, int Height, int destinationX, int destinationY, Strategy strategy, int level, boolean animate){
        width = Width;
        height = Height;
        dX = destinationX;
        dY = destinationY;
        x=startingX;
        y=startingY;
        points = new Point[width][height];
        for(int y=0; y<height; y++){
            for(int x=0; x<width; x++){
                points[x][y] = new Point(x,y);
            }
        }
        for(int y=0; y<height; y++){
            for(int x=0; x<width; x++){
                if(x<width-1) new Edge(points[x][y], points[x+1][y]);
                if(y<height-1) new Edge(points[x][y], points[x][y+1]);
            }
        }

        if(strategy == Strategy.SINGLE_PATH) createSinglePath(0,0,width-1,height-1);

        if(strategy == Strategy.DOUBLE_PATH) createDoublePath(0,0,width-1,height-1);

        List<EdgeList> edgeLists = new ArrayList<EdgeList>();
        if(strategy == Strategy.ISLAND){
            List<Edge> edges = new ArrayList<Edge>();
            if(level==0){
                createIsland(0,0,width-1,height-1);
                deletePath(points[width-2][height-2].right());
                deletePath(points[width-2][height-2].up());
            } else {
                for(int i=0; i<level; i++){
                    createIsland(i,i,width-1-i, height-1-i);
                }
                createDoublePath(level,level,width-1-level,height-1-level);
                for(int i=height-1; i>=height-level; i--){
                    edges.add(points[i-2][i].right());
                    edges.add(points[i][i-2].up());
                    edgeLists.add(new EdgeList(points[i-1][i].right(), points[i][i-1].up()));
                }
            }
            edges.add(points[width-1-level][height-1-level].down());
            edges.add(points[width-1-level][height-1-level].left());
            edgeLists.add(new EdgeList(edges.toArray(new Edge[0])));
        }

        int[] availableVerticals = new int[height];
        if(strategy == Strategy.EXTREME_DOUBLE_PATH){
            for(int i=1; i<width-1; i++){
                deletePath(points[i][0].up());
            }
            availableVerticals[0] = 2;
            for(int i=1; i<height; i++){
                availableVerticals[i] = width;
            }
        }

        boolean[][] available = new boolean[width][height];
        if(strategy == Strategy.PERFECT_DOUBLE_PATH){
            for(int x=0; x<width; x++){
                for(int y=0; y<height; y++){
                    if(x%2==1 && y%2==1){
                        available[x][y] = true;
                    } else {
                        available[x][y] = false;
                    }
                }
            }
        }
//      printPath();
        while(!walk()){
            if(animate)try{Thread.sleep(500);}catch(InterruptedException e){}
            if(strategy == Strategy.ISLAND){
                if(x==y && (x==1 || (x>=2 && x<=level))){
                    if(!hasBeenWalked(points[x][x].down())){
                        deletePath(points[x][x].down());
                    } else if(!hasBeenWalked(points[x][x].left())){
                        deletePath(points[x][x].left());
                    }
                }
            }
            if(strategy == Strategy.EXTREME_DOUBLE_PATH){
                Point cur = points[x][y];
                int untravelled = 0;
                for(Edge edge: cur.edges) if(edge!=null && !edge.walked) untravelled++;
                if(untravelled>1){
                    if(cur.up()!=null && availableVerticals[y]>2 && !cur.up().walked){
                        deletePath(cur.up());
                        availableVerticals[y]--;
                    }
                    if(cur.down()!=null && !cur.down().walked){
                        deletePath(cur.down());
                        availableVerticals[y-1]--;
                    }
                    if(cur.up()!=null && cur.left()!=null && !cur.left().walked){
                        deletePath(cur.left());
                        deletePath(points[x][y+1].left());
                    }
                    if(cur.up()!=null && cur.right()!=null && !cur.right().walked){
                        deletePath(cur.right());
                        if(y<height-1) deletePath(points[x][y+1].right());
                    }
                }
            }
            if(strategy == Strategy.PERFECT_DOUBLE_PATH){
                Point cur = points[x][y];
                int untravelled = 0;
                for(Edge edge: cur.edges) if(edge!=null && !edge.walked) untravelled++;
                if(x%2!=1 || y%2!=1){
                    if(untravelled>1){
                        if(cur.down()==null && hasBeenWalked(cur.right())){
                            if(canBeDeleted(cur.up())) deletePath(cur.up());
                        }
                        if(cur.down()==null && hasBeenWalked(cur.left())){
                            if(x%2==0 && y%2==1 && canBeDeleted(cur.right())) deletePath(cur.right());
                            else if(cur.right()!=null && canBeDeleted(cur.up())) deletePath(cur.up());
                        }
                        if(cur.left()==null && hasBeenWalked(cur.up())){
                            if(canBeDeleted(cur.right())) deletePath(cur.right());
                        }
                        if(cur.left()==null && hasBeenWalked(cur.down())){
                            if(x%2==1 && y%2==0 && canBeDeleted(cur.up())) deletePath(cur.up());
                            else if (cur.up()!=null && canBeDeleted(cur.right())) deletePath(cur.right());
                        }
                    }
                } else {
                    if(!hasBeenWalked(cur.left())){
                        if(x>1 && available[x-2][y]){
                            if(untravelled>1){
                                available[x-2][y] = false;
                                deletePath(cur.up());
                            }
                        } else if(cur.up()!=null){
                            if(canBeDeleted(cur.left())) deletePath(cur.left());
                            if(canBeDeleted(points[x][y+1].left())) deletePath(points[x][y+1].left());
                        }
                    }
                    if(!hasBeenWalked(cur.down())){
                        if(y>1 && available[x][y-2]){
                            if(untravelled>1){
                                available[x][y-2] = false;
                                deletePath(cur.right());
                            }
                        } else if(cur.right()!=null){
                            if(canBeDeleted(cur.down())) deletePath(cur.down());
                            if(canBeDeleted(points[x+1][y].down())) deletePath(points[x+1][y].down());
                        }
                    }
                }
            }
            if(strategy == Strategy.DOUBLE_PATH || strategy == Strategy.EXTREME_DOUBLE_PATH
                    || strategy == Strategy.PERFECT_DOUBLE_PATH){
                if(x==width-2 && y==height-1 && points[width-1][height-1].down()!=null){
                    deletePath(points[width-1][height-1].left());
                }
                if(x==width-1 && y==height-2 && points[width-1][height-1].left()!=null){
                    deletePath(points[width-1][height-1].down());
                }
            } else if(strategy == Strategy.ISLAND){
                for(EdgeList edgeList: edgeLists){
                    boolean deleted = false;
                    for(Edge edge: edgeList.edges){
                        if(edge.start.x == x && edge.start.y == y){
                            if(!hasBeenWalked(edge)){
                                deletePath(edge);
                                edgeList.edges.remove(edge);
                                if(edgeList.edges.size() == 1){
                                    edgeLists.remove(edgeList);
                                }
                                deleted = true;
                                break;
                            }
                        }
                    }
                    if(deleted) break;
                }
            }
            if(animate)printPath();
        }
    }

    public boolean hasBeenWalked(Edge edge){
        if(edge == null) return false;
        return edge.walked;
    }

    public boolean canBeDeleted(Edge edge){
        if(edge == null) return false;
        return !edge.walked;
    }

    public List<Edge> getAdjacentUntravelledEdges(){
        List<Edge> result = new ArrayList<Edge>();
        for(Edge edge: points[x][y].edges){
            if(edge!=null && !hasBeenWalked(edge)) result.add(edge); 
        }
        return result;
    }

    public void printPath(){
        StringBuilder builder = new StringBuilder();
        for(int y=height-1; y>=0; y--){
            for(int x=0; x<width; x++){
                Point point = points[x][y];
                if(this.x==x && this.y==y){
                    if(point.up()!=null) builder.append('?');
                    else builder.append('.');
                } else {
                    if(point.up()!=null) builder.append('|');
                    else builder.append(' ');
                }
                if(point.right()!=null) builder.append('_');
                else builder.append(' ');
            }
            builder.append('\n');
        }
        System.out.print(builder.toString());
    }

    public boolean walk(){
        ArrayList<Edge> possibleMoves = new ArrayList<Edge>();
        Point cur = points[x][y];
        for(Edge edge: cur.edges){
            if(edge!=null) possibleMoves.add(edge);
        }
        int random = (int)(Math.random()*possibleMoves.size());
        Edge move = possibleMoves.get(random);
        move.walked = true;
        if(move.start == cur){
            x = move.end.x;
            y = move.end.y;
        } else {
            x = move.start.x;
            y = move.start.y;
        }
        stepCount++;
        if(x==dX && y == dY){
            return true;
        } else {
            return false;
        }
    }

    public boolean isSolvable(){
        TreeSet<Point> reachable = new TreeSet<Point>();
        Queue<Point> next = new LinkedList<Point>();
        next.offer(points[x][y]);
        reachable.add(points[x][y]);
        while(next.size()>0){
            Point cur = next.poll();
            ArrayList<Point> neighbors = new ArrayList<Point>();
            if(cur.up()!=null) neighbors.add(cur.up().end);
            if(cur.right()!=null) neighbors.add(cur.right().end);
            if(cur.down()!=null) neighbors.add(cur.down().start);
            if(cur.left()!=null) neighbors.add(cur.left().start);
            for(Point neighbor: neighbors){
                if(!reachable.contains(neighbor)){
                    if(neighbor == points[dX][dY]) return true;
                    reachable.add(neighbor);
                    next.offer(neighbor);
                }
            }
        }
        return false;
    }

    public boolean deletePath(Edge toDelete){
        if(toDelete == null) return true;
//      if(toDelete.walked){
//          System.err.println("Edge already travelled!");
//          return false;
//      }
        int startIdx = toDelete.getStartIdx();
        int endIdx = toDelete.getEndIdx();
        toDelete.start.edges[startIdx] = null;
        toDelete.end.edges[endIdx] = null;
//      if(!isSolvable()){
//          toDelete.start.edges[startIdx] = toDelete;
//          toDelete.end.edges[endIdx] = toDelete;
//          System.err.println("Invalid deletion!");
//          return false;
//      }
        return true;
    }

    static class EdgeList{
        List<Edge> edges;

        public EdgeList(Edge... edges){
            this.edges = new ArrayList<Edge>();
            this.edges.addAll(Arrays.asList(edges));
        }
    }

    static class Edge implements Comparable<Edge>{
        Point start, end;
        boolean walked;

        public Edge(Point start, Point end){
            walked = false;
            this.start = start;
            this.end = end;
            this.start.edges[getStartIdx()] = this;
            this.end.edges[getEndIdx()] = this;
            if(start.compareTo(end)>0){
                Point tmp = end;
                end = start;
                start = tmp;
            }
        }

        public Edge(int x1, int y1, int x2, int y2){
            this(new Point(x1,y1), new Point(x2,y2));
        }

        public boolean exists(){
            return start.edges[getStartIdx()] != null || end.edges[getEndIdx()] != null;
        }

        public int getStartIdx(){
            if(start.x == end.x){
                if(start.y < end.y) return 0;
                else return 2;
            } else {
                if(start.x < end.x) return 1;
                else return 3;
            }
        }

        public int getEndIdx(){
            if(start.x == end.x){
                if(start.y < end.y) return 2;
                else return 0;
            } else {
                if(start.x < end.x) return 3;
                else return 1;
            }
        }

        public boolean isVertical(){
            return start.x==end.x;
        }

        @Override
        public int compareTo(Edge o) {
            int result = start.compareTo(o.start);
            if(result!=0) return result;
            return end.compareTo(o.end);
        }
    }

    static class Point implements Comparable<Point>{
        int x,y;
        Edge[] edges;

        public Point(int x, int y){
            this.x = x;
            this.y = y;
            edges = new Edge[4];
        }

        public Edge up(){ return edges[0]; }
        public Edge right(){ return edges[1]; }
        public Edge down(){ return edges[2]; }
        public Edge left(){ return edges[3]; }

        public int compareTo(Point o){
            int result = Integer.compare(x, o.x);
            if(result!=0) return result;
            result = Integer.compare(y, o.y);
            if(result!=0) return result;
            return 0;
        }
    }
}

nur zur Hälfte
quelle

Das ist sehr beeindruckend. Wie lange dauert die Ausführung? Wenn die Siegerbeiträge so knapp bleiben, müssen wir die Anzahl der Läufe erhöhen, um zu sehen, ob wir sie trennen können.

1

Das Timing ist bereits im Snippet enthalten. Rund 400er für 1000 Läufe. Dies schließt die Lösbarkeitsprüfung bei jeder Pfadlöschung ein. Ich kann das entfernen, um ungefähr 170s für 1000 Läufe zu haben. So kann ich in etwa einer Stunde 20 km Läufe machen.

Nur die Hälfte des

Wenn ich noch weiter optimiere, kann ich möglicherweise 100k in 3,5 Stunden laufen.

Nur die Hälfte des

Mein Ergebnis ist mit 100k Läufen und hat 10 Minuten gedauert. @justhalf sehr schön auf dem flexibleren Doppelpfad Labyrinth. Ich weiß, wie man ein noch besseres macht, aber ich habe nicht die Geduld, es im Moment umzusetzen.

Sparr

2

Freut mich, dass die symmetrische Lösung implementiert wurde. Ich habe noch eine weitere Idee, um diese Lösung zu verbessern, und diesmal denke ich, ich könnte es selbst implementieren :)

Sparr

10

227934 (20 x 20)

Mein dritter Versuch. Verwendet den gleichen allgemeinen Ansatz wie @stokastic mit zwei Pfaden zum Ausgang. Wenn der Wanderer das Ende eines Pfades erreicht, wird er geschlossen und muss zurückkehren, um zum Ende des anderen Pfades zu gelangen und diesen zu verlassen. Meine Verbesserung besteht darin, die Pfade zu generieren, während der Wanderer voranschreitet, sodass der Pfad, den er in der ersten Hälfte des Prozesses weiter verfolgt, länger als der andere Pfad wird.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <iostream>

#define DEBUG 0
#define ROUNDS 10000

#define Y 20
#define X 20
#define H (Y*2+1)
#define W (X*2+1)

int maze[H][W];
int scores[ROUNDS];

int x, y;

void print_maze(){
    char line[W+2];
    line[W+1]=0;
    for(int row=0;row<H;row++) {
        for(int col=0;col<W;col++) {
            switch(maze[row][col]) {
                case 0:
                    line[col]=' ';
                    break;
                case 1:
                    line[col]=row%2?'-':'|';
                    break;
                case 8:
                    line[col]=(row==y*2+1&&col==x*2+1)?'@':'?';
                    break;
                case 9:
                    line[col]=(row==y*2+1&&col==x*2+1)?'@':'*';
                    break;
            }
        }
        line[W]='\n';
        printf("%s",line);
    }
    printf("%d %d\n",y,x);
}

int main(){
    srand (time(NULL));
    long long total_turns = 0;
    for(int round=0;round<ROUNDS;round++) {
        for (int r=0;r<H;r++) {
            for (int c=0;c<W;c++) {
                maze[r][c]=0;
            }
        }
        maze[1][1]=9;
        maze[1][2]=1;
        maze[2][1]=1;
        maze[1][3]=8;
        maze[3][1]=8;
        int progress_l = 0;
        int progress_r = 0;
        int side = 0;
        int closed_exit = 0;
        x=0;
        y=0;
        if (DEBUG) print_maze();
        long long turn = 0;
        int in = 0;
        while (x!=X-1||y!=Y-1) {
            turn++;
            int r = y*2+1;
            int c = x*2+1;
            int dx=0, dy=0;
            if (DEBUG) {
                std::cin>>in;
                switch(in) {
                    case 0:
                        dy=-1; dx=0; break;
                    case 1:
                        dy=0; dx=1; break;
                    case 2:
                        dy=1; dx=0; break;
                    case 3:
                        dy=0; dx=-1; break;
                    default:
                        dy=0; dx=0; break;
                }
            } else {
                int exits = maze[r-1][c] + maze[r][c+1] + maze[r+1][c] + maze[r][c-1];
                int exit_choice = -1;
                do {
                    if (rand()%exits == 0) {
                        exit_choice = exits;
                        break;
                    } else {
                        exits--;
                    }
                }while(exits);

                --exits;

                if (maze[r-1][c]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = -1;
                        dx = 0;
                    }
                }
                if (maze[r][c+1]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = 0;
                        dx = 1;
                    }
                }
                if (maze[r+1][c]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = 1;
                        dx = 0;
                    }
                }
                if (maze[r][c-1]&&!dx&&!dy) {
                    if (exits) {
                        --exits;
                    } else {
                        dy = 0;
                        dx = -1;
                    }
                }
            }

            x+=dx;
            y+=dy;

            if(x==X-1 && y==Y-1) continue;

            if (x==0&&y==1) side=-1;
            if (x==1&&y==0) side=1;
            if (maze[y*2+1][x*2+1]==8) { // room needs another exit, maybe
                if (side==-1) { // left half of maze
                    if (y==1) { // top of a column
                        if (x%2) { // going up, turn right
                            maze[y*2+1][x*2+2]=1;
                            maze[y*2+1][x*2+3]=8;
                        } else { // going right, turn down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else if (y==Y-1) { // bottom of a column
                        if (x%2 && x<(X-progress_r-3)) { // going right, turn up if there's room
                            maze[y*2+0][x*2+1]=1;
                            maze[y*2-1][x*2+1]=8;
                            progress_l=x+1;
                        } else { // going down or exiting, go right
                            if (x!=X-2 or closed_exit==1) {
                                maze[y*2+1][x*2+2]=1;
                                maze[y*2+1][x*2+3]=8;
                            } else {
                                closed_exit = -1;
                            }
                        }
                    } else { // in a column
                        if (maze[y*2+0][x*2+1]) { // going down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        } else { // going up
                            maze[y*2+0][x*2+1]=1;
                            maze[y*2-1][x*2+1]=8;
                        }
                    }
                } else { // right half of maze
                    if (y==0) { // top row
                        if (x<X-1) { // go right
                            maze[y*2+1][x*2+2]=1;
                            maze[y*2+1][x*2+3]=8;
                        } else { // go down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else if (y==Y-2) { // heading right to the exit
                        if (x<X-1) { // go right
                            maze[y*2+1][x*2+2]=1;
                            maze[y*2+1][x*2+3]=8;
                        } else { // go down
                            if (x!=X-1 or closed_exit==-1) {
                                maze[y*2+2][x*2+1]=1;
                                maze[y*2+3][x*2+1]=8;
                            } else {
                                closed_exit = 1;
                            }
                        }
                    } else if (y==Y-3) { // bottom of a column
                        if (x>progress_l+1) { // do we have room for another column?
                            if (!(x%2)&&y>1) { // going left, turn up
                                maze[y*2+0][x*2+1]=1;
                                maze[y*2-1][x*2+1]=8;
                            } else { // going down, turn left
                                maze[y*2+1][x*2+0]=1;
                                maze[y*2+1][x*2-1]=8;
                                progress_r=X-x-1;
                            }
                        } else { // abort, move down to escape row
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else if (y==1) { // top of a column
                        if (!(x%2)) { // going up, turn left
                            maze[y*2+1][x*2+0]=1;
                            maze[y*2+1][x*2-1]=8;
                        } else { // going left, turn down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        }
                    } else { // in a column
                        if (maze[y*2+0][x*2+1]) { // going down
                            maze[y*2+2][x*2+1]=1;
                            maze[y*2+3][x*2+1]=8;
                        } else { // going up
                            maze[y*2+0][x*2+1]=1;
                            maze[y*2-1][x*2+1]=8;
                        }
                    }

                }
                maze[y*2+1][x*2+1]=9;
            }

            if (DEBUG) print_maze();
        }
        // print_maze();
        printf("turns:%lld\n",turn);
        scores[round] = turn;
        total_turns += turn;
    }
    printf("%d rounds in a %d*%d maze\n",ROUNDS,X,Y);
    long long avg = total_turns/ROUNDS;
    printf("average: % 10lld\n",avg);
    long long var = 0;
    for(int r=0;r<ROUNDS;r++){
        var += (scores[r]-avg)*(scores[r]-avg);
    }
    var/=ROUNDS;
    // printf("variance: %lld\n",var);
    int stddev=sqrt(var);
    printf("stddev:  % 10d\n",stddev);

}

Ausgabe (mit Zeit):

...
turns:194750
turns:506468
turns:129684
turns:200712
turns:158664
turns:156550
turns:311440
turns:137900
turns:86948
turns:107134
turns:81806
turns:310274
100000 rounds in a 20*20 maze
average:     227934
stddev:      138349
real    10m54.797s
...

Beispiel meines Labyrinths mit ungefähr gleichlangen Hälften zum Pfad, wobei der linke / untere Pfad vom Ausgang abgeschnitten ist (unten rechts):

  _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
 |  _   _   _   _   _   _   _   _   _  |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | | | | | | | | | | |
 | | | | | | | | | | |_| |_| |_| |_| |_|
 | | | | | | | | | |_ _ _ _ _ _ _ _ _ _
 |_| |_| |_| |_| |_ _ _ _ _ _ _ _ _ _  !

PS: Mir ist eine geringfügige Verbesserung dieses Algorithmus bekannt, bei der ein geschickterer Code erforderlich ist, um eine andere Form für die beiden Pfade zu generieren: Treppen statt Zick-Zack-Höhen.

Sparr
quelle

Färbe mich beeindruckt. Sie haben meine Stimme, Sir!

Stokastic

1

Das ist ziemlich beeindruckend. Erinnerst du dich, als wir uns gerade auf die Gesichter der Betrunkenen gezogen haben?

Dennis

Es ist ziemlich schwer, Ihre Grafik zu erkennen. Vielleicht können Sie Ihren Grafikdruck auf etwas Ähnliches wie meinen umstellen?

Nur die Hälfte des

1

@ Justhalf Ihr Wunsch ist mein Befehl

Sparr

1

@justhalf Ich habe es auf Papier gezeichnet. Ich muss nur die Logik schreiben. Wenn ich es in ein paar Tagen nicht fertig bekomme, gebe ich dir die Skizze? :)

Sparr

6

135.488.307,9 für 98 x 98

199094.3 für 20x20

Ich habe eine Lösung implementiert, die zwei Wege zum Ziel schafft und genau einen davon schließt, sobald der Betrunkene es erreicht. Dies simuliert eine Pfadlänge, die mindestens das 1,5-fache der Länge eines einzelnen Pfads vom Anfang bis zum Ende beträgt. Nach 27 Läufen habe ich durchschnittlich 135 Millionen getroffen. Leider dauert ein Spaziergang mehrere Minuten, sodass ich ihn die nächsten Stunden laufen muss. Eine Einschränkung - mein Doppelpfad-Generator funktioniert nur, wenn die Größe des Diagramms die Form 4 * n + 2 hat, was bedeutet, dass ich 100 am nächsten kommen kann, 102 oder 98. Ich werde die Ergebnisse mit 98 veröffentlichen, was ich erwarte um die Zick-Zack-Methode noch zu übertreffen. Ich werde später an einem besseren Pfadsystem arbeiten. Derzeit werden Ergebnisse in Form von (Anzahl Schritte, aktueller Durchschnitt) nach jedem Spaziergang ausgegeben.

BEARBEITEN: Behoben, so dass Code jetzt für Diagrammgrößen funktioniert, die ein Vielfaches von 2 und nicht mehr 4 * n + 2 sind.

Code: (Fügen Sie dem Walker-Konstruktor in Zeile 187 das Argument 'True' hinzu, um das Diagramm als Turtle zu zeichnen).

import random
import turtle

WIDTH  = 20
HEIGHT = 20
L, U, R, D = 1, 2, 4, 8

def delEdge(grid, x1, y1, x2, y2):

    # check that coordinates are in-bounds
    if not (0 <= x1 < WIDTH):  return False
    if not (0 <= y1 < HEIGHT): return False
    if not (0 <= x2 < WIDTH):  return False
    if not (0 <= y2 < HEIGHT): return False

    # swap order such that x1 <= x2 and y1 <= y2
    if x2 < x1:
        x2 ^= x1
        x1 ^= x2
        x2 ^= x1
    if x2 < x1: print "Swap failure: {}, {}".format(x1, x2)

    if y2 < y1:
        y2 ^= y1
        y1 ^= y2
        y2 ^= y1
    if y2 < y1: print "Swap failure: {}, {}".format(y1, y2)

    # check that only one of the deltas is = 1
    dx = x2 - x1
    dy = y2 - y1

    if dx and dy:       return False
    if not (dx or dy):  return False
    if dx > 1:          return False
    if dy > 1:          return False

    #print "<{}, {}>, <{}, {}>".format(x1, y1, x2, y2)

    if dx > 0:
        try: grid[x1][y1].remove(R)
        except: pass
        try: grid[x2][y2].remove(L)
        except: pass
    if dy > 0:
        try: grid[x1][y1].remove(D)
        except: pass
        try: grid[x2][y2].remove(U)
        except: pass

    return True

def newGrid():

    grid = [[[] for y in xrange(HEIGHT)] for x in xrange(WIDTH)]

    for x in xrange(WIDTH):
        for y in xrange(HEIGHT):
            if x > 0:
                grid[x][y].append(L)
            if x < WIDTH-1:
                grid[x][y].append(R)
            if y > 0:
                grid[x][y].append(U)
            if y < HEIGHT-1:
                grid[x][y].append(D)

    return grid

class walker:

    def __init__(self, grid, mode, draw=False):
        self.x  = 0
        self.y  = 0
        self.dx = WIDTH-1
        self.dy = HEIGHT-1

        self.grid     = grid
        self.mode     = mode
        self.draw     = draw
        self.numSteps = 0

        self.initGrid()

    def initGrid(self):
        if self.mode == 0:
            #pass
            if self.draw: drawGrid(grid)

        elif self.mode == 1:

            for y in xrange(HEIGHT-1):
                if y % 2 == 0:
                    for x in xrange(WIDTH - 1):
                        delEdge(grid, x, y, x, y+1)
                else:
                    for x in xrange(1, WIDTH):
                        delEdge(grid, x, y, x, y+1)
            if self.draw: drawGrid(grid)

        elif self.mode == 2:
            for y in xrange(HEIGHT/2):
                if y % 2 == 0:
                    for x in xrange(1, WIDTH-1):
                        delEdge(grid, x, y, x, y+1)
                else:
                    for x in xrange(2, WIDTH):
                        delEdge(grid, x, y, x, y+1)
            for y in xrange(HEIGHT/2, HEIGHT-1):
                if y%2 == 0:
                    for x in xrange(1, WIDTH-1):
                        delEdge(grid, x, y, x, y+1)
                else:
                    for x in xrange(0, WIDTH-2):
                        delEdge(grid, x, y, x, y+1)
            for y in xrange(1, HEIGHT-1):
                midpoint = HEIGHT/2
                if HEIGHT % 4 == 0: 
                    midpoint = HEIGHT/2 + 1
                if y < midpoint:
                    delEdge(grid, 0, y, 1, y)
                else:
                    delEdge(grid, WIDTH-1, y, WIDTH-2, y)
            if self.draw: drawGrid(grid)

    def walk(self):
        self.numSteps += 1
        choices = grid[self.x][self.y]
        direction = random.choice(choices)
        #print (self.x, self.y), grid[self.x][self.y], direction
        if direction   == L: self.x -= 1
        elif direction == U: self.y -= 1
        elif direction == R: self.x += 1
        elif direction == D: self.y += 1

    def main(self):
        hasBlocked = False
        while (self.x, self.y) != (self.dx, self.dy):
            #print (self.x, self.y), (self.dx, self.dy)
            self.walk()
            if self.mode == 2:
                if not hasBlocked:
                    if (self.x, self.y) == (WIDTH-2, HEIGHT-1):
                        delEdge(self.grid, WIDTH-2, HEIGHT-1, WIDTH-1, HEIGHT-1)
                        hasBlocked = True
                    elif (self.x, self.y) == (WIDTH-1, HEIGHT-2):
                        delEdge(self.grid, WIDTH-1, HEIGHT-1, WIDTH-1, HEIGHT-2)
                        hasBlocked = True

        return self.numSteps

def drawGrid(grid):
    size = 3
    turtle.speed(0)
    turtle.delay(0)
    turtle.ht()
    for x in xrange(WIDTH):
        for y in xrange(HEIGHT):
            dirs = grid[x][y]
            for dir in dirs:
                if dir == L:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos(((x-1)*4, y*4))
                elif dir == R:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos(((x+1)*4, y*4))
                elif dir == U:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos((x*4, (y-1)*4))
                elif dir == D:
                    turtle.pu()
                    turtle.setpos((x*4, y*4))
                    turtle.pd()
                    turtle.setpos((x*4, (y+1)*4))
    turtle.mainloop()

numTrials  = 100
totalSteps = 0.0
i = 0
try:
    while i < numTrials:
        grid = newGrid()

        w = walker(grid, 2)
        steps = w.main()
        totalSteps += steps
        print steps, totalSteps/(i+1)
        i += 1

    print totalSteps / numTrials

except KeyboardInterrupt:
    print totalSteps / i

Rohdaten: (aktuelle AnzahlSchritte, laufender Durchschnitt)

358796490 358796490.0
49310430 204053460.0
106969130 171692016.667
71781702 146714438.0
49349086 127241367.6
40874636 112846912.333
487607888 166384194.571
56423642 152639125.5
71077302 143576700.667
101885368 139407567.4
74423642 133499937.818
265170542 144472488.167
59524778 137938048.923
86919630 134293876.143
122462528 133505119.6
69262650 129489965.25
85525556 126903823.529
161165512 128807250.667
263965384 135920836.632
128907594 135570174.5
89535930 133378067.619
97344576 131740181.636
98772132 130306788.174
140769524 130742735.5
198274280 133443997.28
95417374 131981434.846
226667006 135488307.852

stokastisch
quelle

Ich habe die Grafikgröße auf 20 mal 20 reduziert, um die Laufzeiten zu verkürzen. Ich hoffe, es hilft.

Sie gewinnen gerade :)

Ist Ihre 20 mal 20 Punktzahl über 1000 Läufe?

@Lembik ja das ist es.

Stokastic

1

@ Tennis au Contraire :)

Sparr

6

4-Wege-Ansatz, 213k

Der Einweg-Ansatz ist

Gerade Linie von S nach E

und erzielt einen Durchschnitt von N^2.

Der Zwei-Wege-Ansatz ist

Schleife mit S und E gegenüber

Aber das erste Mal, wenn der Betrunkene den Endpunkt erreicht, ist er abgeschnitten:

Die Schleife wird geschnitten, um eine gekrümmte Linie von S nach E zu erhalten

Es erzielt einen Durchschnitt von (N/2)^2 + N^2.

Der Vier-Wege-Ansatz verwendet zwei Schnitte:

Verschachtelte Schleifen, verbunden in zwei Gabeln, eine auf beiden Seiten von E Schneiden Sie eine der Gabeln auf der E-Seite Schneiden Sie auf der anderen Seite die Gabel nicht auf der E-Seite. Dies hinterlässt einen verschlungenen Weg

Angenommen, die äußere Schleife ist lang xNund die innere Schleife ist lang (1-x)N. Der Einfachheit halber normalisiere ich auf N=1.

Vom Start bis zum ersten Schnitt ergibt sich ein Durchschnitt von (x/2)^2. Vom ersten bis zum zweiten Schnitt stehen zwei Optionen zur Verfügung: Länge xund Länge 1-x. das ergibt einen Durchschnitt von (1-x)x^2 + x(1-x)^2 = x-x^2. Schließlich gibt der verbleibende Pfad 1. Die Gesamtpunktzahl ist also N^2 (1 + x - 3/4 x^2).

Anfangs ging ich davon aus, dass es optimal wäre, die verfügbaren Pfade bei jedem Schritt gleich lang zu halten, und mein ursprünglicher Ansatz verwendete x = 1/2eine Punktzahl von 1.3125 N^2. Aber nach der obigen Analyse stellt sich heraus, dass die optimale Aufteilung gegeben ist, wenn x = 2/3mit der Punktzahl 1.3333 N^2.

~~1000 walks with average 210505.738 in 202753ms~~

1000 walks with average 212704.626 in 205191ms

mit Code

import java.awt.Point;
import java.util.*;

// http://codegolf.stackexchange.com/q/37484/194
public class RandomWalker {
    private static final int SIZE = 19;
    private static final Point dest = new Point(SIZE, SIZE);

    private final Random rnd = new Random();
    private Point p = new Point(0, 0);
    private int step = 0;
    private Set<Set<Point>> edges;
    private Map<Set<Point>, String> cuttableEdgeNames;
    private Set<String> cutSequences;
    private String cutSequence = "";

    public static void main(String[] args) {
        long start = System.nanoTime();
        long total = 0;
        int walks = 0;
        while (walks < 1000 && total < 1L << 40) {
            RandomWalker rw = new RandomWalker();
            total += rw.walk();
            walks++;
        }

        long timeTaken = System.nanoTime() - start;
        System.out.println(walks + " walks with average " + total / (double)walks + " in " + (timeTaken / 1000000) + "ms");
    }

    RandomWalker() {
        loadMaze(
            "+-+ +-+ +-+ +-+ +-+ +-+ +-+-+-+-+-+-+-+",
            "| | | | | | | | | | | | |             |",
            "+ + + + + + + + + + + + + +-+ +-+ +-+ +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + +-+ + + + + + + +",
            "| | | | | | | | | | |     | | | | | | |",
            "+ + + + + + + + + + + +-+-+ + + + + + +",
            "| | | | | | | | | | | |     | | | | | |",
            "+ + + + + + + + + + + + +-+ + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ +-+ +-+ +-+ +-+ +-+ + + + + + + + + +",
            "|                     | | | | | | | | |",
            "+ +-+ +-+ +-+ +-+ +-+ + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + + + + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | |",
            "+ + + + + + + + + + + +-+ + + + + + + +",
            "| | | | | | | | | | |     | | | | | | |",
            "+ + + + + + + + + + + +-+ + + + + + + +",
            "| | | | | | | | | | | | | | | | | | | d",
            "+ + + + + + + + + + + + + + +-+ +-+ +c+",
            "| | | | | | | | | | | | | |           |",
            "+ + + + + + + + + + + + + +-+-+-+-+-+ +",
            "| | | | | | | | | | | | |           f b",
            "+-+ +-+ +-+ +-+ +-+ +-+ +-+-+-+-+-+e+a+"
        );
        cutSequences = new HashSet<String>();
        cutSequences.add("ac");
        cutSequences.add("ad");
        cutSequences.add("be");
        cutSequences.add("bf");
    }

    private void loadMaze(String... row) {
        edges = new HashSet<Set<Point>>();
        cuttableEdgeNames = new HashMap<Set<Point>, String>();

        // Horizontal edges
        for (int y = 0; y <= SIZE; y++) {
            for (int x0 = 0; x0 < SIZE; x0++) {
                char ch = row[y * 2].charAt(x0 * 2 + 1);
                if (ch == ' ') continue;
                Set<Point> edge = new HashSet<Point>();
                edge.add(new Point(x0, y));
                edge.add(new Point(x0 + 1, y));
                edges.add(edge);
                if (ch != '-') cuttableEdgeNames.put(edge, "" + ch);
            }
        }

        // Vertical edges
        for (int y0 = 0; y0 < SIZE; y0++) {
            for (int x = 0; x <= SIZE; x++) {
                char ch = row[y0 * 2 + 1].charAt(x * 2);
                if (ch == ' ') continue;
                Set<Point> edge = new HashSet<Point>();
                edge.add(new Point(x, y0));
                edge.add(new Point(x, y0 + 1));
                edges.add(edge);
                if (ch != '|') cuttableEdgeNames.put(edge, "" + ch);
            }
        }
    }

    int walk() {
        while (!p.equals(dest)) {
            List<Point> neighbours = neighbours(p);
            int idx = rnd.nextInt(neighbours.size());
            p = neighbours.get(idx);
            step++;
        }

        return step;
    }

    List<Point> neighbours(Point p) {
        List<Point> rv = new ArrayList<Point>();
        if (p.x > 0) handlePossibleNeighbour(rv, p, new Point(p.x - 1, p.y));
        if (p.x < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x + 1, p.y));
        if (p.y > 0) handlePossibleNeighbour(rv, p, new Point(p.x, p.y - 1));
        if (p.y < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x, p.y + 1));
        return rv;
    }

    private void handlePossibleNeighbour(List<Point> neighbours, Point p1, Point p2) {
        if (edgeExists(p1, p2)) neighbours.add(p2);
    }

    private boolean edgeExists(Point p1, Point p2) {
        Set<Point> edge = new HashSet<Point>();
        edge.add(p1);
        edge.add(p2);

        // Is it cuttable?
        String id = cuttableEdgeNames.get(edge);
        if (id != null) {
            String prefix = cutSequence + id;
            for (String seq : cutSequences) {
                if (seq.startsWith(prefix)) {
                    // Cut it
                    cutSequence = prefix;
                    edges.remove(edge);
                    return false;
                }
            }
        }

        return edges.contains(edge);
    }
}

Peter Taylor
quelle

Ah, ich verstehe, deshalb funktioniert mein Inselansatz nicht, ich habe die Pfadlänge nicht ausgeglichen. Um mein Verständnis zu verdeutlichen, geht fes cin Ihrem Code um die Länge von bis N/2, ob durch e(und d) oder nicht, oder?

Nur die Hälfte des

Wie ist die Pfadlänge N anstatt der Länge N / 2?

Sparr

@justhalf, ja. Es gibt 400 Eckpunkte, also 401 Kanten (nach einem Schnitt ist der Graph ein Hamilton-Zyklus); Die beiden äußeren Pfade haben jeweils 100 Kanten, und die innere Schleife hat daher 101 Kanten.

Peter Taylor

Ich habs. Zwei Beobachtungen: a) Größere Labyrinthe würden von größeren 2 ^ n-Pfaden profitieren. b) Wenn Sie Ihre Pfadlänge dynamisch gestalten, werden Sie die derzeitigen Spitzenreiter mit dynamischen Zwei-Pfad-Lösungen schlagen (ich und @justhalf)

Sparr

@Sparr: Ist es N^2nicht 2^N. Und ja, wenn Sie diese Dynamik optimieren, besteht die Herausforderung darin, sie unter Beibehaltung der Vierpfadeigenschaft zu dynamisieren. @ PeterTaylor: Schöne Bilder!

Nur die Hälfte des

5

Ich experimentierte damit, das Raster fast über alle kZeilen hinweg aufzuteilen. Dies wandelt es effektiv in etwas um, das einem zufälligen Spaziergang kdurch ein N * N/kGitter ähnelt . Am effektivsten ist es, jede Reihe in Scheiben zu schneiden, damit wir den Betrunkenen zum Zickzack zwingen.

Für den 20x20 Fall ( SIZE=19) habe ich

time java RandomWalker 
1000 walks with average 148577.604

real    0m14.076s
user    0m13.713s
sys     0m0.360s

mit Code

import java.awt.Point;
import java.util.*;

// http://codegolf.stackexchange.com/q/37484/194
// This handles a simpler problem where the grid is mutilated before the drunkard starts to walk.
public class RandomWalker {
    private static final int SIZE = 19;
    private final Random rnd = new Random();

    public static void main(String[] args) {
        RandomWalker rw = new RandomWalker();
        long total = 0;
        int walks = 0;
        while (walks < 1000 && total < 1L << 40) {
            total += rw.walk();
            walks++;
        }

        System.out.println(walks + " walks with average " + total / (double)walks);
    }

    int walk() {
        Point dest = new Point(SIZE, SIZE);
        Point p = new Point(0, 0);
        int step = 0;

        while (!p.equals(dest)) {
            List<Point> neighbours = neighbours(p);
            int idx = rnd.nextInt(neighbours.size());
            p = neighbours.get(idx);
            step++;
        }

        return step;
    }

    List<Point> neighbours(Point p) {
        List<Point> rv = new ArrayList<Point>();
        if (p.x > 0) handlePossibleNeighbour(rv, p, new Point(p.x - 1, p.y));
        if (p.x < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x + 1, p.y));
        if (p.y > 0) handlePossibleNeighbour(rv, p, new Point(p.x, p.y - 1));
        if (p.y < SIZE) handlePossibleNeighbour(rv, p, new Point(p.x, p.y + 1));
        return rv;
    }

    private void handlePossibleNeighbour(List<Point> neighbours, Point p1, Point p2) {
        if (edgeExists(p1, p2)) neighbours.add(p2);
    }

    private boolean edgeExists(Point p1, Point p2) {
        return p1.x != p2.x || p1.x == SIZE * (Math.max(p1.y, p2.y) & 1);
    }
}

Peter Taylor
quelle

Habe ich Recht, wenn ich davon ausgehe, dass alle Kanten gelöscht werden, bevor der Lauf in Ihrer Lösung beginnt?

@ Lembik, ja. Ich dachte, der Kommentar oben würde das klar machen.

Peter Taylor

Es tut, danke. Ich frage mich, wie viel Unterschied Sie machen können, wenn Sie Kanten während des Spaziergangs löschen.

Wie lange dauert der Lauf aus Neugier (insgesamt und pro Lauf)?

Stokastic

@stokastic, ungefähr 3 Sekunden pro Lauf.

Peter Taylor

3

Für alle, die das Rad nicht neu erfinden wollen

Mach dir keine Sorgen! Ich werde es für dich neu erfinden :)

Das ist übrigens in Java.

Ich habe eine Walker-Klasse erstellt, die sich mit dem zufälligen Gehen befasst. Es enthält auch eine hilfreiche Methode, um festzustellen, ob ein Zug gültig ist (wenn er bereits ausgeführt wurde).

Ich gehe davon aus, dass alle von euch klugen Leuten herausfinden können, ob sie Zufallszahlen für den Konstruktor eingeben können. Ich habe es Ihnen überlassen, damit Sie bestimmte Fälle testen können. Rufen Sie einfach die Funktion walk () auf, um den Betrunkenen (zufällig) zum Laufen zu bringen (Sie haben es erraten!).

Ich werde die Funktion canComeHome () ein anderes Mal implementieren. Am besten, nachdem ich nachgeschlagen habe, wie ich das am besten mache.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeSet;

public class Walker {
    int width,height;
    int x,y; //walker's position (does anyone else keep thinking about zombies?!?)
    int dX,dY; //destination
    TreeSet<Edge> pathsNoLongerAvailable = new TreeSet<Edge>();
    TreeSet<Edge> previouslyTraveled = new TreeSet<Edge>();
    int stepCount = 0;

    public static void main(String[]args){
        int side = 10;
        Walker walker = null;
        int total = 0;
        double count = 1000;
        for(int i=0; i<count; i++){
            walker = new Walker(0,0,side,side,side-1,side-1);
            total += walker.stepCount;
            System.out.println("Iteration "+i+": "+walker.stepCount);
        }
        System.out.printf("Average: %.3f\n", total/count);
        walker.printPath();
    }

    public Walker(int startingX,int startingY, int Width, int Height, int destinationX, int destinationY){
        width = Width;
        height = Height;
        dX = destinationX;
        dY = destinationY;
        x=startingX;
        y=startingY;
        while(!walk()){
            // Do something
        }
    }

    public void printPath(){
        for(int i=0; i<width-1; i++){
            if(!pathsNoLongerAvailable.contains(new Edge(i,height-1,i+1,height-1))){
                System.out.print(" _");
            } else {
                System.out.print("  ");
            }
        }
        System.out.println();
        for(int i=height-2; i>=0; i--){
            for(int j=0; j<2*width-1; j++){
                if(j%2==0){
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2,i+1))){
                        System.out.print("|");
                    } else {
                        System.out.print(" ");
                    }
                } else {
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2+1,i))){
                        System.out.print("_");
                    } else {
                        System.out.print(" ");
                    }
                }
            }
            System.out.println();
        }
    }

    public boolean walk(){
        ArrayList<int[]> possibleMoves = new ArrayList<int[]>();
        if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
            possibleMoves.add(new int[]{-1,0});
        }
        if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
            possibleMoves.add(new int[]{1,0});
        }
        if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
            possibleMoves.add(new int[]{0,-1});
        }
        if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
            possibleMoves.add(new int[]{0,1});
        }
        int random = (int)(Math.random()*possibleMoves.size());
        int[] move = possibleMoves.get(random);
        previouslyTraveled.add(new Edge(x,y,x+move[0],y+move[1]));
        x+=move[0];
        y+=move[1];
        stepCount++;
        if(x==dX && y == dY){
            return true;
        } else {
            return false;
        }
    }

    public boolean isSolvable(){
        TreeSet<Point> reachable = new TreeSet<Point>();
        Queue<Point> next = new LinkedList<Point>();
        next.offer(new Point(x,y));
        reachable.add(new Point(x,y));
        while(next.size()>0){
            Point cur = next.poll();
            int x = cur.x;
            int y = cur.y;
            ArrayList<Point> neighbors = new ArrayList<Point>();
            if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
                neighbors.add(new Point(x-1, y));
            }
            if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
                neighbors.add(new Point(x+1, y));
            }
            if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
                neighbors.add(new Point(x, y-1));
            }
            if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
                neighbors.add(new Point(x, y+1));
            }
            for(Point neighbor: neighbors){
                if(!reachable.contains(neighbor)){
                    if(neighbor.compareTo(new Point(dX, dY))==0){
                        return true;
                    }
                    reachable.add(neighbor);
                    next.offer(neighbor);
                }
            }
        }
        return false;
    }

    public boolean hasBeenWalked(int x1, int y1, int x2, int y2){
        return previouslyTraveled.contains(new Edge(x1, y1, x2, y2));
    }

    public boolean hasBeenWalked(Edge edge){
        return previouslyTraveled.contains(edge);
    }

    public void deletePath(int startX, int startY, int endX, int endY){
        Edge toAdd = new Edge(startX,startY,endX,endY);
        if(hasBeenWalked(toAdd)){
            System.out.println("Edge already travelled!");
            return;
        }
        pathsNoLongerAvailable.add(toAdd);
        if(!isSolvable()){
            pathsNoLongerAvailable.remove(toAdd);
            System.out.println("Invalid deletion!");
        }
    }

    static class Edge implements Comparable<Edge>{
        Point start, end;

        public Edge(int x1, int y1, int x2, int y2){
            start = new Point(x1, y1);
            end = new Point(x2, y2);
            if(start.compareTo(end)>0){
                Point tmp = end;
                end = start;
                start = tmp;
            }
        }

        @Override
        public int compareTo(Edge o) {
            int result = start.compareTo(o.start);
            if(result!=0) return result;
            return end.compareTo(o.end);
        }
    }

    static class Point implements Comparable<Point>{
        int x,y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
        public int compareTo(Point o){
            int result = Integer.compare(x, o.x);
            if(result!=0) return result;
            result = Integer.compare(y, o.y);
            if(result!=0) return result;
            return 0;
        }
    }
}

Stretch Maniac
quelle

Dies enthält einige Fehler und Inkonsistenzen. previouslyTraveled.add(new int[]{x,y,move[0],move[1]})sollte x+move[0]und sein y+move[1]. Die Width-1und Height-1, und Ineffizienz bei der Überprüfung der gelöschten Pfade. Ich habe Ihren Code bearbeitet (mit zusätzlicher Funktion zum Drucken des Labyrinths). Fühlen Sie sich frei, ein Rollback durchzuführen, wenn Sie der Meinung sind, dass dies unangemessen ist.

9.

Ihr Edgeimplementiert nicht richtig Comparable<Edge>. Wenn Sie möchten, dass Kanten als Gleiche verglichen werden, auch wenn Sie sie umkehren, müssen Sie die Umkehrung auch im ungleichen Fall berücksichtigen. Am einfachsten ist es, den Konstruktor so zu ändern, dass die geordneten Punkte erhalten bleiben.

Peter Taylor

@ PeterTaylor: Danke für die Köpfe hoch. Ich dachte ein wenig über den ungleichen Fall nach, brachte mich aber nicht dazu zu verstehen, warum es wichtig ist. Wissen Sie, wo ich nach Implementierungsanforderungen suchen kann Comparable?

Nur die Hälfte des

1

docs.oracle.com/javase/7/docs/api/java/lang/Comparable.html Der Schlüssel ist, dass eine Gesamtreihenfolge definiert werden muss. Aber wenn Aund Bdie gleiche Kante umgekehrt und Cunterschiedlich ist, kann man A.compareTo(B) == B.compareTo(A) == 0aber A.compareTo(C) < 0und bekommen B.compareTo(C) > 0.

Peter Taylor

Wie wäre es jetzt? Ich habe eine weitere Klasse hinzugefügt. Und ich habe die Funktion hinzugefügt, um zu überprüfen, ob es lösbar ist (oder canComeHome())

halbe

3

64,281

Aktualisierung seit Änderung des Rasters von 100x100 auf 20x20 (1000 Tests). Das Ergebnis bei 100 × 100 (100 Tests) betrug ungefähr 36 Millionen.

Während dies keinen 1D-Spaziergang schlagen wird, wollte ich mit einer Idee spielen, die ich hatte.

Die Grundidee ist, dass das Raster in quadratische Räume aufgeteilt ist, von denen jeweils nur ein Pfad nach Hause führt. Der offene Weg ist je nachdem , was der Betrunkene der Nähe von bekommt letzte , was bedeutet er jeden möglichen Ausgang zu erkunden hat, nur alle zu haben , aber einer von ihnen in seinem Gesicht schlug.

Nachdem ich mit den Raumgrößen gespielt hatte, kam ich zu dem gleichen Schluss wie Peter. Kleiner aufzuschneiden ist besser. Die besten Ergebnisse werden mit einer Raumgröße von 2 erzielt.

Average score over 100 trials: 36051265

Der Code ist schlampig, stört das Chaos nicht. Sie können den SHOWSchalter umlegen , und bei jedem SHOW_INTSchritt wird ein Bild der Pfade angezeigt, damit Sie es in Aktion sehen können. Ein abgeschlossener Lauf sieht ungefähr so aus:

Bildbeschreibung hier eingeben

(Dies ist das Bild aus dem vorherigen 100x100-Raster. 20x20 ist genau so, aber auch kleiner. Der folgende Code wurde für neue Größen / Auflagen aktualisiert.)

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Point;
import java.awt.image.*;
import java.util.*;
import javax.swing.*;

public class DrunkWalk {

    boolean SHOW = false;
    int SHOW_INT = 10;
    int SIZE = 20;
    Random rand = new Random();
    Point pos;
    int[][] edges;
    int[][] wally;
    int[] wallx;
    int roomSize = 2;
    JFrame frame;
    final BufferedImage img;

    public static void main(String[] args){
        long total=0,runs=1000;
        for(int i=0;i<runs;i++){
            int steps = new DrunkWalk().run();
            total += steps;
            System.out.println("("+i+") "+steps);
        }
        System.out.println("\n Average " + (total/runs) + " over " + runs + " trials.");
    }

    DrunkWalk(){
        edges = new int[SIZE][SIZE];
        for(int x=0;x<SIZE;x++){
            for(int y=0;y<SIZE;y++){
                if(x>0) edges[x][y] |= WEST;
                if(x+1<SIZE) edges[x][y] |= EAST;
                if(y>0) edges[x][y] |= NORTH;
                if(y+1<SIZE) edges[x][y] |= SOUTH;
            }
        }
        wallx = new int[SIZE/roomSize+1];
        wally = new int[SIZE/roomSize+1][SIZE/roomSize+1];
        pos = new Point(SIZE-1,SIZE-1);
        img = new BufferedImage(SIZE*6+1,SIZE*6+1, BufferedImage.TYPE_INT_RGB);
        frame = new JFrame(){
            public void paint(Graphics g) {
                g.drawImage(img, 50, 50, null);
            }
        };
        frame.setSize(700,700);
        if(SHOW)
            frame.show();
    }

    void draw(){
        try {
            Thread.sleep(200);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        Graphics g = img.getGraphics();
        g.setColor(Color.WHITE);
        g.clearRect(0, 0, img.getWidth(), img.getHeight());
        for(int x=0;x<SIZE;x++){
            for(int y=0;y<SIZE;y++){
                if((edges[x][y]&EAST)==EAST)
                    g.drawLine(x*6, y*6, x*6+5, y*6);
                if((edges[x][y]&SOUTH)==SOUTH)
                    g.drawLine(x*6, y*6, x*6, y*6+5);
            }
        }
        g.setColor(Color.RED);
        g.drawOval(pos.x*6-2, pos.y*6-2, 5, 5);
        g.drawOval(pos.x*6-1, pos.y*6-1, 3, 3);
        frame.repaint();
    }

    int run(){
        int steps = 0;
        Point home = new Point(0,0);
        while(!pos.equals(home)){
            if(SHOW&&steps%SHOW_INT==0){
                System.out.println(steps);
                draw();
            }
            step();
            adversary();
            steps++;
        }
        if(SHOW)
            draw();
        return steps;
    }

    void adversary(){
        int rx = pos.x / roomSize;
        int ry = pos.y / roomSize;
        int maxWalls = roomSize - 1;
        if(wally[rx][ry] < maxWalls){
            if(pos.y%roomSize==0)
                if(delete(pos.x,pos.y,NORTH))
                    wally[rx][ry]++;
        }
        maxWalls = SIZE-1;
        if(pos.x%roomSize==0){
            if(wallx[rx] < maxWalls)
                if(delete(pos.x, pos.y,WEST))
                    wallx[rx]++;


        }       
    }

    void step(){
        List<Integer> choices = getNeighbors(pos);
        Collections.shuffle(choices);
        int dir = choices.get(0);
        pos.x += dir==WEST?-1:dir==EAST?1:0;
        pos.y += dir==NORTH?-1:dir==SOUTH?1:0;
    }

    boolean delete(int x, int y, int dir){
        if((edges[x][y] & dir) != dir)
            return false;
        edges[x][y] -= dir;
        if(dir == NORTH)
            if(y>0) edges[x][y-1] -= SOUTH;
        if(dir == SOUTH)
            if(y+1<SIZE) edges[x][y+1] -= NORTH;
        if(dir == EAST)
            if(x+1<SIZE) edges[x+1][y] -= WEST;
        if(dir == WEST)
            if(x>0) edges[x-1][y] -= EAST;
        return true;
    }

    List<Integer> getNeighbors(Point p){
        if(p.x==SIZE || p.y==SIZE){
            System.out.println("wtf");
            System.exit(0);
        }
        List<Integer> choices = new ArrayList<Integer>();
        if((edges[p.x][p.y] & NORTH) == NORTH)
            choices.add(NORTH);
        if((edges[p.x][p.y] & SOUTH) == SOUTH)
            choices.add(SOUTH);
        if((edges[p.x][p.y] & EAST) == EAST)
            choices.add(EAST);
        if((edges[p.x][p.y] & WEST) == WEST)
            choices.add(WEST);
        return choices;
    }

    final static int NORTH=1,EAST=2,SOUTH=4,WEST=8;
}

Geobits
quelle

Mir ist gerade aufgefallen, dass er von bot / left-> top / right gehen sollte, während meiner von bot / right-> top / left geht. Ich kann es ändern, wenn es wirklich wichtig ist, aber ...

Geobits

Das ist sehr schön und ist die erste dynamische Lösung, die ich denke. Es interessiert mich, dass Ihr Weg noch nicht ganz so lang ist wie der statische.

Wenn mit "nicht ganz so lang" ~ 1/3 so lang wie der eine und ~ 36x so lang wie der andere gemeint ist? : P

Geobits

3

188k, mit 2 Pfaden

Die besten Einträge scheinen alle den Ansatz zu verfolgen, zwei Pfade zu generieren und einen abzuschneiden, wenn sich der Betrunkene dem Ende des Pfades nähert. Ich glaube nicht, dass ich den Einstieg von justhalf schlagen kann, aber ich konnte nicht anders als mich zu fragen: Warum 2 Pfade? Warum nicht 3 oder 5 oder 20?

TL; DR : 2 Pfade scheinen optimal zu sein

Also habe ich ein Experiment gemacht. Basierend auf dem Framework von Stretch Maniac habe ich einen Eintrag geschrieben, um verschiedene Anzahlen von Pfaden zu testen. Sie können den featureSizeParameter anpassen , um die Anzahl der Pfade zu ändern. A featureSizevon 20 gibt 1 Pfad, 10 gibt 2 Pfade, 7 gibt 3, 5 gibt 4 und so weiter.

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.ThreadLocalRandom;

public class Walker {
    final int width,height;
    int x,y; //walker's position (does anyone else keep thinking about zombies?!?)
    final int dX,dY; //destination
    final int featureSize;
    Set<Edge> pathsNoLongerAvailable = new HashSet<>();
    Set<Edge> previouslyTraveled = new HashSet<>();
    int stepCount = 0;
    private final BitSet remainingExits;

    public static void main(String[]args){
        int side = 20;
        Walker walker = null;
        int total = 0;
        int featureSize = 10;
        double count = 1000;
        for(int i=0; i<count; i++){
            walker = new Walker(0,0,side,side,side-1,side-1, featureSize);
            total += walker.stepCount;
            System.out.println("Iteration "+i+": "+walker.stepCount);
        }
        System.out.printf("Average: %.3f\n", total/count);
        walker.printPath();
    }

    public Walker(int startingX,int startingY, int Width, int Height, int destinationX, int destinationY, int featureSize){
        width = Width;
        height = Height;
        dX = destinationX;
        dY = destinationY;
        x=startingX;
        y=startingY;
        this.featureSize = featureSize;

        deleteBars();

        remainingExits = new BitSet();
        for (int yy = 0; yy < height; yy++) {
            if (!pathsNoLongerAvailable.contains(new Edge(width - 2, yy, width - 1, yy))) {
                remainingExits.set(yy);
            }
        }

        while(!walk()){
            if (x == width - 2
                    && remainingExits.get(y)
                    && remainingExits.cardinality() > 1) {
                deletePath(x, y, x + 1, y);
                remainingExits.set(y, false);
            }
        }
    }

    private void deleteBars() {
        for (int xx = 0; xx < width - 1; xx++) {
            for (int yy = 0; yy < height / featureSize + 1; yy++) {
                if (xx != 0) deletePath(xx, featureSize * yy + featureSize - 1, xx, featureSize * yy + featureSize);
                boolean parity = xx % 2 == 0;
                if (yy == 0) parity ^= true; // First path should be inverted
                for (int i = 0; i < featureSize && featureSize * yy + i < height; i++) {
                    if (i == 0 && !parity) continue;
                    if ((i == featureSize - 1 || featureSize * yy + i == height - 1) && parity) continue;
                        deletePath(xx, featureSize * yy + i, xx + 1, featureSize * yy + i);
                }
            }
        }
    }

    public void printPath(){
        for(int i=0; i<width-1; i++){
            if(!pathsNoLongerAvailable.contains(new Edge(i,height-1,i+1,height-1))){
                System.out.print(" _");
            } else {
                System.out.print("  ");
            }
        }
        System.out.println();
        for(int i=height-2; i>=0; i--){
            for(int j=0; j<2*width-1; j++){
                if(j%2==0){
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2,i+1))){
                        System.out.print("|");
                    } else {
                        System.out.print(" ");
                    }
                } else {
                    if(!pathsNoLongerAvailable.contains(new Edge(j/2,i,j/2+1,i))){
                        System.out.print("_");
                    } else {
                        System.out.print(" ");
                    }
                }
            }
            System.out.println();
        }
    }

    public boolean walk(){
        ArrayList<int[]> possibleMoves = new ArrayList<int[]>();
        if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
            possibleMoves.add(new int[]{-1,0});
        }
        if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
            possibleMoves.add(new int[]{1,0});
        }
        if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
            possibleMoves.add(new int[]{0,-1});
        }
        if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
            possibleMoves.add(new int[]{0,1});
        }
        int random = ThreadLocalRandom.current().nextInt(possibleMoves.size());
        int[] move = possibleMoves.get(random);
        previouslyTraveled.add(new Edge(x,y,x+move[0],y+move[1]));
        x+=move[0];
        y+=move[1];
        stepCount++;
        if(x==dX && y == dY){
            return true;
        } else {
            return false;
        }
    }

    public boolean isSolvable(){
        Set<Point> reachable = new HashSet<>();
        Queue<Point> next = new LinkedList<>();
        next.offer(new Point(x,y));
        reachable.add(new Point(x,y));
        while(next.size()>0){
            Point cur = next.poll();
            int x = cur.x;
            int y = cur.y;
            ArrayList<Point> neighbors = new ArrayList<>();
            if(x!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x-1,y))){
                neighbors.add(new Point(x-1, y));
            }
            if(x!=width-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x+1,y))){
                neighbors.add(new Point(x+1, y));
            }
            if(y!=0 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y-1))){
                neighbors.add(new Point(x, y-1));
            }
            if(y!=height-1 && !pathsNoLongerAvailable.contains(new Edge(x,y,x,y+1))){
                neighbors.add(new Point(x, y+1));
            }
            for(Point neighbor: neighbors){
                if(!reachable.contains(neighbor)){
                    if(neighbor.compareTo(new Point(dX, dY))==0){
                        return true;
                    }
                    reachable.add(neighbor);
                    next.offer(neighbor);
                }
            }
        }
        return false;
    }

    public boolean hasBeenWalked(int x1, int y1, int x2, int y2){
        return previouslyTraveled.contains(new Edge(x1, y1, x2, y2));
    }

    public boolean hasBeenWalked(Edge edge) {
        return previouslyTraveled.contains(edge);
    }

    public void deletePath(int startX, int startY, int endX, int endY){
        Edge toAdd = new Edge(startX,startY,endX,endY);
        if(hasBeenWalked(toAdd)){
            System.out.println("Edge already travelled!");
            return;
        }
        pathsNoLongerAvailable.add(toAdd);
        if(!isSolvable()){
            pathsNoLongerAvailable.remove(toAdd);
            System.out.println("Invalid deletion!");
        }
    }

    public static class Edge implements Comparable<Edge>{
        Point start, end;

        public Edge(int x1, int y1, int x2, int y2){
            start = new Point(x1, y1);
            end = new Point(x2, y2);
            if(start.compareTo(end)>0){
                Point tmp = end;
                end = start;
                start = tmp;
            }
        }

        @Override
        public int compareTo(Edge o) {
            int result = start.compareTo(o.start);
            if(result!=0) return result;
            return end.compareTo(o.end);
        }

        @Override
        public String toString() {
            return start.toString() + "-" + end.toString();
        }

        @Override
        public int hashCode() {
            int hash = 7;
            hash = 83 * hash + Objects.hashCode(this.start);
            hash = 83 * hash + Objects.hashCode(this.end);
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Edge other = (Edge) obj;
            if (!Objects.equals(this.start, other.start)) {
                return false;
            }
            if (!Objects.equals(this.end, other.end)) {
                return false;
            }
            return true;
        }


    }

    static class Point implements Comparable<Point>{
        int x,y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
        public int compareTo(Point o){
            int result = Integer.compare(x, o.x);
            if(result!=0) return result;
            result = Integer.compare(y, o.y);
            if(result!=0) return result;
            return 0;
        }
        @Override
        public String toString() {
            return "(" + x + "," + y + ")";
        }

        @Override
        public int hashCode() {
            int hash = 7;
            hash = 23 * hash + this.x;
            hash = 23 * hash + this.y;
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Point other = (Point) obj;
            if (this.x != other.x) {
                return false;
            }
            if (this.y != other.y) {
                return false;
            }
            return true;
        }


    }
}

Es gibt ein paar Optimierungen, die ich tun könnte, aber nicht, und es unterstützt keine der adaptiven Tricks, die nur die Hälfte verwendet.

Hier sind die Ergebnisse für verschiedene featureSizeWerte:

20 (1 path):  156284 
10 (2 paths): 188553
7 (3 paths):  162279
5 (4 paths):  152574
4 (5 paths):  134287
3 (7 paths):  118843
2 (10 paths): 94171
1 (20 paths): 64515

Und hier ist eine Karte mit 3 Pfaden:

 _   _   _   _   _   _   _   _   _    
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| |_| |_| |_| |_| |_| |_| |_| |_| |_| |
|_   _   _   _   _   _   _   _   _   _|
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| |_| |_| |_| |_| |_| |_| |_| |_| |_| |
|  _   _   _   _   _   _   _   _   _  |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
|_| |_| |_| |_| |_| |_| |_| |_| |_| | |

James_pic
quelle

Danke dafür. Es

Warum schneidest du den Pfad unten ab? Sie können den Pfad zwischen dem unteren und dem mittleren Pfad abschneiden, um eine bessere Punktzahl zu erzielen.

Nur die Hälfte des

@justhalf Ja, ich erwarte es würde. Ich entschied mich dagegen, da dies den Code komplizierter gemacht hätte und es in keiner Weise ein Gewinner gewesen wäre.

James_pic

1

Die drei Pfade (unter der Annahme eines optimalen 3-Pfads) sind im Durchschnitt die gleichen wie der einzelne Pfad: Sei Nes die Pfadlänge (das heißt n^2-1), der einzelne Pfad erfordert im Durchschnitt N^2Bewegungen, während die drei Pfade (N/3)^2 + (2N/3)^2 + (2N/3)^2 = N^2plus einige relativ kleine Werte, also drei, sind Paths hat keinen signifikanten Gewinn gegenüber Single Path, geschweige denn Double Path. (Die Berechnung basiert auf dem Wahrscheinlichkeitsergebnis, das angibt, dass zufällige Bewegungen auf einem NN^2

eindimensionalen Längenpfad

@justhalf Schön. Ich hatte Mühe, ein gutes Argument für die ersten Prinzipien zu finden, warum 2 am besten ist, aber das nagelt es.

James_pic

2

131 KB (20 x 20)

Mein erster Versuch war, alle horizontalen Kanten außer der oberen und unteren Reihe zu entfernen. Jedes Mal, wenn der Geher den unteren Rand einer Spalte erreichte, entfernte ich die Kante vor ihm, bis er den unteren Rand jeder Spalte besucht hatte und schließlich in der Lage sein, den Ausgang zu erreichen. Dies führte zu durchschnittlich 1/8 so vielen Schritten wie @ PeterTaylors 1-D-Walk-Ansatz.

Als nächstes habe ich beschlossen, etwas Umständlicheres zu probieren. Ich habe das Labyrinth in eine Reihe verschachtelter hohler Chevrons aufgeteilt und fordere ihn auf, den Umfang jedes Chevrons mindestens 1,5-mal zu durchlaufen. Dies hat eine durchschnittliche Zeit von ca. 131k Schritten.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <math.h>

#define DEBUG 0
#define ROUNDS 10000

#define Y 20
#define X 20
#define H (Y*2+1)
#define W (X*2+1)

int maze[H][W];
int scores[ROUNDS];

int x, y;

void print_maze(){
    char line[W+2];
    line[W+1]=0;
    for(int row=0;row<H;row++) {
        for(int col=0;col<W;col++) {
            switch(maze[row][col]) {
                case 0:
                    line[col]=' ';
                    break;
                case 1:
                    line[col]=row%2?'-':'|';
                    break;
                case 9:
                    line[col]=(row==y*2+1&&col==x*2+1)?'@':' ';
                    break;
            }
        }
        line[W]='\n';
        printf("%s",line);
    }
    printf("%d %d\n",y,x);
}

int main(){
    srand (time(NULL));
    long long total_turns = 0;
    for(int round=0;round<ROUNDS;round++) {
        for (int r=0;r<H;r++) {
            for (int c=0;c<W;c++) {
                if (r==0 || r==H-1 || c==0 || c==W-1) maze[r][c]=0; // edges
                else if (r%2) { // rows with cells and E/W paths
                    if (c%2) maze[r][c] = 9; // col with cells
                    else if (r==1 || r==H-2) maze[r][c]=1; // E/W path on N/Smost row
                    else if (c>r) maze[r][c]=1; // E/W path on chevron perimeter
                    else maze[r][c]=0; // cut path between cols
                } else { // rows with N/S paths
                    if (c%2==0) maze[r][c] = 0; // empty space
                    else if (c==1 || c==W-2) maze[r][c]=1; // N/S path on E/Wmost row
                    else if (r>c) maze[r][c]=1; // N/S path on chevron perimeter
                    else maze[r][c]=0;
                }
            }
        }
        int progress = 0;
        int first_cut = 0;
        x=0;
        y=0;
        if(DEBUG) print_maze();
        long long turn = 0;
        while (x!=X-1||y!=Y-1) {
            if(DEBUG) std::cin.ignore();
            turn++;
            int r = y*2+1;
            int c = x*2+1;
            int exits = maze[r-1][c] + maze[r][c+1] + maze[r+1][c] + maze[r][c-1];
            int exit_choice = -1;
            do {
                if (rand()%exits == 0) {
                    exit_choice = exits;
                    break;
                } else {
                    exits--;
                }
            }while(exits);
            int dx=0, dy=0;
            --exits;
            if (maze[r-1][c]&&!dx&&!dy) {
                if (exits) {
                    --exits;
                } else {
                    dy = -1;
                    dx = 0;
                }
            }
            if (maze[r][c+1]&&!dx&&!dy) {
                if (exits) {
                    --exits;
                } else {
                    dy = 0;
                    dx = 1;
                }
            }
            if (maze[r+1][c]&&!dx&&!dy) {
                if (exits) {
                    --exits;
                } else {
                    dy = 1;
                    dx = 0;
                }
            }
            if (maze[r][c-1]&&!dx&&!dy) {
                if (exits) {
                    --exits;
                } else {
                    dy = 0;
                    dx = -1;
                }
            }
            x+=dx;
            y+=dy;
            if (first_cut==0) {
                if(x==X-1 && y==progress*2+1) {
                    first_cut = 1;
                    maze[y*2+2][x*2+1]=0;
                }
                if(y==Y-1 && x==progress*2+1) {
                    first_cut = 2;
                    maze[y*2+1][x*2+2]=0;
                }
            }
            else if (first_cut==1) {
                if (y==Y-1 && x==progress*2) {
                    maze[y*2+1][x*2+2]=0;
                    progress++;
                    first_cut=0;
                }
                else if (y==Y-2 && x==progress*2+1) {
                    maze[y*2+2][x*2+1]=0;
                    progress++;
                    first_cut=0;
                }
            }
            else if (first_cut==2) {
                if (x==X-1 && y==progress*2) {
                    maze[y*2+2][x*2+1]=0;
                    progress++;
                    first_cut=0;
                }
                else if (x==X-2 && y==progress*2+1) {
                    maze[y*2+1][x*2+2]=0;
                    progress++;
                    first_cut=0;
                }
            }
            if(DEBUG) print_maze();
        }
        // printf("turns:%lld\n",turn);
        scores[round] = turn;
        total_turns += turn;
    }
    long long avg = total_turns/ROUNDS;
    printf("average: % 10lld\n",avg);
    long long var = 0;
    for(int r=0;r<ROUNDS;r++){
        var += (scores[r]-avg)*(scores[r]-avg);
    }
    var/=ROUNDS;
    // printf("variance: %lld\n",var);
    int stddev=sqrt(var);
    printf("stddev:  % 10d\n",stddev);

}

Sparr
quelle

0

Nichts tun

Da sich der Mann willkürlich bewegt, könnte man meinen, dass das Entfernen eines Knotens langfristig nur die Chance erhöht, nach Hause zu kommen.

Schauen wir uns zunächst den eindimensionalen Fall an. Dies kann erreicht werden, indem Knoten entfernt werden, bis Sie einen verschnörkelten Pfad ohne Deadends oder Zyklen erhalten, der (fast) jeden Gitterpunkt besucht. In einem N x NRaster beträgt die maximale Länge eines solchen Pfades L = N*N - 2 + N%2 (98 für ein 10x10-Raster). Das Gehen entlang des Pfades kann durch eine Übergangsmatrix beschrieben werden, wie sie durch erzeugt wird T1d.

(Die leichte Asymmetrie macht es schwierig, eine analytische Lösung zu finden, mit Ausnahme von sehr kleinen oder unendlichen Matrizen, aber wir erhalten eine numerische Lösung schneller, als es ohnehin nötig wäre, die Matrix zu diagonalisieren.)
Der Zustandsvektor hat 1an der Startposition eine einzige und nach KSchritten erhalten (T1d**K) * statewir die Wahrscheinlichkeitsverteilung, in einem bestimmten Abstand vom Start zu sein (das entspricht einer Mittelung über alle2**K möglichen Wege entlang des Pfades!).

Ausführen der Simulation für 10*L**2Schritte und Speichern des letzten Elements des Zustandsvektors nach jedem Schritt, wodurch wir die Wahrscheinlichkeit erhalten, nach einer bestimmten Gesamtanzahl von Schritten das Ziel erreicht zu haben - die kumulative Wahrscheinlichkeitsverteilung cd(t). Wenn wir es differenzieren, erhalten wir die Wahrscheinlichkeit p, das Ziel genau zu einem bestimmten Zeitpunkt zu erreichen. Ermittlung der durchschnittlichen Integrationszeit t*p(t) dt
Die durchschnittliche Zeit bis zum Erreichen des Ziels ist proportional zu L**2einem Faktor, der sehr schnell auf 1 steigt. Die Standardabweichung ist mit etwa 79% der durchschnittlichen Zeit nahezu konstant.
Diese Grafik zeigt die durchschnittliche Zeit bis zum Erreichen des Ziels für verschiedene Pfadlängen (entsprechend den Rastergrößen von 5 x 5 bis 15 x 15). Bildbeschreibung hier eingeben

So sieht die Wahrscheinlichkeit aus, das Ziel zu erreichen. Die zweite Kurve sieht ausgefüllt aus, da die Position bei jedem ungeraden Zeitschritt ungerade ist und daher nicht am Ziel sein kann. Bildbeschreibung hier eingeben

Daraus können wir ersehen, dass die ausgewogene Doppelpfadstrategie hier am besten funktioniert. Bei größeren Gittern, bei denen der Mehraufwand für die Erstellung von Pfaden im Vergleich zu ihrer Größe vernachlässigbar ist, ist es möglicherweise besser, die Anzahl der Pfade zu erhöhen, ähnlich wie Peter Taylor es beschrieben hat, aber die Längen im Gleichgewicht zu halten

Was ist, wenn wir überhaupt keine Knoten entfernen?

Dann hätten wir doppelt so viele begehbare Knoten plus vier mögliche Richtungen anstelle von zwei. Es scheint so, als würde es sehr unwahrscheinlich sein, jemals irgendwohin zu gelangen. Simulationen zeigen jedoch, dass der Mann nach nur 100 Schritten in einem 10x10-Raster mit ziemlicher Wahrscheinlichkeit sein Ziel erreicht. Daher ist es ein vergeblicher Versuch, ihn auf Inseln zu trappen, da Sie einen potenziell N**2langen kurvenreichen Pfad mit einer durchschnittlichen Fertigstellungszeit von N**4für handeln eine Insel, die in N**2Schritten passiert wird

Wahrscheinlichkeit eines Spaziergangs auf 2d Gitter

from numpy import *
import matplotlib.pyplot as plt

def L(N): # maximal length of a path on an NxN grid
    return N*N - 2 + N%2

def T1d(N): # transition along 1d path
    m = ( diag(ones(N-1),1) + diag(ones(N-1),-1) )/2.
    m[1,0] = 1
    m[-2,-1] = 0
    m[-1,-1] = 1
    return m

def walk(stepmatrix, state, N):
    data = zeros(N)
    for i in xrange(N):
        data[i] = state[-1]
        state = dot(stepmatrix, state)
    return data

def evaluate(data):
    rho = diff(data)/data[-1]
    t = arange(len(rho))
    av = sum(rho*t)
    stdev = sum((t-av)**2 * rho)**.5
    print 'average: %f\nstd: %f'%(av, stdev)
    return rho, av, stdev

gridsize = 10
M = T1d(L(gridsize))
initpos = zeros(L(gridsize))
initpos[0] = 1
cd = walk(M, initpos, L(gridsize)**2*5)

plt.subplot(2,1,1)
plt.plot(cd)
plt.title('p of reaching the goal after N steps')
plt.subplot(2,1,2)
plt.plot(evaluate(cd)[0])
plt.title('p of reaching the goal at step N')
plt.show()


''' 
# uncomment to run the 2D simulation
# /!\ WARNING /!\ generates a bunch of images, dont run on your desktop

def links(k,n):
    x = [k-n, k+n]
    if k%n != 0: x.append(k-1)
    if k%n != n-1: x.append(k+1)
    x = [i for i in x if 0<= i <n*n]
    return x

N = 10 # gridsize    

MM = zeros((N*N, N*N)) # build transition matrix
for i in range(N*N):
    temp = links(i,N)
    for j in temp: MM[i,j] = 1./len(temp)
MM[:,-1] = zeros(N*N)
MM[-1,-1] = 1

pos = zeros(N*N)
pos[0] = 1
for i in range(N*N):
    plt.imsave('grid_%.2d'%i, kron(pos.reshape((N,N)), ones((10,10))), cmap='gray')
    pos = dot(MM, pos)
'''

DenDenDo
quelle

+1 für Mühe und schöne Grafiken. Dies beantwortet jedoch nicht die Frage, und die ersten beiden Wörter widersprechen dem Ergebnis Ihrer Analyse. Und Sie sollten die Achsen Ihrer Diagramme wirklich beschriften. Für welche Rastergröße ist Ihr Wahrscheinlichkeitsgraph anwendbar?

Nur die Hälfte des

Schöne Bilder, aber ich bin mir nicht sicher, ob Sie die richtige Frage haben. Zum Beispiel "Da sich der Mann willkürlich bewegt, könnte man meinen, dass das Entfernen eines Knotens seine Chance erhöht, langfristig nach Hause zu kommen." 1) Der Mann wird immer irgendwann nach den festgelegten Regeln nach Hause kommen, so dass dies nicht relevant zu sein scheint, und 2) wir entfernen Kanten, nicht Knoten.

Wie man einen Säufer auf dem Heimweg bremst

Antworten:

230.794,38 auf 20x20, 100k Läufen

Vorherige Einsendungen

Experimente Abschnitt

Einzelner Pfad

Insel (Stufe 0)

Doppelter Pfad

Insel (Stufe 1)

Insel (Stufe 2)

Insel (Stufe 3)

Insel (Stufe 4)

Fazit

Code

227934 (20 x 20)

135.488.307,9 für 98 x 98

199094.3 für 20x20

4-Wege-Ansatz, 213k

Für alle, die das Rad nicht neu erfinden wollen

64,281

188k, mit 2 Pfaden

131 KB (20 x 20)

Nichts tun

Was ist, wenn wir überhaupt keine Knoten entfernen?