経路探索
問題
r行c列のグリッドに障害物がいくつかある。左上から右下にいく経路を探索する。ただし、動ける方向は右と下のみ。
考え方
グリッド (i,j)にたどり着けるかどうかをTrue or Falseで格納する。flg[i][j]は左側flg[i][j-1]と上側flg[i-1][j]を見れば到達できるかわかる。flg[i][j]がTrueになる動く方向を記録しておく。（どちらも大丈夫な場合にはどちらか片方を）
障害物があることを0とすると(i,j)にたどり着けるかは以下で計算できる。
flg[i][j] = max(flg[i-1][j]*ob[i][j], flg[i][j-1]*ob[i][j])
次に、経路を格納する際は前の動いた方向を記録していく。下を０、右を１とすると
p[i][j] = np.argmax([flg[i-1][j]*ob[i][j], flg[i][j-1]*ob[i][j]])
となる。
最後に、flg[r][c] がTrueならp[i][j]を後ろから辿ることで経路がわかる。
コード例
import numpy as np # 右に進むのを1 下に進むのを0とする # 障害物があることを0として何もないのを1とします。 def searchRoute(r, c, ob): flg = np.zeros([r, c]) p = np.zeros([r, c]) - 1 # 初期値は-1にしておく # 初期値として、へんだけ別に行う flg[0][0] = ob[0][0] # 下方向 for i in range(1, r): flg[i][0] = flg[i-1][0]*ob[i][0] p[i][0] = 0 # 右方向 for j in range(1, c): flg[0][j] = flg[0][j-1]*ob[0][j] p[0][j] = 1 for i in range(1, r): for j in range(1, c): flg[i][j] = max(flg[i-1][j]*ob[i][j], flg[i][j-1]*ob[i][j]) p[i][j] = np.argmax([flg[i-1][j]*ob[i][j], flg[i][j-1]*ob[i][j]]) if flg[r-1][c-1] == True: i = r-1 j = c-1 print("左上まで戻るには") while not (i==0 and j==0): move = p[i][j] if move == 0: i -= 1 print("上") else: j -= 1 print("左") else: print("no Route") return flg, p if __name__ == "__main__": # 障害物 作成 r = 5 c = 10 ob = np.zeros([r, c]) + 1 ob[1][0] = 0 ob[1][2] = 0 ob[0][7] = 0 ob[4][5] = 0 print("障害物は\n", ob) print("---経路探索---") flg, p = searchRoute(r, c, ob)
実行結果は
障害物は [[1. 1. 1. 1. 1. 1. 1. 0. 1. 1.] [0. 1. 0. 1. 1. 1. 1. 1. 1. 1.] [1. 1. 1. 1. 1. 1. 1. 1. 1. 1.] [1. 1. 1. 1. 1. 1. 1. 1. 1. 1.] [1. 1. 1. 1. 1. 0. 1. 1. 1. 1.]] ---経路探索--- 左上まで戻るには 上 上 上 左 左 左 上 左 左 左 左 左 左
