こんにちは．1000chです．前回の迷路探索コード公開後「自分は幅優先でフツーにといたわぁ」「俺DP使ったー」「各ノードでクラス作ったのかー」などなどいろいろなコメントを頂きました．他の問題に比べ，やり方がいろいろある分個性が出て面白いですね．

では，自分用のA*アルゴリズムメモをかねて，前回コードの簡単な解説を行います．

A*アルゴリズムとは

とりあえずwikipedia先生に聞いてみました(こちら)．概要をまとめてみます．

A*アルゴリズムは，経路探索アルゴリズムのひとつです．経路にコストという概念を設け，ゴールノードまでにかかるコストを推定しながら経路を探索していきます．

ゴールまでの最小コストをf(n)，スタートから現在ノードnまでの最小コストをg(n)，現在ノードからゴールノードまでの最小コストをh(n)としたとき，f(n)は

f(n) = g(n) + h(n)

で求めることができます．しかし，g(n)やh(n)が既知であることはそうそうありません．そこで，これらの変わりに推定値であるg*(n)，h*(n)を利用し，f*(n)を考えていきます．

f*(n) = g*(n) + h*(n)

g*(n)は訪れたノードまでの推定最短値なので，探索しながら適宜更新していきます． h*(n)は推定値として，適当な値を利用します． h*(n)の満たすべき条件は

∀n, 0 <= h*(n) <= h(n)

だそうで，このようなh*(n)のことをヒューリスティック関数と呼ぶそうです．単純な経路探索では，評価関数としてユークリッド距離を使うことが多いようです（ちなみにheuristicの意味は「発見的，試行錯誤的，経験的」だそうな）．

では，実際のアルゴリズムの流れをみていきましょう．

A*アルゴリズムのながれ

まぁwikipedia先生におまかせです． (コピペなので本家wikipedia先生の方が見やすいかも

ゴールノード（G ）とスタートノード（S ）を作成する。また計算中のノードを格納しておくためのリスト（Openリスト）と、計算済みのノードを格納しておくリスト（Closeリスト）を用意する。

スタートノードをOpenリストに追加する、このとき g*(S) = 0 であり f*(S) = h*(S) となる。また Closeリストは空にする。

Openリストが空なら探索は失敗とする（スタートからゴールにたどり着くような経路が存在しなかったことになる）。

Openリストに格納されているノードの内、最小の f*(n) を持つノード n を取り出す。

n = G であるなら探索を終了する。それ以外の場合は n を Close リストに移す。

n に隣接している全てのノード（ここでは隣接ノードを m とおく）に対して以下(7,8)の操作を行う

f '(m) = g*(n) + h*(m) + COST(n,m) を計算する、ここで COST(n,m) はノード n から m へ移動するときのコストである。また g*(n) は g*(n) = f*(n) - h*(n) で求めることができる。

m の状態に応じて以下(9-11)の操作を行う

m が Openリストにも Closeリストにも含まれていない場合 f*(m) = f '(m) とし m を Openリストに追加する。このとき m の親を n として記録する。(ここではじめてf*(m)が記録される)

m が Openリストにある場合、f '(m) < f*(m) であるなら f*(m) = f '(m) に置き換える。このとき記録してある m の親を n に置き換える。

m が Closeリストにある場合、f '(m) < f*(m) であるなら f*(m) = f '(m) として m を Openリストに移動する。また記録してある m の親を n に置き換える。

3 以降を繰り返す。

探索終了後 G から親を順次たどっていくと S から G までの最短経路が得られる。

今回はコストとしてそのマスへの移動回数をつかいました．ただしh*(n)に関しては，前述の通りスタートからゴールまでの直線距離を利用しました．

コード解説

以上をふまえて，前回コードの解説です．

ノードクラスをつくる

まず，地図上の各点をノードとして利用するためのクラスを設計します．各ノード固有の情報として，

位置
f*
g*
h*
壁かどうか
親ノードへの参照

をもたせることにしました．位置情報はh*の計算と，最後の経路出力する際に利用します．壁かどうか，の情報は隣接ノード取得時に使います．一応．

また今回の実装では，openリスト，closeリストのかわりに，各ノード自体に「未調査(none)・open・close」の属性を持たせることにしました． objA in openListというようなオブジェクトの存在確認が若干面倒だったことによる苦肉の策というわけで

condition (none / open / close)

も加えます．

メソッドとしては，各種セッターとg*の更新をもたせます（どう見てもひつようないsetterまでいますね）． g*は適宜更新されますが，h*は直線距離という定数なので最初に計算して後は使い回すだけ，というところは頭に入れておくとよいですね．

てな感じで設計したのが以下のMazeNodeクラスです．

class MazeNode:

    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 checkio(data):

    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)

    #以下略

作成した関数

言い換えると「最小単位として切り分けた機能」と考えてください．こんな感じです．

openなノードからf*が最小のものを選ぶ(step4)
選択ノードの隣接ノードを処理する(step6-11)
ゴールへのルート生成(step13)

ひとつずつみてみましょう．

step4

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

関数名のままです． MazeNodeオブジェクトのリストから，openかつf_star(以下fs)が最小のものを取得します．

step6-11

def check_next_node(target_node,maze_nodes):
    # ターゲットノード周囲のノードを取得(step6)
    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]
            ]

    # 周囲ノードmに処理(step7-11)
    target_node.update_gs() # step7のため，g*の更新.ここで初めてg*に値が入る．
    for node in next_nodes:
        if node.state == 1:
            continue
        # f'(n)の計算(step7)
        f_dash = target_node.gs + node.hs + 1

        # mの状態に合わせ処理(step8)
        if node.cond == "none":
            # step9
            node.set_cond("open")
            node.fs = f_dash
            node.parent = target_node
        elif node.cond == "open" and f_dash < node.fs:
            # spet10
            node.fs = f_dash
            node.parent = target_node
        elif node.cond == "close" and f_dash < node.fs:
            # step11
            node.set_cond("open")
            node.fs = f_dash
            node.parent = target_node

愚直にwikipediaで紹介されているアルゴリズムを実装しました，という感じ．対応するstepを記しておきました．

step13

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]

終了ノードから，親をたどっていきます．たどる際にどちらの方角に移動したか，という情報から「そもそもどの方向から来たのか」を文字列にappendしていきます．このままだと"ゴールからスタートまでのルート"となるので，最後にroute[::-1]とすることで"逆順の文字列"をreturnしています．文字列クラスにreverseメソッドがあればいいんですけどね．

以上をふまえ，メイン関数はこんな感じです．

def checkio(data):
    # step1:init
    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)

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

    while True: # step12:repeat
        # step3,4
        target_node = get_min_fs_node(maze_nodes)
        if not target_node:
            # step3
            print("search fail")
            return "fail"
        elif target_node.x == goal_pos_x and target_node.y == goal_pos_y:
            #step5_finish
            print("search finish")
            return make_route(target_node) #step13
        else:
            # step5_continue
            target_node.set_cond("close")
            check_next_node(target_node,maze_nodes) #step6-11

上に引き続き，愚直にwikipediaで紹介されたアルゴリズムを実装しましたという感じですね．ループの構造自体は見やすいんじゃないかなと思います．

こうして振り返ってみると，A*は結構簡単に実装できるアルゴリズムであることがわかりますね．

まとめ

A*アルゴリズムを使った迷路探索の解説
案外簡単に実装できる
2週間前にかいたコードを読むと，自分の意図がわからない事がある←new

すこしふしぎ．

VR/HI系院生による技術ブログ．まったりいきましょ．（友人ズとブログリレー中．さぼったら焼肉おごらなきゃいけない）

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