D.P.(ダイナミック・プログラミング)と最短路

: 無向グラフ : 最短経路問題 : ラベル付き有向グラフ

D.P.(ダイナミック・プログラミング)と最短路

D.P.の原理

(図5.6)

　節点から節点への最短路が与えられたとします。その路が途中に節点bを経由しているとすると,その経路のからへの部分の路も,やはりからへの最短経路になっています。
実際,からへの別の最短路があったとすると,例えば,(図6)の節点を経由して,に行く路がそうであったとすると

$\begin{displaymath} L(a,c)+L(c,e)+L(e,b)　<　　L(a,b) \end{displaymath}$

　となり,これから

$\begin{displaymath} L(a,c)+L(c,e)+L(e,b)+L(b,d)　<　　L(a,b)+　L(b,d) \end{displaymath}$

ですから,路が最短路より短くなってしまい, 路が最短であることに矛盾します。
結局, 「全体が最短（最適）ならその部分も最短（最適）」ということになります。
このような,性質を体系的に扱った最適化法の研究がベルマンによってなされました。ベルマンの（ダイナミック・プログラミング）とか最適性の原理と呼ばれています。
再帰的な計算法
最適性の原理を使うと,例えば,接点iからkまでの路が存在するとして,その中の最短路の長さをで表すと
からまでの弧が存在しない場合は $L(i,k)=\infty$ としておき,　

$\begin{eqnarray*} &&O(i,k)=min\{\{ L(i,k) \} \cup \{L(i,j)+O(j,k) \vert j \ne i,... ...+O(j_0,k),j_0 \ne i,k,(i,j0)はVの元となる j_0を一つ選択)(1b）\\ \end{eqnarray*}$

という「再帰的」な定義ができます。
ここで, $(i,(j,\cdots,k))=(i,j,\cdots,k)$ とします。
これは,節点iからの弧が存在する節点について,節点から節点までの最短の長さをもつ路 $(j,\cdots,k)$ と長さの弧をつなげた路 $(i,j,\cdots,k)$ の長さのうち,最短のものがであるという意味です。

(図5.5)
に適用すると

$\begin{eqnarray*} &&O(3,6)=20　　R(3,6)=(3,6) \\ &&O(5,6)=30　　R(5,6)=(5,6) \\... ...)\} =min\{10+40,20+50\}　 =50　\\ &&R(1,6)=(1,R(2,6))=(1,2,5,6) \end{eqnarray*}$
Dijkstraの方法
DPの原理を使った効率的な方法として,Dijkstraの方法が知られています。 <Dijkstra>

準備

$\begin{eqnarray*} 　&&K \leftarrow \phi \\ 　&&L \leftarrow P　 \\ 　&&O(1) \l... ... \\ 　&&j \ne 1となるPの要素j全てに対してO(j) \leftarrow \infty \end{eqnarray*}$

手順1

$\begin{eqnarray*} 　&&K=Pなら終了 \\ 　&&K \ne Pのとき \\ 　&&O(m)=\min \{O(i)\vert iはLの元 \}となるLの元mを選ぶ。 \end{eqnarray*}$

手順2

$\begin{eqnarray*} &&K \leftarrow K \cup \{m \}（Kに要素mを加えた集合を新たにKと.. ...\ &&~~R(j) \leftarrow m \\ &&~~そうでなければ何もしない。>>\\ \end{eqnarray*}$

手順1にもどる。

このアルゴリズムの終了時には,

には節点から節点への最短の長さ,
には節点から節点への最短路で,節点の直前の節点の番号

が書き込まれています。
以下このDijkstraの方法を図5の例に適用してみます。これは、本大学院の社会人学生「たなかさん」にやっていただいたものです。図5.5は、

$\begin{eqnarray*} &&P=\{1,2,3,4,5,6\} \\ &&V=\{(1,2),(1,4),(2,3),(2,5),(3,6),(4... ...2,3)=25, \\ &&L(2,5)=10, L(3,6)=20, L(4,5)=20, \\ &&L(5,6)=30 \end{eqnarray*}$

準備

$\begin{eqnarray*} &&K \leftarrow \phi \\ &&L \leftarrow \{1,2,3,4,5,6\} \\ &&O... ... \leftarrow 999, O(5) \leftarrow 999, \\ &&O(6) \leftarrow 999 \end{eqnarray*}$

手順１(1回目)

$\begin{eqnarray*} &&K \ne Pなので終了ではない \\ &&O(m)=min\{O(1),O(2),O(3),O(4),O(5),O(6)\} =O(1) =0 \end{eqnarray*}$

となり、m=1を選ぶ。

手順２(1回目)

$\begin{eqnarray*} &&K \leftarrow \{ 1\} \\ &&L \leftarrow \{2,3,4,5,6\} \\ &&<... ... 1\\ &&~~j=5,6のとき\\ &&~~(1,5),(1,6)はVの元ではない\\ &&~>> \end{eqnarray*}$

手順１(2回目)

$\begin{eqnarray*} &&K=\{1 \}なのでK \ne Pとなり終了ではない\\ &&O(2)=10, O(3)=9... ...6)=999なので\\ &&O(m)=min\{O(2),O(3),O(4),O(5),O(6)\} =O(2) =10 \end{eqnarray*}$

となり、を選ぶ。

手順２(２回目)

$\begin{eqnarray*} &&K \leftarrow 　\{1\} \cup \{2\}=\{1,2\}\\ &&L \leftarrow \{... ...(5) \leftarrow 2\\ &&~~j=6\\ &&~~(2,6)はVの元ではない\\ &&~>> \end{eqnarray*}$

手順１(３回目)

$\begin{eqnarray*} &&K=\{1,2\}なのでK \ne Pとなり終了ではない\\ &&O(3)=35,O(4)=2... ...=min\{O(3),O(4),O(5),O(6)\} =O(4)　 =20\\ &&となり、m=4を選ぶ。 \end{eqnarray*}$

手順２(３回目)

$\begin{eqnarray*} &&K \leftarrow \{1,2,4\}\\ &&L \leftarrow \{3,5,6\}\\ &&<<\\... ...覆蝓�燭發靴覆ぼ\ &&~j=6\\ &&~(4,6)はVの元ではない\\ &&~>>\\ \end{eqnarray*}$

手順１(４回目)

$\begin{eqnarray*} &&K=\{1,2,4\}なのでK \ne Pとなり終了ではない\\ &&O(3)=35,O(5)=20,O(6)=999なので O(m)=min\{O(3),O(5),O(6)\} =O(5) =20 \end{eqnarray*}$

となり、を選ぶ。

手順２(４回目)

$\begin{eqnarray*} &&K \leftarrow \{1,2,4,5\} \\ &&L \leftarrow \{3,6\} \\ &&~~... ...なり\\ &&~~O(6) \leftarrow 50\\ &&~~R(6) \leftarrow 5\\ &&~>> \end{eqnarray*}$

手順１(５回目)

$\begin{eqnarray*} &&K=\{1,2,4,5\}なのでK \ne Pとなり終了ではない\\ &&O(3)=35,O(6)=50なので O(m)=min\{O(3),O(6)\} =O(3) =35 \end{eqnarray*}$

となり、を選ぶ。

手順２(５回目)

$\begin{eqnarray*} &&K \leftarrow \{1,2,3,4,5\} \\ &&L \leftarrow \{6\} \\ &&~~... ... 35 + 20 = 55\\ &&~O(6) < O(3) + L(3,6)となり何もしない\\ &&>> \end{eqnarray*}$

手順１(６回目)

$\begin{eqnarray*} &&K=\{1,2,3,4,5\}なのでK \ne Pとなり終了ではない\\ &&O(6)=50なので O(m)=min\{O(6)\} =O(6) =50 \end{eqnarray*}$

となり、を選ぶ。

手順２(６回目)

$\begin{eqnarray*} &&K \leftarrow \{1,2,3,4,5,6\}\\ &&L \leftarrow \phi\\ &&<<\\ &&Lの要素がない\\ &&>> \end{eqnarray*}$

手順１(７回目) $K=\{1,2,3,4,5,6\}$ なのでとなり終了
節点1から節点への最短の長さ
節点1から節点6への最短路で節点6の直前の節点の番号

: 無向グラフ : 最短経路問題 : ラベル付き有向グラフ

Yasunari SHIDAMA