[python] 格子状の最短経路問題

Python

今回はpythonで格子状の最短経路を求める問題を解いていこうと思います。

それでは早速解いていきましょう。

例題

55 66 77 15 16 17
35 79 13 10 87 11
14 30 20 99 19 12
25 18 85 63 23 73
21 91 31 61 22 44

例えば上記のような格子状の表があるとして左上から右下まで行くまでに一番合計の数が少なくなるように移動し、どこを通ることになったか知りたい。

ただし移動できるのは右と下のみで上移動、左移動、斜めは移動できません。

どうすればいいでしょうか?

s=[[0 for i in range(6)] for j in range(5)]

s[0][0]=55
s[0][1]=66
s[0][2]=77
s[0][3]=15
s[0][4]=16
s[0][5]=17
s[1][0]=35
s[1][1]=79
s[1][2]=13
s[1][3]=10
s[1][4]=87
s[1][5]=11
s[2][0]=14
s[2][1]=30
s[2][2]=20
s[2][3]=99
s[2][4]=19
s[2][5]=12
s[3][0]=25
s[3][1]=18
s[3][2]=85
s[3][3]=63
s[3][4]=23
s[3][5]=73
s[4][0]=21
s[4][1]=91
s[4][2]=31
s[4][3]=61
s[4][4]=22
s[4][5]=44

f=[[0 for i in range(6)] for j in range(5)]

f[0][0]=s[0][0]

for q in range(1,6):
    f[0][q]=f[0][q-1]+s[0][q]

for p in range(1,5):
    f[p][0]=f[p-1][0]+s[p][0]
    for q in range(1,6):
        f[p][q]=min(f[p-1][q],f[p][q-1])+s[p][q]  
              
print("最短距離は",f[4][5])

"""
最短距離は 361
"""

fはその地点までに要したコストの合計値の記憶したもので、gが通過経路を記憶するための配列、sはその経路のコストです。

イメージは上と左の値を見て小さい方を採用して、その場所のコストを足すというイメージですね。

動的計画法です。

あと、通過経路の記憶ですが、左から来たらgに0を、上から来たらgに1を代入して通過経路の記憶を行いました。

以上で今回は終了となります。ありがとうございました。

コメント

タイトルとURLをコピーしました