Aperçu

Il s'agit d'une série de lecture de livres, de réétude de diverses choses et d'écriture de ce qui vous intéresse. Cette fois-ci, [Référence rapide de l'algorithme](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) Le thème est "Algorithme graphique" au chapitre 6. Plus précisément, il est devenu un chapitre pour résoudre le labyrinthe en Python. Comment est-ce arrivé.

Comment résoudre le labyrinthe

Avant

Il explique comment convertir un point de branchement en un graphe avec des nœuds et le résoudre. C'est vrai, mais on parlait uniquement de la façon dont les humains le font "comment réduire un labyrinthe donné en un graphique". Alors, pensons à faire un graphique en saisissant la figure suivante (chaîne de caractères) qui a copié le labyrinthe autant que possible.

`maze_input.txt`


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

C'est très déroutant, mais il y a des s et des t, qui correspondent aux points de départ et cible. La méthode pour créer la chaîne de caractères inférieure à partir de la figure supérieure consiste à ** l'étendre et à la connecter, en pensant que les carrés sont en fait cachés entre chaque carré du diagramme du labyrinthe **. En d'autres termes

Les 2e et 2j colonnes de la chaîne de caractères ci-dessous correspondent aux colonnes i et j de la figure ci-dessus.
Les autres positions dans la chaîne inférieure (par exemple, le symbole $ sur 3 lignes et 3 colonnes) sont la ligne noire dans la figure ci-dessus ou le "passage" caché entre les carrés s'il n'y a pas de mur. Correspond à

Vous pouvez ajouter une telle réponse. En d'autres termes, quand il y a des carrés en forme de grille, vous pouvez penser à deux types de placement: comment placer les pierres sur le plateau de go et comment placer les pièces sur le plateau de shogi. En les combinant, j'ai décidé de penser soit (1) le centre du carré, (2) le milieu du côté, ou l'intersection (3) du côté comme "un endroit où les pierres et les pièces peuvent être placées". S'il y a une ligne noire à cet "endroit où les pierres et les pièces peuvent être placées", elle peut être obtenue en faisant la correspondance "$", sinon "".

Faire un graphique

Bon, l'introduction est devenue longue, mais j'écrirai un programme en Python qui récupère un graphe de ce labyrinthe.

`CreateGraph.py`


#Tracez le labyrinthe: recherche essentiellement en profondeur
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

#Paramètres de ces données
getEdge(arr, 3, 7, edges, 1, 1)

Une fonction appelée getEdge est essentiellement une recherche de priorité en profondeur et traite simplement de manière récursive les cellules adjacentes. Le fait que la masse ait déjà été traitée ou non est écrit tel quel dans la liste arr qui contient le plateau. De plus, lors de ce processus, j'ai également décidé de calculer "side length" = "nombre de carrés jusqu'à la prochaine intersection ou impasse".

Visualisation des graphiques de labyrinthe

Puisque c'est un gros problème, visualisons ceci.

`Visualize.py`


#Visualisation
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()

Par rapport au labyrinthe d'origine, la relation positionnelle semble légèrement pivotée, mais si vous la saisissez en fonction de la relation positionnelle de s et t, vous pouvez voir qu'il s'agit d'un graphique qui est une transcription du labyrinthe d'origine. .. Naturellement, il s'agit du même type que l'illustration du livre. (Sauf pour les noms des sommets!)

Recherche de priorité de largeur dans ce graphique

Maintenant que nous avons un graphique, ignorons la pondération (distance réelle) de ce graphique et calculons la profondeur en fonction uniquement du nombre de nœuds.

`BreadthFirst.py`


#Recherche de priorité de largeur
import copy

#Définition du quartier et drapeau utilisé (génération)
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

Vous obtiendrez une sortie similaire à ce qui suit: (Omettre les sauts de ligne)

`résultat`


{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}

Vous pouvez maintenant voir la "génération" de chaque nœud = intersection lorsque s est la première génération. C'est une valeur qui peut être utilisée comme indice pour dire: "Combien de fois devrais-je me perdre avant d'y arriver?"

Recherche de l'itinéraire le plus court dans ce graphique (algorithme naïf Dyxtra)

Dans le livre original, il est calculé avec un graphe orienté, mais si vous pensez à un graphe non orienté comme un graphe avec des arêtes dans les deux directions, vous pouvez appliquer l'algorithme de Dyxtra exactement de la même manière. Ici, je voudrais calculer la distance la plus courte de s à t avec un algorithme Dyxtra naïf et facile à implémenter.

`Dijkstra.py`


#Calcul de l'itinéraire le plus court par la méthode Dyxtra
costs = {}
# costs[v] = (cost, prev, used)Une paire de
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)
    #Ce sera plus rapide si vous trouvez un moyen de le mettre dans la file d'attente, mais ici je ne mettrai qu'une valeur la plus basse dans la file d'attente
    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)

`résultat`


{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)}

Une implémentation assez bonne autour de la file d'attente, mais elle renvoie le résultat correct car elle n'ajoute qu'un des sommets les moins coûteux à chaque fois qu'il est traité. Le résultat de sortie est, par exemple, (20, 4, 1) lorsque vous regardez la ligne t, mais la distance (pas) par rapport au but est de 20 et l'intersection précédente est de "4". Cela signifie que c'est le lieu représenté par. En suivant cela, non seulement la distance mais aussi l'itinéraire le plus court lui-même peuvent être connus. Je suis heureux.

Au fait, lorsque j'ai écrit cet article pour la première fois, j'ai sérieusement essayé d'utiliser Python et j'ai réfléchi à ce qui suit.

――Il est assez facile d'utiliser des taples

Il est très difficile d'accéder au taple avec [0] ou [2](cela ne veut pas dire que Python est mauvais)

Je me suis demandé s'il devait être correctement défini comme quelque chose de structurel lorsque je l'utilisais comme une structure appropriée au lieu de le combiner avec for.

La fin

D'autres algorithmes seront supprimés pour le moment. Vous pouvez appliquer la méthode Floyd-Warshall ou la méthode Prim pour ce graphique, mais j'ai pensé qu'il serait préférable de passer un peu de temps sur les chapitres 7 et 8, puis d'y réfléchir si vous pouvez vous le permettre. C'était.

À propos, il existe d'autres articles de cette série comme suit. Bucket sort and n log n wall-Supplement to Chapter 4 of Algorithm Quick Reference- * Ruby Division de la recherche et du calcul - Supplément au chapitre 5 de la référence rapide de l'algorithme- * Python [Cet article →] Résolution du labyrinthe avec Python-Supplément au chapitre 6 de la référence rapide de l'algorithme- * Python Méthode Ford-Falkerson et son application - Supplément au chapitre 8 de la référence rapide de l'algorithme- * Python