人材獲得作戦の試験問題を解いてみた

出遅れた感があるけど、人材獲得作戦の試験問題をPythonで解いてみた。もちろん、調べたりググったりするの禁止で。というかググればコピペで終わりのような気がする。今回はゆるめの記事なので、メインのブログではなく、こちらに書いておく。

普通にダイクストラ法で書いたけど、何故か40分もかかった。途中でコードが気に入らなくて最初から書き直したり、ケアレスミスの修正をしたりしたからか。それにしてもすっきりしないコードだ。INFを100000で決め打ちしていたりとか、優先順位付きキューを用いていなかったりとか、周りに壁があること前提だとか。いろいろひどいなぁ。

これだけじゃ面白くないので、ダイクストラ法とA*アルゴリズムの違いを説明してみる。ダイクストラ法はスタート地点から順に隣接するノードの距離を足し合わせていき、常に最も距離の短いノードからそれに隣接するノードを調べていく方法で、A*は距離を足し合わせる際に、そのノードとゴールとの最短距離も一緒に足す方法だ。この最短距離を求める関数をヒューリスティック関数と言って、通常はそのノードとゴールの直線距離が用いられる。今回の迷路の場合はどのノードも距離が1で、ヒューリスティック関数にはマンハッタン距離での最短距離を用いている。

 a
bSc
 d
   G

上記の例では、スタート地点をS、ゴール地点をGとしており、a〜dの位置はSから見ればどれも距離が1で同じだが、普通はゴール地点に近いcもしくはdから先に調べた方が効率が良いと考えるだろう。つまり、ゴールに近いという評価をヒューリスティック関数で付加するわけだ。付加した場合、a, b, c, dのそれぞれの距離は1+5, 1+5, 1+3, 1+3となる。ただし、cやdとGの間に壁などがあるかもしれないから必ずしも近いとは限らない。ゴールに近い可能性が高いというだけだ。つまり、ヒューリスティックということになる。

まあ、言葉で説明するよりもソースコードを見た方が早いかもしれない。これはA*を使っているがheuristic関数部分を削除すれば、それがそのままダイクストラ法となる。たった2行変更するだけだ。因みにheuristic関数は最初に書いたコードに後から付け足した。dist0にはスタート位置からの距離、distにはそれにヒューリスティック関数を加えた距離が入っている。

#!/usr/bin/env python
"""http://okajima.air-nifty.com/b/2010/01/post-abc6.html"""

import sys

INF = 100000

heuristic = lambda pos, goal, offset: abs(pos // offset - goal // offset) + abs(pos % offset - goal % offset)

def search(data, offset, start, goal):
    dist, dist0 = [INF for n in range(len(data))], [INF for n in range(len(data))]
    prev = [-1 for n in range(len(data))]
    visited = [False for n in range(len(data))]
    dist[start], dist0[start], pos = heuristic(start, goal, offset), 0, start
    while pos != goal:
        min_dist, visited[pos] = INF, True
        for m in (-1, 1, -offset, offset):
            if data[pos+m] != '*':
                if dist0[pos+m] > dist0[pos] + 1:
                    dist[pos+m], dist0[pos+m] = dist0[pos] + heuristic(pos + m, goal, offset) + 1, dist0[pos] + 1
                    prev[pos+m] = pos
        for i in range(len(data)):
            if not visited[i] and min_dist > dist[i]:
                min_dist, pos = dist[i], i
    return prev

def main(args):
    data = [l.strip() for l in file(args[1])]
    print "\n".join(data) + "\n"
    offset = len(data[0])
    data = list("".join(data))
    for i, d in enumerate(data):
        if ('S' == d): start = i
        elif ('G' == d): goal = i

    path = search(data, offset, start, goal)

    pos = goal
    while True:
        pos = path[pos]
        if pos == start: break
        data[pos] = "$"
    for i in range(0, len(data), offset):
        print "".join(data[i:i+offset])

if __name__ == "__main__": main(sys.argv)

実際にダイクストラ法とA*でどれだけ違いがあるのか、ループの繰り返し回数を測定してみた。

試験問題の迷路では、ダイクストラ法で148回、A*で115回の探索回数だった。次いで以下のような迷路を解いてみた。ダイクストラ法で261回に対して、A*では71回で探索が完了した。もっと広い迷路だと更に差が出るだろう。そうなってくるとA*の方が断然効率が良い。

**************************
*                        *
*                        *
*                        *
*                        *
*                        *
*            S           *
*                        *
*                        *
*                        *
*                        *
*                       G*
**************************

ゆるい記事のつもりが何だか書いているうちに長くなってしまった。