Lösen des Labyrinths mit Python-Ergänzung zu Kapitel 6 der Algorithmus-Kurzreferenz-

Überblick

Dies ist eine Reihe von Büchern zu lesen, verschiedene Dinge neu zu studieren und zu schreiben, woran Sie interessiert sind. Diesmal [Algorithmus-Kurzreferenz](http://www.amazon.co.jp/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82% BA% E3% 83% A0% E3% 82% AF% E3% 82% A4% E3% 83% 83% E3% 82% AF% E3% 83% AA% E3% 83% 95% E3% 82% A1% E3% 83% AC% E3% 83% B3% E3% 82% B9-George-T-Heineman / dp / 4873114284) Das Thema lautet "Graph-Algorithmus" in Kapitel 6. Insbesondere wurde es ein Kapitel, um das Labyrinth in Python zu lösen. Wie ist es passiert.

Wie man das Labyrinth löst

Vor

Es wird erklärt, wie ein Verzweigungspunkt in ein Diagramm mit Knoten konvertiert und gelöst wird. Das stimmt, aber wenn es darum geht, "ein bestimmtes Labyrinth auf ein Diagramm zu reduzieren", wurde nur über die Art und Weise gesprochen, wie Menschen es tun. Lassen Sie uns also überlegen, ein Diagramm zu erstellen, indem Sie die folgende Abbildung (Zeichenkette) eingeben, die das Labyrinth so weit wie möglich kopiert hat.

maze_input.txt

$$$$$$$$$$$$$$$$$
$   $   $       $
$ $ $ $ $ $$$$$ $
$ $ $ $ $ $   $ $
$ $ $ $$$ $ $ $ $
$ $ $   $ $ $   $
$ $ $ $ $ $ $$$$$
$ $ $ $ $t$   $ $
$ $$$ $ $$$ $ $ $
$     $     $ $ $
$ $$$ $ $$$ $ $ $
$ $   $ $   $   $
$$$ $$$$$ $$$ $ $
$   $         $ $
$ $$$ $$$$$$$$$ $
$    s          $
$$$$$$$$$$$$$$$$$

Es ist sehr verwirrend, aber es gibt s und t, die den Start- und Zielpunkten entsprechen. Die Methode zum Erstellen der unteren Zeichenfolge aus der oberen Abbildung besteht darin, ** die Quadrate zu erweitern und zu verbinden, wobei zu berücksichtigen ist, dass die Quadrate tatsächlich zwischen den einzelnen Quadraten im Labyrinthdiagramm verborgen sind **. Mit anderen Worten

• Die Spalten 2 und 2j in der Zeichenfolge unten entsprechen den Spalten i und j in der obigen Abbildung.
• Andere Positionen in der unteren Zeichenfolge (z. B. das $ -Symbol in 3 Zeilen und 3 Spalten) sind die schwarze Linie in der obigen Abbildung oder die zwischen den Quadraten verborgene "Passage", wenn keine Wand vorhanden ist. Entspricht

Sie können eine solche Antwort hinzufügen. Mit anderen Worten, wenn es gitterartige Quadrate gibt, können Sie sich zwei Arten der Platzierung vorstellen: wie man die Steine auf dem Go-Brett platziert und wie man die Teile auf dem Shogi-Brett platziert. Indem ich diese kombinierte, entschied ich mich, entweder (1) die Mitte des Quadrats, (2) den Mittelpunkt der Seite oder den Schnittpunkt von (3) der Seite als "einen Ort, an dem Steine und Stücke platziert werden können" zu betrachten. Wenn sich an dieser "Stelle, an der Steine und Stücke platziert werden können" eine schwarze Linie befindet, können Sie diese erhalten, indem Sie die Korrespondenz "$", andernfalls "" erstellen.

Machen Sie ein Diagramm

Nun, die Einführung ist lang geworden, aber ich werde ein Programm in Python schreiben, das eine Grafik aus diesem Labyrinth erhält.

CreateGraph.py

#Stellen Sie das Labyrinth grafisch dar: im Wesentlichen Tiefensuche
import itertools as it

def isWall(s):
    return 1 if s == '$' else 0

def getWalls(arr, i, j):
    return isWall(arr[i+1][j]) + isWall(arr[i-1][j]) + isWall(arr[i][j+1]) + isWall(arr[i][j-1])

def getEdge(arr, i, j, edges, v, c):
    for (a,b) in zip([1,-1,0,0], [0,0,1,-1]):
        if isWall(arr[i+a][j+b]) == 0:
            arr[i+a][j+b] = '$'
            if arr[i+2*a][j+2*b] == 0:
                vn = v
                cn = c + 1
            else:
                vn = arr[i+2*a][j+2*b]
                edges.append((v, vn, c))
                cn = 1
            getEdge(arr, i+2*a, j+2*b, edges, vn, cn)

vs = 0
edges = list()
arr = list()
for line in open('maze_input.txt', 'r'):
    arr.append(list(line))
height = len(arr)
width = len(arr[height - 1])
cellidi = range(1,width,2)
cellidj = range(1,height,2)
for i,j in it.product(cellidi, cellidj):
    if getWalls(arr, i, j) == 2:
        arr[i][j] = 0
    elif arr[i][j] == ' ':
        vs += 1
        arr[i][j] = vs

#Einstellungen für diese Daten
getEdge(arr, 3, 7, edges, 1, 1)

Eine Funktion namens getEdge ist im Wesentlichen eine Suche mit Tiefenpriorität und verarbeitet die angrenzenden Zellen einfach rekursiv. Ob die Masse bereits verarbeitet wurde oder nicht, wird so geschrieben, wie es in der Liste arr steht, die die Karte enthält. Außerdem habe ich mich bei diesem Vorgang dazu entschlossen, "Seitenlänge" = "Anzahl der Quadrate bis zur nächsten Kreuzung oder Sackgasse" zu berechnen.

Visualisierung von Labyrinthgraphen

Da es eine große Sache ist, lassen Sie uns dies visualisieren.

Visualize.py

#Visualisierung
import networkx as nx
import matplotlib.pyplot as plt
import math

G = nx.Graph()
srcs, dests = zip(* [(fr, to) for (fr, to, d) in edges])
G.add_nodes_from(srcs + dests)

for (s,r,d) in edges:
    G.add_edge(s, r, weight=20/math.sqrt(d))

pos = nx.spring_layout(G)

edge_labels=dict([((u,v,),d)
             for u,v,d in edges])

plt.figure(1)
nx.draw_networkx(G, pos, with_labels=True)
nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_labels)

plt.axis('equal')
plt.show()

Im Vergleich zum ursprünglichen Labyrinth scheint die Positionsbeziehung leicht gedreht zu sein. Wenn Sie sie jedoch anhand der Positionsbeziehung von s und t erfassen, können Sie sehen, dass es sich um eine Grafik handelt, die eine Transkription des ursprünglichen Labyrinths darstellt. .. Natürlich ist es der gleiche Typ wie die Abbildung im Buch. (Mit Ausnahme der Namen der Eckpunkte!)

Suche nach Breitenpriorität in diesem Diagramm

Nachdem wir nun ein Diagramm haben, ignorieren wir die Gewichtung (tatsächliche Entfernung) dieses Diagramms und berechnen die Tiefe nur basierend auf der Anzahl der Knoten.

BreadthFirst.py

#Suche nach Breitenpriorität
import copy

#Definition der Nachbarschaft und der verwendeten Flagge (Generation)
verts = range(1,vs + 1)
verts.append('s')
verts.append('t')
neighbor = {}
used = {}
used['t'] = 0
for v in verts:
    neighbor[v] = {}
    used[v] = 0
used['s'] = 1
for (s, t, d) in edges:    
    neighbor[s][t] = d
    neighbor[t][s] = d

queue = list()
queue.append('s')
while len(queue) > 0:
    t = queue.pop(0)
    for n in neighbor[t]:
        if used[n] == 0:
            used[n] = used[t] + 1
            queue.append(n)

used

Sie erhalten eine Ausgabe ähnlich der folgenden: (Zeilenumbrüche weglassen)

Ergebnis

{1: 4, 2: 3, 3: 4, 4: 4, 5: 3, 6: 3, 7: 2, 8: 4, 9: 3, 10: 4, 
 11: 5, 12: 3, 13: 2, 14: 2, 's': 1, 't': 5}

Jetzt können Sie die "Generation" jedes Knotens = Schnittpunkt sehen, wenn s die erste Generation ist. Es ist ein Wert, der als Index verwendet werden kann, um zu sagen: "Wie oft sollte ich mich verlaufen, bevor ich dort ankomme?"

Suchen Sie in diesem Diagramm nach der kürzesten Route (naiver Dyxtra-Algorithmus)

Im Originalbuch wird es mit einem gerichteten Diagramm berechnet. Wenn Sie sich jedoch ein ungerichtetes Diagramm als Diagramm mit Kanten in beide Richtungen vorstellen, können Sie den Dyxtra-Algorithmus genauso anwenden. Hier möchte ich den kürzesten Abstand von s nach t mit einem naiven Dyxtra-Algorithmus berechnen, der einfach zu implementieren ist.

Dijkstra.py

#Berechnung der kürzesten Kostenroute nach der Dyxtra-Methode
costs = {}
# costs[v] = (cost, prev, used)Ein Paar
for v in verts:
    costs[v] = (float("inf"),0,0)
costs['s'] = (0,-1,0)

queue = list()
queue.append('s')
while len(queue) > 0:
    t = queue.pop(0)
    costs[t] = (costs[t][0], costs[t][1], 1)
    for n in neighbor[t]:
        if costs[n][2] == 0 and costs[n][0] > neighbor[t][n] + costs[t][0]:
            costs[n] = (neighbor[t][n] + costs[t][0], t, 0)
    #Es wird schneller sein, wenn Sie einen Weg finden, es in die Warteschlange zu stellen, aber hier werde ich nur einen niedrigsten Wert in die Warteschlange stellen
    mincost = float("inf")
    minv = 's'
    for v in verts:
        if mincost > costs[v][0] and costs[v][2] == 0:
            mincost = costs[v][0] 
            minv = v
    if minv != 's':
        queue.append(minv)

Ergebnis

{1: (13, 2, 1),
 2: (9, 7, 1),
 3: (17, 6, 1),
 4: (7, 9, 1),
 5: (9, 13, 1),
 6: (9, 7, 1),
 7: (7, 's', 1),
 8: (8, 9, 1),
 9: (6, 14, 1),
 10: (10, 6, 1),
 11: (9, 8, 1),
 12: (6, 14, 1),
 13: (7, 's', 1),
 14: (3, 's', 1),
 's': (0, -1, 1),
 't': (20, 4, 1)}

Eine ziemlich gute Implementierung in der Warteschlange, die jedoch das richtige Ergebnis zurückgibt, da bei jeder Verarbeitung nur der Scheitelpunkt mit den niedrigsten Kosten angehängt wird. Das Ausgabeergebnis ist beispielsweise "(20, 4, 1)", wenn Sie auf die Linie "t" schauen, aber der Abstand (Schritte) zum Ziel beträgt 20 und der vorherige Schnittpunkt ist "4". Es bedeutet, dass es der Ort ist, der durch dargestellt wird. Auf diese Weise kann nicht nur die Entfernung, sondern auch die kürzeste Route selbst ermittelt werden. Ich bin glücklich.

Übrigens, als ich diesen Artikel zum ersten Mal schrieb, habe ich ernsthaft versucht, Python zu verwenden, und über Folgendes nachgedacht.

――Es ist recht einfach, Taples zu verwenden

• Es ist sehr schwierig, mit [0] oder [2] auf den Taple zuzugreifen (dies bedeutet nicht, dass Python schlecht ist).

Ich fragte mich, ob es richtig als etwas Strukturelles definiert werden sollte, wenn man es wie eine richtige Struktur verwendet, anstatt es mit "für" zu kombinieren.

Das Ende

Andere Algorithmen werden vorerst weggelassen. Sie können die Floyd-Warshall-Methode oder die Prim-Methode für dieses Diagramm anwenden, aber ich dachte, es wäre besser, einige Zeit in den Kapiteln 7 und 8 zu verbringen und dann darüber nachzudenken, wenn Sie es sich leisten können. Es war.

Übrigens gibt es andere Artikel in dieser Reihe wie folgt. Bucket-Sortierung und n log n wall-Ergänzung zu Kapitel 4 der Algorithmus-Kurzreferenz- * Ruby Aufteilung von Suche und Berechnung - Ergänzung zu Kapitel 5 der Algorithmus-Kurzreferenz- * Python [Dieser Artikel →] Lösen des Labyrinths mit Python-Supplement zu Kapitel 6 der Algorithmus-Kurzreferenz- * Python Ford-Falkerson-Methode und ihre Anwendung - Ergänzung zu Kapitel 8 der Algorithmus-Kurzreferenz- * Python