Open Labyrinthに再チャレンジ （A*探索）

先日、Open Labyrinth （迷路の探索）で、他の人の解答やヒントがさっぱり理解できなかったのが悔しかったので、図書館で「アルゴリズムを学ぼう」という本を借りてきた。

アルゴリズムを学ぼう

この本、amazonでの評価は低いが、グラフ探索、BFS、DFS、A*探索 と全く意味不明だった単語が解説されていたし、なにより、4-6章「A*探索で迷路を解く」で、Open Labyrinthとほとんど同じ問題がソースコード付きで載っているのだ。

該当のコードは、リスト4-5とリスト4-6 （p.101～102）で、Javaで書かれているので、Pythonに移植してみる。
しかし、何かがおかしい。リスト4-6って、本当に迷路を解けてる？そもそも引数のマップデータ(m)を全く使っていないように見えるのだが。障害物を避けるという部分が無いので、これでは一直線にゴールに進むだけなんじゃ？？？

ま、とにかくポイントを整理すると、こんな感じ。

• A*探索を使うなら、優先度付きキュー（＝ヒープキュー）を使う。
• 現在値の東西南北のマスが未探索ならキューに追加。優先度はゴールまでの距離を使う。
• キューから優先度の一番小さいものを取り出して、そこへ移動。
• 探索済みの場所は visited辞書に入れる。keyが座標、valueが方角(NEWS)
• ゴールに着いたら、visited辞書を使って、スタートまでのルートを逆算する。

左手法では、左のマスを優先的に探索したが、A*探索では、ゴールに近いマスを優先的に探索する、ということのようだ。

優先度付きキュー（ヒープキュー）

JavaのPriorityQueueは、Pythonではheapqを使えばよい。
http://docs.python.jp/3.3/library/heapq.html

要素の追加は heappush関数、取り出すには、heappop関数を使う。
要素は (優先度, 値) のタプルとしておく。今回の場合、優先度はゴールまでの距離、値はマスの座標(x,y)となる。

優先度付きキューではなく、スタックを使えば DFS（深さ優先探索）、キューを使えば BFS（幅優先探索） となるらしい。

Pythonで書いてみた

本のソースコードを参考に、CheckiOのOpen Labyrinthに合わせて書き直したのがこちら。

import heapq

def checkio(maze_map):
    DIRS = {'N': (0, -1), 'E': (1, 0), 'S': (0, 1), 'W': (-1, 0)}  # value=(x,y)

    def push(pt):
        # ヒープキューに(距離, 座標)を追加
        distance = abs(pt[0] - goal[0]) + abs(pt[1] - goal[1])
        heapq.heappush(q, (distance, pt))

    def get_new_position(pt, direction, reverse=False):
        # 東西南北のマスの座標を取得
        d = DIRS[direction]
        if reverse:
            return pt[0] - d[0], pt[1] - d[1]
        else:
            return pt[0] + d[0], pt[1] + d[1]

    def get_path():
        # ゴールからスタートまでを逆にたどる
        pt = goal
        result = ''
        while pt != start:
            result = visited[pt] + result
            pt = get_new_position(pt, visited[pt], True)
        return result

    def is_safe(pt):
        # 座標が通路ならTrue
        return maze_map[pt[1]][pt[0]] == 0

    start = (1, 1)
    goal = (10, 10)

    q = []
    visited = dict()  # key=(x,y), value='N','E','W','S'

    push(start)
    while len(q) > 0:
        pos = heapq.heappop(q)[1]  # キューから取り出す
        if pos == goal:
            return get_path()  # ゴールに着いたら、ルートを取得
        for d in DIRS:
            new_pt = get_new_position(pos, d)
            if is_safe(new_pt) and new_pt not in visited:  # 未探索ならキューに追加
                visited[new_pt] = d
                push(new_pt)

テストしてみると、たしかに左手法と違って無駄なルートを通らないようになっている。