参考：最短経路問題 (Shortest Path Problem)

仕事や遊びで旅行をするとき，目的地までどのようなルートをとるかを考えなくてはなりませ ん．鉄道を使うのか，自動車で行くか，あるいは飛行機か．交通手段が決まったとして，鉄道であ れば路線と乗り換え駅を考えなくてはいけません．自動車であっても，高速道を使うかどうか，ど の道を通るか，などについて，様々な条件を考慮して選択することになります．実際の旅行などは，

予算や興味の対象を考慮してルートを選択することになるでしょう．

この節では，ルート選択を“距離”が最短になるように選ぶ問題を考えます．すなわち，ネット ワークの枝に，何らかの意味で端点間の遠近の度合を表す“ 距離”が与えられているものとして，

2つの相異なる端点間の距離を最短で結ぶような経路を求めるということです．“距離”として考え られるものには，例えば，地理上の距離，交通費，移動時間などが挙げられます．

A地点からB地点まで移動することを考えます．両地点間の移動に利用できる交通網は図2.34 のネットワークによって表現することができます．枝上に与えられた数字は，その枝で表される交 通を利用した際の時間を表すとします．最短時間の移動経路はどのような経路になるでしょうか?

図表2.34 A地点とB地点間の交通網

2 4

1 6

3 5

1

7

3

6

10 2

8

2 5

2

最初に，輸送問題として定式化してみましょう．

この問題を輸送問題の枠組で解くには，A地点に供給量として1を，B地点に需要量として1 を与えます．そして，枝上の時間を，1単位の輸送にかかる費用とみなして，最小費用輸送問題と して定式化すればよいのです．最適解において1単位の物流が存在する経路が最短時間で移動でき る経路です．2.5節で示したように，この種の輸送問題は，最適解では輸送料がどの枝でも必ず整

数(この場合は1)になることを思い出してください．

最短経路を求める問題は最小費用を目的関数とする輸送問題として考えることができることを 示しました．あとは線形計画問題を適当なソルバで解けばよいことになります．しかし最短経路問

2.8. 参考：最短経路問題(Shortest Path Problem) 81 題の解法は，LPばかりではありません．例えばダイクストラ(Dijkstra)法などのより効率的な解 法が存在するのです．

端点の集合V ={s, 1, 2, . . . , n}と枝の集合E，および枝ij∈Eの距離dij> 0が与えられたと とき，以下の手続きを用いて，端点sから他の端点jへの最短経路を求めることができます．

[ダイクストラ法のアルゴリズム：]

ステップ1 初期化:

以下のように初期値を設定する．

v_s=0

vj=∞, j∈V, j̸=s M={s}

N=∅ ステップ2 端点の選択：

Mの中から，最小のラベルを持つ端点iを選び出す．

v_i=min

j∈M{v_j} ステップ3 MとNの更新：

N←N∪{i}

M←M/{i}

ステップ4 ラベルv_jの更新：

すべてのj∈V/Mについて，ij∈Eが存在し，vi+dij< vjならば，

vj←vi+dij

M←M∪{j}

とする．

ステップ5 終了判定：

M=∅なら終了する．そうでなければ，ステップ2へ．

ダイクストラ法が終了したときのラベルdj が，sからj への最短距離を与えます．図2.34の ネットワークに対してダイクストラ法を適用した際の途中経過を表2.35にまとめました．

次に,一般的な動的計画法(dynamic programming, DP)による解法を見ることにします²． 端点の集合をV=1, 2, . . . , n, tとします．端点tが目標とする端点です(図2.34では，端点6)．

端点iからtまで，n−kステップで到達する場合の最短距離をJ_k(i)で表します．k=0, 1, . . . , n−1 です．そうすると，Jk(i)は以下の関係を満たすものとして定義することができます³．

{ J_k(i) =min_j=1,...,n[d_ij+J_k+1(j)], k=0, 1, . . . , n−2; i=1, . . . , n

Jn−1(i) =ait, i=1, . . . , n (2.13)

2ダイクストラ法もDPの一種と考えることができます

3(2.13)の1本目の式は再帰方程式と呼ばれます．

図表2.35ダイクストラ法の適用例

初期化 step 1 v1=0, vj=∞, j=2, 3, 4, 5, 6 M={1}, N={∅}

反復1 step 2 min_j∈M{v_j}=v₁=0 端点1を選択 step 3 M={∅}, N={1}

step 4 端点2: min{v0+d12, v2}=min{0+1,∞}=1 ラベルを更新 端点3: min{v₀+d₁₃, v₃}=min{0+7,∞}=7 ラベルを更新 M={2, 3}

step 5 M̸=∅なのでstep 2へ

反復2 step 2 min_j∈M{v_j}=min{v₂, v₃}=min{1, 7}=1 端点2を選択 step 3 M={3}, N={1, 2}

step 4 端点3: min{v₂+d₂₃, v₃}=min{1+3, 7}=4 ラベルを更新 端点4: min{v2+d24, v4}=min{1+6,∞}=7 ラベルを更新 端点5: min{v₂+d₂₅, v₅}=min{1+10,∞}=11 ラベルを更新 M={3, 4, 5}

step 5 M̸=∅なのでstep 2へ

反復3 step 2 minj∈M{vj}=min{v3, v4, v5}=min{4, 7, 11}=4 端点3を選択 step 3 M={4, 5}, N={1, 2, 3}

step 4 端点4: min{v3+d34, v4}=min{4+2, 7}=6 ラベルを更新

端点5: min{v₃+d₃₅, v₅}=min{4+8, 11}=11 ラベルを更新しない M={4, 5}

step 5 M̸=∅なのでstep 2へ

反復4 step 2 min_j∈M{v_j}=min{v₄, v₅}=min{6, 11}=6 端点4を選択 step 3 M={5}, N={1, 2, 3, 4}

step 4 端点5: min{v4+d45, v5}=min{6+2, 11}=8 ラベルを更新 端点6: min{v₄+d₄₆, v₆}=min{6+5,∞}=11 ラベルを更新 M={5}

step 5 M̸=∅なのでstep 2へ

反復5 step 2 min_j∈M{v_j}=min{v₅, v₆}=min{8, 11}=8 端点5を選択 step 3 M={6}, N={1, 2, 3, 4, 5}

step 4 端点6: min{v₅+d₅₆, v₆}=min{8+2, 11}=10 ラベルを更新 M={6}

step 5 M̸=∅なのでstep 2へ

反復6 step 2 min_j∈M{v_j}=min{v₆}=10 端点6を選択 step 3 M={∅}, N={1, 2, 3, 4, 5, 6}

step 4 M={∅}

step 5 M=∅なので終了

結果 v1=0, v2=1, v3=4, v4=6, v5=8, v6=10 最短径路: 1—2—3—4—5—6

2.8. 参考：最短経路問題(Shortest Path Problem) 83 ここで，dijは，枝ijの距離を表します．またdii=0とおきます．

k=n−1から0にむかって，(2.13)を後ろ向きに計算(後退計算)することで，DPを解くこ とができます．実際に，図2.34に適用してみましょう．

k=4(1ステップでtに到達する場合)：

J₄(4) =5 J₄(5) =2

k=3(2ステップでtに到達する場合)：

J₃(5) = min

j=1,...,n{d_5j+J₄(j)}=d₅₅+J₄(5) =0+2=2 J₃(4) =min{d₄₄+J₄(4), d₄₅+J₄(5)}={0+5, 2+2}=4 J₃(3) =min{d₃₄+J₄(4), d₃₅+J₄(5)}={2+5, 8+2}=7 J₃(2) =min{d₂₄+J₄(4), d₂₅+J₄(5)}={6+5, 10+2}=11 k=2(3ステップでtに到達する場合)：

J₂(5) =min{d₅₅+J₃(5)}=0+2=2

J₂(4) =min{d₄₄+J₃(4), d₄₅+J₃(5)}={0+4, 2+2}=4

J₂(3) =min{d₃₃+J₃(3), d₃₄+J₃(4), d₃₅+J₃(5)}={0+7, 2+4, 8+2}=6 J₂(2) =min{d₂₂+J₃(2), d₂₃+J₃(3), d₂₄+J₃(4), d₂₅+J₃(5)}

={0+11, 3+7, 6+4, 10+2}=10

J2(1) =min{d12+J3(2), d13+J3(3)}=min{1+11, 7+7}=12 k=1(4ステップでtに到達する場合)：

J₁(5) =min{d₅₅+J₂(5)}=0+2=2

J₁(4) =min{d₄₄+J₂(4), d₄₅+J₂(5)}={0+4, 2+2}=4

J1(3) =min{d33+J2(3), d34+J2(4), d35+J2(5)}={0+6, 2+4, 8+2}=6 J1(2) =min{d22+J2(2), d23+J2(3), d24+J2(4), d25+J2(5)}

={0+10, 3+6, 6+4, 10+2}=9

J1(1) =min{d11+J2(1), d12+J2(2), d13+J2(3)}=min{0+12, 1+10, 7+6}=11 k=0(5ステップでtに到達する場合)：

J0(5) =min{d55+J1(5)}=0+2=2

J0(4) =min{d44+J1(4), d45+J1(5)}={0+4, 2+2}=4

J0(3) =min{d33+J1(3), d34+J1(4), d35+J1(5)}={0+6, 2+4, 8+2}=6 J0(2) =min{d22+J1(2), d23+J1(3), d24+J1(4), d25+J1(5)}

={0+9, 3+6, 6+4, 10+2}=9

J0(1) =min{d11+J1(1), d12+J1(2), d13+J1(3)}=min{0+11, 1+9, 7+6}=10

計算結果をまとめると図2.36となります．横軸にステップ数，縦軸に端点を取りました．図の 黒い丸の上にある数字はJ_k(i)の値です．端点2からの最短径路を知るには，k=0でi=2の場 所を見ます．この矢印をたどっていくと，2(—2)—3—4—5—6が最短のルートであることがわか ります．端点1から6までの最短距離が，ダイクストラ法で求めた値(10)と等しいことを確認し てください．

図表2.36 DPによって解いた結果

k i

1 2 3 4

1 2 3 4 5 6

2 2

2 2

4 4 4 5

7 6

6 9 11

0 4 6 9 10 2

10 11

10

例題2.13

図書館で蔵書を収容するために新しい棚を設置することになりました．この蔵書の内訳は，4イン チの高さが200冊，8インチが100冊，12インチが80冊です．本棚は，棚の高さに応じた種類が あり，4インチ，8インチ，12インチの3種類を選択できます．当然ながら8インチの棚には4イ ンチの本も収納できるし，12インチであれば，全ての本を収納することが可能です．全ての本の 厚さは0.5インチで一定であると仮定します．本一冊あたりの保管費用はその本が占める面積(棚 の高さ×本の厚み)に比例し，単位面積当り5ドルかかります．また，本棚はどの種類も1つの価 格は同じで，2300ドルです．設置費用と保管費用の合計が最小になるような棚の高さの組合わせ はどのようになるでしょうか．

[解答例]

図2.37で表される最短経路問題を解くと最適な棚の高さの組合わせが得られます．ただし，枝 の距離を設置コストと保管費用の和としています．すなわち，

枝0 4のコスト=2300+4×0.5∗200

枝0 8のコスト=2300+8×0.5∗(200+100) 枝0 12のコスト=2300+12×0.5∗(200+100+80)

枝4 8のコスト=2300+8×0.5∗100

枝4 12のコスト=2300+12×0.5∗(100+80) 枝8 12のコスト=2300+12×0.5∗80

2.9. PERT/CPM 85