pythonで迷路探索するよ＜解答紹介編＞

こんばんは，1000chです． 最近Check iOが面白いのでいろんな人に布教しています． non pythonユーザに布教andしばらく様子を見た感じ，for文とlistの使い方になれが必要なのかなぁと感じています．

で，おそらくその辺の友人ズは最初の島の経路探索プログラムで詰まるんじゃないかな？と思ったので， 今回から２回に分けてちょっとした解説をしていこうかと思います．

だっさんの形式を参考に，今回まず解答コードを載せ，次回で以降で詳解していこうと思います． ではでは，いきますね．

問題

今回のターゲット問題は，はじめの島"Home"の"open labyrinth"という問題です． 問題文はこんな感じ．

The labyrinth has no walls, but pits surround the path on each side. If a player falls into a pit, they lose. The labyrinth is presented as a matrix (a list of lists): 1 is a pit and 0 is part of the path. The labyrinth's size is 12 x 12 and the outer cells are also pits. Players start at cell (1,1). The exit is at cell (10,10). You need to find a route through the labyrinth. Players can move in only four directions--South (down [1,0]), North (up [-1,0]), East (right [0,1]), West (left [0, -1]). The route is described as a string consisting of different characters: "S"=South, "N"=North, "E"=East, and "W"=West.

ざっくり言うと，「listで迷路情報が与えられるので，それを攻略する経路を出力してね」って感じですね． 最短とは書いてないような気もしますが，まぁ最短経路を求めれば委員じゃないかなと思います．

解答

さっそく，自分の解答を紹介します．

#Your code here
#You can import some modules or create additional functions

import math

class MazeNode:
    '''
    @params
    x:pos_x
    y:pos_y
    state:0:route,1:wall
    cond:'none','open','close'
    hs:h*(pos):goalまでの直線距離
    gs:適宜update:fs-hs
    fs:gs+hs
    parent:親node
    '''
    def __init__(self,x,y,st,cond):
        self.x = x
        self.y = y
        self.state = st
        self.cond = cond
        self.parent = None
        self.fs = 0
        self.hs = 0
        self.gs = 0

    def calc_hs(self,gx,gy):
        dx = self.x - gx
        dy = self.y - gy
        self.hs = math.sqrt(dx ** 2 + dy ** 2)
    
    def update_gs(self):
        self.gs = self.fs - self.hs

    def set_gs(self,val):
        self.gs = val

    def set_cond(self,cond):
        if cond == "open" or cond == "close":
            self.cond = cond
        else:
            print("cond set error")
    
    # debug
    def show_pos(self):
        print("(%d:%d) %d %s" % (self.x,self.y,self.state,self.cond))

def get_min_fs_node(maze_nodes):
    # open_nodeのうちmin_fsのものを1つreturn
    res_node = None
    for row in maze_nodes:
        for node in row:
            if node.cond != "open":
                continue
            if not res_node:
                res_node = node
            elif node.fs < res_node.fs:
                res_noe = node
    return res_node

def check_next_node(target_node,maze_nodes):
    # get next nods
    tx = target_node.x
    ty = target_node.y
    next_nodes = [
            maze_nodes[ty-1][tx  ],
            maze_nodes[ty  ][tx+1],
            maze_nodes[ty+1][tx  ],
            maze_nodes[ty  ][tx-1]
            ]

    # process next nodes
    target_node.update_gs()
    for node in next_nodes:
        if node.state == 1:
            continue
        f_dash = target_node.gs + node.hs + 1
        if node.cond == "none":
            node.set_cond("open")
            node.fs = f_dash
            node.parent = target_node
        elif node.cond == "open" and f_dash < node.fs:
            node.fs = f_dash
            node.parent = target_node
        elif node.cond == "close" and f_dash < node.fs:
            node.set_cond("open")
            node.fs = f_dash
            node.parent = target_node

# debug
def print_route(maze,fin_node):
    # make map data
    map = []
    for y in range(len(maze)):
        row = []
        for x in range(len(maze[0])):
            row.append("-" if maze[y][x] == 1 else " ")
        map.append(row)

    # make route data
    node = fin_node
    while node:
        map[node.y][node.x] = "x"
        node = node.parent

    # print route data
    for y in range(len(map)):
        for x in range(len(map[0])):
            print(map[y][x], end="")
        print("")

def make_route(fin_node):
    route = ""
    node = fin_node

    while node.parent:
        dx = node.x - node.parent.x
        dy = node.y - node.parent.y

        if dx == 1:
            route += "E"
        elif dx == -1:
            route += "W"
        elif dy == 1:
            route += "S"
        elif dy == -1:
            route += "N"
        
        node = node.parent

    return route[::-1]



def checkio(data):
    #Your code here
    #It's main function. Don't remove this function
    #It's using for auto-testing and must return a result for check.
    maze = data
    maze_nodes = []

    goal_pos_x = 10
    goal_pos_y = 10

    for y in range(len(maze)):
        row = []
        for x in range(len(maze[0])):
            node = MazeNode(x,y,maze[y][x],"none")
            node.calc_hs(goal_pos_x,goal_pos_y)
            row.append(node)
        maze_nodes.append(row)

    start_node = maze_nodes[1][1]
    start_node.set_cond("open")
    start_node.set_gs(0)
    start_node.fs = start_node.hs

    while True:
        target_node = get_min_fs_node(maze_nodes)
        print("target") 
        target_node.show_pos()
        if not target_node:
            print("search fail")
            break
        elif target_node.x == goal_pos_x and target_node.y == goal_pos_y:
            print("search finish")
            print_route(maze,target_node)
            return make_route(target_node)
            break
        else:
            target_node.set_cond("close")
            check_next_node(target_node,maze_nodes)




    #replace this for solution
    #This is just example for first maze
    return "SSSSSEENNNEEEEEEESSWWWWSSSEEEESS"

#Some hints
#Look to graph search algorithms
#Don't confuse these with tree search algorithms


#This code using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
    print(checkio([
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],
        [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1],
        [1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1],
        [1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1],
        [1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]))
    print(checkio([
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1],
        [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    ]))
    #be careful with infinity loop
    print(checkio([
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    ]))
    print(checkio([
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
        [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    ]))
    print(checkio([
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
        [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1],
        [1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1],
        [1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1],
        [1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1],
        [1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1],
        [1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1],
        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    ]))

check io に書いたモノのコピーですいませんw

経路探索といえば，昔授業でA*アルゴリズムとか紹介されたなぁと思い，wikipediaさんに詳細を聞きながら実装しました． だいたい3H弱で一気書きしたので，ツッコミどころは多々あるかもです． とはいえ定番問題なので，アルゴリズムちゃんと勉強した人だったらもっと早く書けるのかなとも思います． 精進せなあかんですね．

さて，では今回はこの辺で． 次回以降，結局このプログラム何してんの？ ってとこをちょいちょい解説していきますね．