『Pythonで体験してわかるアルゴリズムとデータ構造』メモその8/動的計画法で最短距離を求める

『Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。

Pythonで体験してわかるアルゴリズムとデータ構造

第7章 問題に適した設計法とは

前回のハノイの塔問題に引き続き、今回は最短経路の数え上げ問題を考える。

snofra.hatenablog.com

最短経路の数え上げ問題について

高校数学で出てくる問題ひとつ。

格子状の道があったとして、スタートからゴールまでの最短経路は何パターンあるかという問題。
格子状の道の中には通過することができない箇所も存在する。

この問題のイメージ、数学的な解き方については以下動画が詳しい。

www.youtube.com

動画上では階乗を使用した商を出して最短距離も求めていたが、動的計画法を用いて解いていくのがこの章の考え方なので、 以下サイトの書き込み方式の考え方で解いていく。

mathtrain.jp

ルールとしては、

• 左上にスタート、右下がゴールとして設定
• どのように追加してもよいが、上下作用で移動すること。斜め移動はNG
• 最短距離を目指すので、迂回はしない
• 通過することができないマスが存在する

このような5×6の格子状の道があったとした場合、最短距離で行くのであれば右上から左下にいくという前提があるので、赤字（Ⅰの行と1の列）は1回しか通ることができない。

では、青文字のⅡ-2ところは何回通るかというと、緑の赤字Ⅰ-2とオレンジの赤字Ⅱ-1から通ることになる。
つまりⅡ-2は2通り通る方法があるということになる。

更にここから分かるのは、求めたいマスの上のマスと左のマスの値を合算することで、そのマスを通過するのは何通りか特定することができる。

ルールにある「通過できないマス」についても基本的な考えは変わらない。

通れないマスは、そこに行くパターンはない（通過できないので）ので、行くパターンは0通り。
事前に0埋めしておくことでⅢ-3を計算したいときに 3 + 0 =3 となる。

実装

def counting(a, b, X):
    # 格子状の道のイメージを表現する。リスト型の制限で不要な0番目が生成される。
    A = [[-1 for j in range(b + 1)] for i in range(a+1)]
    print(A)
    print()
    
    #格子状の道の0番目列は不要なので、0埋めする。
    for i in range(a+1):
        A[i][0] = 0
    print(A)
    print()

    #格子状の道の0番目行は不要なので、0埋めする。
    for j in range(b+1):
        A[0][j] = 0
    print(A)
    print()

    # 通過できないところを事前に0で埋めておく
    for (i,j) in X:
        A[i][j] = 0
    print(A)
    print()
    
    #スタートは必ず通り、1通りなので1をセットしておく
    A[1][1] = 1
    
    for i in range(1, a+1):
        for j in range(1, b+1):
            if A[i][j] == -1:
                A[i][j] = A[i-1][j] + A[i][j-1]
                print("{}-{}番目を通過するのは{}+{}で{}通り".format(i, j, A[i-1][j], A[i][j-1], A[i][j]))
    return A[a][b]

counting(5,6,[(2,3),(4,5)])

[[-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, -1, -1, -1], [-1, -1, -1, -1, -1, -1, -1]]

[[0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1]]

[[0, 0, 0, 0, 0, 0, 0], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1]]

[[0, 0, 0, 0, 0, 0, 0], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, 0, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, 0, -1], [0, -1, -1, -1, -1, -1, -1]]

1-2番目を通過するのは0+1で1通り
1-3番目を通過するのは0+1で1通り
1-4番目を通過するのは0+1で1通り
1-5番目を通過するのは0+1で1通り
1-6番目を通過するのは0+1で1通り
2-1番目を通過するのは1+0で1通り
2-2番目を通過するのは1+1で2通り
2-4番目を通過するのは1+0で1通り
2-5番目を通過するのは1+1で2通り
2-6番目を通過するのは1+2で3通り
3-1番目を通過するのは1+0で1通り
3-2番目を通過するのは2+1で3通り
3-3番目を通過するのは0+3で3通り
3-4番目を通過するのは1+3で4通り
3-5番目を通過するのは2+4で6通り
3-6番目を通過するのは3+6で9通り
4-1番目を通過するのは1+0で1通り
4-2番目を通過するのは3+1で4通り
4-3番目を通過するのは3+4で7通り
4-4番目を通過するのは4+7で11通り
4-6番目を通過するのは9+0で9通り
5-1番目を通過するのは1+0で1通り
5-2番目を通過するのは4+1で5通り
5-3番目を通過するのは7+5で12通り
5-4番目を通過するのは11+12で23通り
5-5番目を通過するのは0+23で23通り
5-6番目を通過するのは9+23で32通り