2019-02-03 17:49:07 Python

Python

Copy Copied! Full
# 壁があるマスは 1 で、通路は 0 で表す。 m = [ [1,1,1,1,1,1,1,1,1], [1,0,1,0,0,0,0,0,1], [1,0,1,0,1,0,1,0,1], [1,0,0,0,1,0,1,0,1], [1,1,1,1,1,0,1,0,1], [1,0,0,0,0,0,0,0,1], [1,0,1,0,1,1,1,1,1], [1,0,1,0,0,0,0,0,1], [1,1,1,1,1,1,1,1,1], ] # 幅と高さ w = len(m[0]) h = len(m) # スタートとゴールをそれぞれ (1,1) および (7,7) に定める。 start = [1,1] goal = [7,7] def neighbors(p): # 隣接ノードを格納する配列 a = [] # 座標の取り出し x = p[0] y = p[1] # pから見て上下左右のマスについて、 # 1.インデックスが存在する # 2.通路(m[y][x] == 0)である # 上記2つの条件を満たせばそのマスは到達可能であるので、aに追加する。 # 上 if y-1 >= 0 and m[y-1][x] == 0: a.append([x,y-1]) # 下 if y+1 < h and m[y+1][x] == 0: a.append([x,y+1]) # 左 if x-1 >= 0 and m[y][x-1] == 0: a.append([x-1,y]) # 右 if x+1 < w and m[y][x+1] == 0: a.append([x+1,y]) return a # 点[x,y]を文字列キー('x,y')に変換する def tokey(p): return str(p[0]) + "," + str(p[1]) # ゴールから各点への最短距離を格納するハッシュ cost = {} # ある点pとゴールとの最短距離を取得する(デフォルト:9999) def getcost(p): k = tokey(p) if k in cost: return cost[k] else: return 9999 # 点pのコストをcに設定する def setcost(p, c): cost[tokey(p)] = c def shortest(start, goal): # ダイクストラ法で最短経路を探索する # ゴールを起点とした各点への最短距離を算出しながら、ゴールからスタートへの最短経路を記録する。 # (変数costにハッシュとして格納する) # 起点(ゴール)への最短距離は0 setcost(goal, 0) # 最短距離の算出は、ゴールから隣接ノードへと道筋をたどっていくことで行う。 # rootには、たどっている道筋の末端を格納する(末端は複数存在することもある) root = [goal] # 最後に最短経路をスタート地点からたどるために、「あるノードの次に通るべきノード」を記録する。 # どのようにして「通るべきノード」を判断するかは後述する。 # originは、tokey(p)を与えると点pの直前に通った点qを返すハッシュである origin = {} # 全ての末端がなくなるまで探索を継続する while 0 < len(root): # 末端の内一つを取り出し、その点への最短距離を取得する p = root[0] del root[0] c0 = getcost(p) # 全ての隣接ノードについて最短距離を計算する for q in neighbors(p): # 隣接ノードへの最短距離はは当該ノードへの最短距離+1である c1 = c0 + 1 # もし、隣接ノードへの距離を算出した結果、既知の最短距離よりも短かった場合、 # より短い経路が見つかったということだから最短距離を更新する # なお、既知の最短距離が存在しなかった場合はデフォルト距離が9999だから必然的に更新される if c1 < getcost(q): # 最短距離を更新する setcost(q, c1) # 更新した場合のみ、隣接ノードを末端として追加する # 更新しなかった場合はそのノードを通る別の最短経路が既に探索中もしくは探索済みであるので、 # 末端に追加する必要はない。 root.append(q) # 隣接ノードはよりスタート側に近いので、ゴールに到達する際に「次に通るべきノード」は # pそのものである。(そうすると最短経路でゴールに近づく) origin[tokey(q)] = p # 末端がなくなるまで探索を繰り返すと、全てのノードについて「ゴールへの最短距離」 # および「最短で到達する際に次に通るべき点」が記録される。 # あとはスタート地点を起点として経路をたどれば良い。 # 直前に通った点をprevとする(最初はstart) prev = start while True: x = prev[0] y = prev[1] # 通った点は経路として記録する m[y][x] = 2 # ゴールに到達したら終了 if prev == goal: break # 次の点を通る prev = origin[tokey(prev)] # 実際に最短経路を導出する shortest(start, goal) # 完成した解法を表示する。 for y in range(len(m)): s = "" for x in range(len(m[y])): if m[y][x] == 1: # 壁 s = s + "#" elif m[y][x] == 2: # 最短ルート s = s + "." else: # その他 (通路) s = s + " " print(s)
RECOMMEND