RE:自分ならこう書く - pythonでA*

おぉぉぉ、コードが添削されとる！
しかし、ソート付きキューのheapqは知らなかったです、勉強になります。

それにしても、C言語のベタ移植だったとはいえ、Pythonに直すと短くなるもんだなぁ！！
・・・でも、短くしすぎでは？ (;・_・）
重要な処理まではしょっている気が・・・

これ、斜め移動を可能にする場合、nexts()とdistance()をいじると思うんですが

def nexts(pos):
    wall = "O"
    if dungeon[pos[0] - 1][pos[1]] != wall: yield (pos[0] - 1, pos[1])
    if dungeon[pos[0] + 1][pos[1]] != wall: yield (pos[0] + 1, pos[1])
    if dungeon[pos[0]][pos[1] - 1] != wall: yield (pos[0], pos[1] - 1)
    if dungeon[pos[0]][pos[1] + 1] != wall: yield (pos[0], pos[1] + 1)
    if dungeon[pos[0]-1][pos[1]-1] != wall: yield (pos[0]-1, pos[1]-1)
    if dungeon[pos[0]+1][pos[1]-1] != wall: yield (pos[0]+1, pos[1]-1)
    if dungeon[pos[0]-1][pos[1]+1] != wall: yield (pos[0]-1, pos[1]+1)
    if dungeon[pos[0]+1][pos[1]+1] != wall: yield (pos[0]+1, pos[1]+1)
    pass

def distance(path):
    px,py = path[0]
    dist = 0.
    for (nx,ny) in path[1:]:
        dist += ((px - nx)**2 + (py - ny)**2) ** 0.5
        #dist += 1.41421356237 if (px-nx)!=0 and (py-ny)!=0 else 1.0
        px,py = nx,ny
    return dist

として、経路計算をすると・・・

OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
Os* O     O     O         O    ***** O
O  *O  O  O  O  O   ****  O   *OOOO gO
O  *   O     O  O  *OOOO* O   *O  OOOO
OO*OOOOOOOOOOOOOOO *O    *O   *O**   O
O  *********     O *O    *O    *  *  O
O        OOO*    O *O    *OOOOOOOOO* O
O  OO    O   *OOOO* O    *O ***  OO* O
O   O    O    ****  O    *O* O * O*  O
O   OOO  O          O     *  O  *O*  O
O        O          O        O   *   O
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

よーーーーーくみると、2箇所ほど遠回りしてます。
で、原因はですね、なんとなくは分かるんですけど、特定には至ってません、すみません。
distance()の計算でしくじってるのかなぁ？なんか気持ち悪いなぁ・・・

孫トラックバック

勝手に採点 (Re: 自分ならこう書く - pythonでA*) - methaneのブログ
 setの話 - Doge log

* checked が配列なので pos in checked が遅い。

直したらこんな感じ。

def astar(init, goal, nexts,
          distance=len,
          heuristic=lambda pos: 0):
    import heapq
    hpush = heapq.heappush
    hpop = heapq.heappop
    queue = []
    checked = set([init])
    hpush(queue, (distance([init]) + heuristic(init), [init]))
    while queue:
        score, path = hpop(queue)
        last = path[-1]
        if last == goal:
            return path
        for pos in nexts(last):
            if pos in checked:
                continue
            checked.add(pos)
            newpath = path + [pos]
            hpush(queue, (distance(newpath) + heuristic(pos), newpath))

大きい問題なら結構差がつくかも。特に checked がモロに計算量に影響するので。

勝手に採点 (Re: 自分ならこう書く - pythonでA*) - methaneのブログ

なるほど、確かにsetを使うと速くなりますね。

結果
    9.95783400536
    0.000999927520752
setの話 - Doge log

って、set速えぇな！！
まぁ、線形探索(list)と2分木の探索(set&dict)ですから、速度に差がつくのは当たり前なんですが、結構差がつくんだなぁ。