動的計画法を 図 で説明。最短経路のもとめ方-pythonで実装

目的地までの経路が何通りもあるような設定で、動的計画法(dynamic programming)を使って最短経路をもとめてみます。

- 目次 -

スポンサーリンク

考え方

例題

動的計画法で最短経路を選択
現在地は左端、駅のホームにいます。
目的地は右端のコンビニ (ローソン または セブンイレブン) です。

とにかく急いで買い物がしたいので、最速でいけるコンビニに向かいたいとします。
どちらのコンビニに、どんな経路で行くべきでしょうか。

もちろん しらみつぶしに時間を計算してもいいのですが(2 の 4乗で16通り)
なるべく計算量を減らす工夫をします。それが動的計画法です。

計算のコツ

一度に全体の経路を考えず

  • 川までの最短
  • 国道までの最短
  • コンビニまでの最短

と順番に考えていきます。

そして、 の結果をもとに をもとめ、 の結果をもとに をもとめます。

手前から順に最短をもとめていく

① 川 (橋1、橋2) まで

まず、川 (橋1、橋2) までの最短経路をもとめます。

▲ 橋1
ホーム → 北口 → 橋1 : 7分 (遠回り。この経路は選択肢からはずす)
ホーム → 南口 → 橋1 : 6分 ⇐ 橋1への最短経路
▲ 橋2
ホーム → 北口 → 橋2 : 8分 ⇐ 橋2への最短経路
ホーム → 南口 → 橋2 : 9分 (遠回り。この経路は選択肢からはずす)

するとこうなります。
動的計画法で最短経路を選択

② 国道 (信号1、信号2)まで

つぎは国道 (信号1、信号2)まで調べます。
ここで前提として、先にもとめた橋1、橋2までの最短経路を使います。それぞれ 6分と 8分でした。

▲ 信号1
橋1まで 6分 そこから信号1 まで 3分 → 計 9分 ⇐ 信号1への最短経路
橋2まで 8分 そこから信号1 まで 2分 → 計 10分 (遠回り。この経路は選択肢からはずす)
▲ 信号2
橋1まで 6分 そこから信号2 まで 4分 → 計 10分 ⇐ 信号2への最短経路
橋2まで 8分 そこから信号2 まで 3分 → 計 11分 (遠回り。この経路は選択肢からはずす)

こうなります。
動的計画法で最短経路を選択

③ コンビニまで

そして、コンビニまでの最短経路を求めます。
前提は、先にもとめた信号1、信号2までの最短経路を使います。それぞれ 9分と 10分でした。

▲ ローソン
信号1まで 9分 そこからローソン まで 7分 → 16分
信号2まで 10分 そこからローソン まで 5分 → 15分 ⇐ ローソンへの最短経路
▲ セブンイレブン
信号1まで 9分 そこからセブンイレブン まで 3分 → 12分 ⇐ セブンイレブンへの最短経路
信号2まで 10分 そこからセブンイレブン まで 3分 → 13分

動的計画法で最短経路を選択

答え

ホーム -> 南口 -> 橋 1 -> 信号1 -> セブンイレブンが最短

最短経路をもとめるとは、つまり

ポイント X までの最短を求めるとします。

  • 直前のポイント A、B までの最短時間を A0分、B0分
  • A から X までを AX分
  • B から X までを BX分

とすると

douteki6

(A0 + AX)(B0 + BX) を比べて、短いほうが X への最短時間になります。
仮に前者が短かければ、X の直前のポイントは A に決まります。

つまり、「Xへの最短を選ぶ」 という行為は 「Xの直前のポイントを選ぶ 」 という行為に等しいといえます。そして、すべてのポイントにおいて「直前のポイント」を選んで、それを線でつなげば最短経路になるはずです。

プログラムで組んでみる

python で実装

出力結果

説明

path_pos
クラスは2つ。

  • 場所を表す Position
  • 場所をつなぐ Path

Position は自分の直前の Path に計算指示を出し(getTotalTime 呼出し)
Path は自分の直前の Position に計算指示を出す(calcBestTime 呼出し)

再帰呼出しになっています。
後ろのほうから前にむかって計算指示を出し、始点のホームに到達したら、くるりと向きを変えて計算結果を戻していきます。

スポンサーリンク
その他の記事

コメントはお気軽に