Solving the Maze with Python-Supplement to Chapter 6 of the Algorithm Quick Reference-

Overview

This is a series of reading books, re-studying various things, and writing what you are interested in. This time, [Algorithm Quick Reference](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) The theme is "Graph Algorithm" in Chapter 6. Specifically, it's a chapter on solving mazes in Python. How did this happen.

How to solve the maze

Before

It explains how to convert a graph with a branch point as a node and solve it. That's true, but when it comes to "how to reduce a given maze to a graph," only the way humans do it was talked about. python_6_0.PNG So, let's think about making a graph by inputting the following figure (character string) that copied the maze as much as possible.

maze_input.txt


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

It's very confusing, but there are s and t, which correspond to the start and target points. The method of creating the lower character string from the upper figure is to ** extend and connect the squares, thinking that the squares are actually hidden between each square in the maze diagram **. In other words

--The 2nd and 2j columns in the character string below correspond to the i and j columns in the above figure. --Other positions in the string below (for example, the $ symbol in 3 rows and 3 columns) are the black line in the above figure or the "passage" hidden between the squares if there is no wall. Corresponds to

You can add such a response. In other words, when there are grid-like squares, you can think of two types of placement: how to place the stones on the board and how to place the pieces on the shogi board. By combining these, I decided to think of either (1) the center of the square, (2) the midpoint of the side, or the intersection of (3) the side as "a place where stones and pieces can be placed". If there is a black line in this "place where stones and pieces can be placed", it can be obtained by making the correspondence "$", otherwise "".

Make a graph

Well, the introduction has become long, but I will write a program in Python that gets a graph from this maze.

CreateGraph.py


#Graph the maze: Depth-first search in essence
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

#Settings for this data
getEdge(arr, 3, 7, edges, 1, 1)

A function called getEdge is essentially a depth-first search, and simply recursively processes the cells adjacent to it. Whether or not the square has already been processed is written as it is in the list arr that contains the board. In addition, when doing this process, I also decided to calculate "side length" = "the number of squares until the next intersection or dead end".

Visualization of maze graph

Since it's a big deal, let's visualize this.

Visualize.py


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

python_6_3.PNG

Compared to the original maze, it seems that the positional relationship is slightly rotated, but if you grasp it based on the positional relationship of s and t, you can see that it is a graph that is a transcription of the original maze. .. Naturally, it is the same type as the illustration in the book. (Except for the names of the vertices!)

Breadth-first search in this graph

Now that we have a graph, let's ignore the weighting (actual distance) of this graph and calculate the depth based only on the number of nodes.

BreadthFirst.py


#Breadth-first search
import copy

#Definition of neighborhood and used flags (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

You will get output similar to the following: (Omit line breaks)

result


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

Now you can see the "generation" of each node = intersection when s is the first generation. It's a value that can be used as an index to say, "How many times should I get lost before I get there?"

Search for the shortest path in this graph (naive Dijkstra's algorithm)

In the original book, we calculate with directed graphs, but if you think of undirected graphs as graphs with edges in both directions, you can apply Dijkstra's algorithm in exactly the same way. Here we want to calculate the shortest distance from s to t with a naive Dijkstra algorithm that is easy to implement.

Dijkstra.py


#Calculated by Dijkstra's algorithm for the shortest cost route
costs = {}
# costs[v] = (cost, prev, used)Pair of
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)
    #It will be faster if you devise a way to put it in the queue, but here I will only put one lowest value in the queue
    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)

result


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

A fairly good implementation around the queue, but it returns the correct result as it appends only one vertex with the lowest cost each time it is processed. The output result is, for example, (20, 4, 1) when you look at the't' line, but the distance (steps) to the goal is 20, and the previous intersection is "4". It means that it is the place represented by. By following this, you can see not only the distance but also the shortest path itself. I'm happy.

By the way, when I wrote this article for the first time, I seriously tried using Python and thought about the following.

――It's quite easy to use tuples --It's very rough to access tuples with [0] or [2](it doesn't mean that Python is bad).

I wondered if it should be properly defined as something structural when it is used like a proper structure instead of a combination with for.

The end

Other algorithms will be omitted for the time being. You can apply the Floyd-Warshall method or the Prim method for this graph, but I thought it would be better to spend some time on chapters 7 and 8 and then think about it if you can afford it. It was.

By the way, there are other articles in this series as follows. Bucket sort and n log n wall-Supplement to Chapter 4 of Algorithm Quick Reference- * Ruby Division of search and calculation-Supplement to Chapter 5 of Algorithm Quick Reference- * Python [This article β†’] Solving the maze with Python-Supplement to Chapter 6 of the Algorithm Quick Reference- * Python Ford-Fulkerson method and its application --Supplement to Chapter 8 of Algorithm Quick Reference- * Python

Recommended Posts

Solving the Maze with Python-Supplement to Chapter 6 of the Algorithm Quick Reference-
How to try the friends-of-friends algorithm with pyfof
Visualize the behavior of the sorting algorithm with matplotlib
Solving the Python knapsack problem with the greedy algorithm
Add information to the bottom of the figure with Matplotlib
Try to solve the problems / problems of "Matrix Programmer" (Chapter 1)
The first algorithm to learn with Python: FizzBuzz problem
[Chapter 6] Introduction to scikit-learn with 100 knocks of language processing
Try to get the contents of Word with Golang
[Chapter 3] Introduction to Python with 100 knocks of language processing
[Chapter 2] Introduction to Python with 100 knocks of language processing
[Chapter 4] Introduction to Python with 100 knocks of language processing
I tried to find the entropy of the image with python
I tried to find the average of the sequence with TensorFlow
Introduction to Statistics The University of Tokyo Press Chapter 2 Exercises
Settings to debug the contents of the library with VS Code
I implemented the FloodFill algorithm with TRON BATTLE of CodinGame.
Try to solve the problems / problems of "Matrix Programmer" (Chapter 0 Functions)
Try to automate the operation of network devices with Python
Finding a solution to the N-Queen problem with a genetic algorithm (1)
Get the source of the page to load infinitely with python.
Try to extract the features of the sensor data with CNN
Solving the nurse scheduling problem (shift optimization) with a genetic algorithm
Save the results of crawling with Scrapy to the Google Data Store
Find the optimal value of a function with a genetic algorithm (Part 2)
Become familiar with (want to be) around the pipeline of spaCy
How to get the ID of Type2Tag NXP NTAG213 with nfcpy
[Introduction to StyleGAN] I played with "The Life of a Man" ♬
Try to solve the N Queens problem with SA of PyQUBO
Output the contents of ~ .xlsx in the folder to HTML with Python
Consider the speed of processing to shift the image buffer with numpy.ndarray
How to monitor the execution status of sqlldr with the pv command
I tried to expand the size of the logical volume with LVM
To improve the reusability and maintainability of workflows created with Luigi
Solving Knapsack Problems with Google's OR-Tools-Practicing the Basics of Combinatorial Optimization Problems
I want to check the position of my face with OpenCV!
From the introduction of JUMAN ++ to morphological analysis of Japanese with Python
I tried to improve the efficiency of daily work with Python
PhytoMine-I tried to get the genetic information of plants with Python
Implementation of Dijkstra's algorithm with python
Solving the amplitude of interferometer observations
Supplement to the explanation of vscode
Solving the phase of interferometer observations
Calculate the shortest route of a graph with Dijkstra's algorithm and Python
The 16th offline real-time how to write reference problem to solve with Python
Try to image the elevation data of the Geographical Survey Institute with Python
I tried to solve the 2020 version of 100 language processing [Chapter 3: Regular expressions 25-29]
[Image recognition] How to read the result of automatic annotation with VoTT
Try to solve the traveling salesman problem with a genetic algorithm (Theory)
I tried to get the authentication code of Qiita API with Python.
Get the number of visits to each page with ReportingAPI + Cloud Functions
I want to express my feelings with the lyrics of Mr. Children
Setting to debug test by entering the contents of the library with pytest
I tried to automatically extract the movements of PES players with software
How to fix the initial population with a genetic algorithm using DEAP
Try to react only the carbon at the end of the chain with SMARTS
I tried to analyze the negativeness of Nono Morikubo. [Compare with Posipa]
I tried to streamline the standard role of new employees with Python
I tried to visualize the text of the novel "Weathering with You" with WordCloud
The 19th offline real-time how to write reference problem to solve with Python
Write the result of keyword search with ebaysdk to Google Spread Sheets