テーマ

地形コストを情報として持つマップにおいて、スタート地点とゴール地点までを最低コストで結ぶルートを探す。(例えば、SRPG系のゲームでは、平地、家屋、森、山へ移動するときに地形コストが考慮されている)

アルゴリズム

1) 座標と地形コストが対応した配列を用意(cost_map)
2) ゴール地点を始点として、各地点まで移動にかかるコストを求め、配列を作成(rout_cost)
3) 各地点の移動コスト(rout_cost)をもとに、スタート地点からコストの小さい点をたどる

注) 補足(プログラムを書く上で用いるテクニック)
再帰関数を用います。

実践

1) 例えば以下のような地形コストを持つマップにおいてスタート ( x3, y0 ) からゴール ( x1, y6 ) への最短経路を考える。

	y0	y1	y2	y3	y4	y5	y6
x0	4	3	1	1	1	2	3
x1	3	2	1	2	1	1	1
x2	2	1	3	3	2	3	2
x3	2	3	5	3	2	4	3

地形コストを要素に持つ配列cost_map、さらに無限値を要素に持つ配列rout_costを用意する。

alg_01.py

s = [3,0]; g = [1,6]  ## start and goal position
cost_map = [[4,3,1,1,1,2,3],\
            [3,2,1,2,1,1,1],\
            [2,1,3,3,2,3,2],\
            [2,3,5,3,2,4,3]]
m = len(cost_map)
n = len(cost_map[0])
rout_cost = [[float("inf") for j in range(n)] for i in range(m)]

2) ゴール地点を始点として各地点までの移動コストを計算し、計算結果に基づいて上で用意したrout_costを更新する。

alg_02.py

def calc_rout_cost(x,y,cost_tmp):
    cost_tmp += cost_map[x][y]
    if cost_tmp < rout_cost[x][y]:
        rout_cost[x][y] = cost_tmp
        if y < n-1:
            calc_rout_cost(x,y+1,cost_tmp)
        if y > 0:
            calc_rout_cost(x,y-1,cost_tmp)
        if x < m-1:
            calc_rout_cost(x+1,y,cost_tmp)
        if x > 0:
            calc_rout_cost(x-1,y,cost_tmp)
calc_rout_cost(g[0],g[1],-cost_map[g[0]][g[1]])

出来上がったrout_costは以下の通り。ゴール地点(x6,y1)はゼロになることに注意。

	x0	x1	x2	x3	x4	x5	x6
y0	12	8	5	4	3	3	3
y1	10	7	5	4	2	1	0
y2	10	8	8	7	4	4	2
y3	12	11	13	9	6	8	5

3) 最後に、スタートからゴールまでの最短経路を探す。

alg_03.py

def search_rout(x,y):
    tmp = rout_cost[x][y]
    tmp_x, tmp_y = x, y
    if x > 0 and rout_cost[x-1][y] < tmp :
        tmp_x, tmp_y = x-1, y
        tmp = rout_cost[tmp_x][tmp_y]
    if x < m-1 and rout_cost[x+1][y] < tmp :
        tmp_x, tmp_y = x+1, y
        tmp = rout_cost[tmp_x][tmp_y]
    if y > 0 and rout_cost[x][y-1] < tmp :
        tmp_x, tmp_y = x, y-1
        tmp = rout_cost[tmp_x][tmp_y]
    if y < n-1 and rout_cost[x][y+1] < tmp :
        tmp_x, tmp_y = x, y+1
        tmp = rout_cost[tmp_x][tmp_y]
    if rout_cost[x][y] == 0: return;
    rout_list.append([tmp_x,tmp_y])
    search_rout(tmp_x,tmp_y)

rout_list = []
rout_list.append(s)
search_rout(s[0],s[1])

最短経路は

result.py

print(rout_list)
## [[3, 0], [2, 0], [2, 1], [1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6]]

となる。

参考文献

柳井政和「プログラマのためのコードパズル」技術評論社 (2014)
詳しい説明は文献をあたってください。Javascriptで記述してあります。