Finding Shortest Path using Breadth First Search Algorithm

面白い問題があったので解いてみました。問題の詳細は、出題者さんのエントリでご確認ください。

さて試験問題です。内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。

人生を書き換える者すらいた。: 人材獲得作戦・４　試験問題ほか

実装は以下となりました。Python3.1.1を使用し、BFS + 既知の最短経路での刈り込みを行なっています。

#!/usr/local/bin/python3.1 -t

import collections
import sys

def solve(a, s, g):
    dps = (( 0, -1),
           ( 1,  0),
           ( 0,  1),
           (-1,  0))

    shortest = {}

    queue = collections.deque([[s]])
    while queue:
        path = queue.popleft()
        p = path[-1]
        if p in shortest:
            if len(path) < len(shortest[p]):
                shortest[p] = path
            else:
                continue
        else:
            shortest[p] = path
        if p == g:
            yield path
            continue
        for dp in dps:
            np = p[0] + dp[0], p[1] + dp[1]
            if np not in path:
                if a[np[1]][np[0]] != '*':
                    queue.append(path + [np])
    
if __name__ == '__main__':
    a = []
    for i, l in enumerate(sys.stdin):
        l = l.strip()
        if 'S' in l:
            s = (l.index('S'), i)
        if 'G' in l:
            g = (l.index('G'), i)
        a.append(l)
    for path in sorted(solve(a, s, g), key=lambda x: len(x)):
        for i, r in enumerate(a):
            for j, c in enumerate(r):
                if (j, i) == g:
                    print('G', end='')
                elif (j, i) in path:
                    print('$', end='')
                else:
                    print(c, end='')
            print()

制限時間がある中のコーディングであったため汚いですね。そのような中でもしっかりと実装出来るようになりたいものです。

追記(2010/1/12)

ゴールを発見した後も検索を続けていたので、打ち切りました。

             :
        if p == g:
            yield path
            continue
             :

追記(2010/1/21)

Visualizing Dijkstra's, and A* Search Algorithm - agwの日記として、ダイクストラのアルゴリズムとA*検索アルゴリズムについての考察を記載しました。