pythonでA*のコードを修正しました

自分ならこう書く - pythonでA* - ラシウラの記事の元記事の方から、実装が不十分との記事でトラバがきてたのに気がついたので、正しく動くよう直しました。

RE:自分ならこう書く - pythonでA* - Pashango’s Blog

def astar(init, goal, nexts,
          distance=lambda path: len(path),
          heuristic=lambda pos: 0):
    import heapq
    queue = []
    init_score = distance([init]) + heuristic(init)
    checked = {init: init_score}
    heapq.heappush(queue, (init_score, [init]))
    while len(queue) > 0:
        score, path = heapq.heappop(queue)
        last = path[-1]
        if last == goal: return path
        for pos in nexts(last):
            newpath = path + [pos]
            pos_score = distance(newpath) + heuristic(pos)
            if pos in checked and checked[pos] <= pos_score: continue
            checked[pos] = pos_score
            heapq.heappush(queue, (pos_score, newpath))
            pass
        pass
    return None

問題はchecked(用語的にはclosed listだったかな)でのカットが、すでに通ったかどうかだけでなく、スコア比較が必要だったということでした。つまり、「すでに通った場所でも、それまでのスコアのほうが大きければ、それも継続対象にする」という部分です。

ほんのちょっとの差(checkedをdictにして、その値も比較する)ですが、これで斜めでもふくらまないようになりました。

thanks.

補足: なぜふくらみがでたか、この変更でなぜ解消できるか

元記事では、斜め移動を追加し、斜め移動のコスト(distance)を2 ** 0.5 (≒1.4)としてました。

ふくらむ場合でも、ふくらまない場合でも合流点のパスの長さは3
ふくらむほうのコストは 1.4 + 1 + 1.4
ふくらまないほうのコストは 1 + 1 + 1

ヒューリスティック値との和によって、合流点の手前までは、ふくらむほうがコストは大きくても「スコア」が小さくなります。

そのため合流直前は、先に膨らんだほうが優先して計算されます。そこで3.8のコストで合流点がまず計算されました。
しかし、そのあと続けると、ふくらまないコスト2のほうがスコアが小さくなる状況が出てくるので、その時点であらためて次の点を取ろうとします。

以前の実装ではとおったかどうかを調べるだけだった(checkedがlist/setだった)ので、ふくらんだときすでに合流点は計算されていたため、ふくらまない場合の合流点のパスをカットしていました(for中のif文にて)。

今回の実装では以前のように通ったかどうかだけでなく、そのときのスコアも保持するようにしました(checkedを(point, score)のdictにした)。
すでに通った点でも一度スコア計算をし、checkedで保持してる以前通ったときのスコアと比較して、より小さい場合は、計算対象にする(queueに放り込む)ようにしたため、その状況でも評価が進むようになり、結果としてスコアが小さいためふくらまないほうが選ばれるようになりました。