経路問題

提供: Internet Web School

目次 1 有向グラフ 1.1 ラベル 1.2 路 1.3 最短路問題 2 D.P.(ダイナミック・プログラミング)と最短路 2.1 D.P.の原理 2.2 再帰的な計算法 2.3 Dijkstraの方法 3 無向グラフ 3.1 ラベル 3.2 路 3.3 巡回セールスマン問題 3.4 D.P.の適用 3.5 分岐限定法

有向グラフ

有向グラフは,ここでは\(G\)で表しますが,コンピュータや,ネットワークにもよく使われ ます。有向グラフ\(G\)は

(1) 節点の集合\(P\)

(2) \(P\)の点の順序対\((a,b)(a,bはPの点)\)の集合\(V\)

からなる.

\(a \ne b\)のとき\((a,b) \ne (b,a)\)である.

また

\((a,b)=(c,d)\Leftrightarrow (a=c\ and\ b=d）\)

\(V\)は\(P\)の自乗直積 \(P \times P= \{(a,b)|a,bはPの要素 \} \) の部分集合である.　すなわち,

\(V \subseteq P \times P\)

順序対\((a,b)\)は向きのついた枝,あるいは弧と呼ばれ,

(図5.1)

のように表すことができる。\(a\)は始点,\(b\)は終点と呼ばれる。 このような枝のまたは弧の図をつなぎ合わせば,有向グラフ \(G=(P,V)\)を平面図で表すことができる。

(図5.2)

\( P=\{ a,b,c,d,e,f \}　　\\ V=\{(a,b),(a,c),(b,d),(b,e),(c,e),(d,f),(e,f) \} \)

ラベル

有向グラフ\(G=(P,V)\)の弧には,長さや,所要時間などのデータでラベル付けされているとき \(G\)をラベル付き有向グラフといいます。

(図5.3)

路

節点の多重対 \((p_1,p_2,\cdots,p_k)\)で,各\((p_1,p_2),(p_2,p_3),\cdots,(p_{k-1},p_k)\)が\(V\) の元,すなわち弧であるものを 路といいます。

上の図では,\((a,b,e,f),(a,c,e),(b,d,f)\)などが路である.

最短路問題

\(G\)をラベル付き有向グラフとする。ただし,

(図5.4)

の\((b,e,f,d,b)\)のように「閉じた路」は含まないものとする。

さて,簡単にするため、集合\(P\)が\(n\)個の節点からなっているとして

\(P=\{1,2,\cdots,n\}\)とし,夫々の弧に付けられている,ラベルはその弧の長さを 表すものとしておく。

(図5.5)

弧をつなぎ合わせて作られる路の長さは,それを構成している弧の長さの和で 表します。例えば(図5)で路\((1,4,5,6)\)の長さは,\(20+20+30\)で\(70\)である.

節点1から出発して,節点nへ行くための長さ最小の路をどう求めるかという問題を考えます。(図5.5)の例では,路(1,2,5,6)が解で,長さ\(50\)である.

\(P\)の点の数が少なければ,路を全て調べてみるのも一つの方法であるが,数が多くなると 実用的ではない。

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

D.P.の原理

(図5.6)

　節点\(a\)から節点\(d\)への最短路が与えられたとする。その路が途中に節点\(b\)を経由しているとすると, その経路の\(a\)から\(b\)への部分の路も,やはり\(a\)から\(b\)への最短経路になっている.

実際,\(a\)から\(b\)への別の最短路があったとすると,例えば,(図6)の 節点\(c,e\)を経由して,\(b\)に行く路がそうであったとすると

\( L(a,c)+L(c,e)+L(e,b) \lt L(a,b) \)　

となり,これから

\( L(a,c)+L(c,e)+L(e,b)+L(b,d) \lt L(a,b)+L(b,d) \)

であるから,路\((a,c,e,b,d)\)が最短路\((a,b,d)\)より短くなってしまい, 路\((a,b,d)\)が最短であることに矛盾する.

結局, 「全体が最短（最適）ならその部分も最短（最適）」 である.

このような,性質を体系的に扱った最適化法の研究がベルマンによってなされた.

ベルマンの\(D.P.\)（ダイナミック・プログラミング）とか最適性の原理と呼ばれている.

再帰的な計算法

最適性の原理を使うと,例えば,接点\(i\)から\(k\)までの路が存在するとして,その中の 最短路\(R(i,k)\)の長さを\(O(i,k)\)で表すと

\(i\)から\(k\)までの弧\((i,k)\)が存在しない場合は\(L(i,k)=\infty\) としておき,　

\( O(i,k)=min\{ \{ L(i,k) \} \cup \{L(i,j)+O(j,k) |j \ne i,k,(i,j)はVの元\}\} \qquad (1a) \)

\( R(i,k)= \Big \{ \begin{array}{cc}(i,k) \quad & O(i,k)=L(i,k)のとき \\ (i,R(j_0,k)) & 上記以外でO(i,k)=L(i,j_0)+O(j_0,k),j_0 \ne i,(i,(j0,k))がVの元となるj_0を一つ選択 \\ \end{array} \qquad (1b） \)

という「再帰的」な定義ができる。

ここで,\((i,(j,\cdots,k))=(i,j,\cdots,k)\)とする。

これは,節点\(i\)からの弧\((i,j)\)が存在する節点\(j\)について,

節点\(j\)から節点\(k\) までの最短の長さ\(O(j,k)\)をもつ路\((j,\cdots,k)\)と 長さ\(L(i,j)\)の弧\((i,j)\) をつなげた路\((i,j,\cdots,k)\) の長さ

\(L(i,j)+O(j,k)\)

のうち,最短のものが\(O(i,k)\)であるという意味である.

(図5.5)

に適用すると

\( O(3,6)=20　　R(3,6)=(3,6) \\ O(5,6)=30　　R(5,6)=(5,6) \\ O(2,6) =min\{L(2,3)+O(3,6),L(2,5)+O(5,6)\} =min\{25+20,10+30\}　=40　 \\ R(2,6)=(2,5,6) \\ O(4,6) =L(4,5)+O(5,6) =50　　 \\ R(4,6)=(4,R(5,6))=(4,5,6) \\ O(1,6) =min\{L(1,2)+O(2,6),L(1,4)+O(4,6)\} =min\{10+40,20+50\}　 =50　 \\ R(1,6)=(1,R(2,6))=(1,2,5,6) \)

Dijkstraの方法

DPの原理を使った効率的な方法として,Dijkstraの方法が知られています。 <Dijkstra>

準備 \( K \leftarrow \phi \\ L \leftarrow P　 \\ O(j) \leftarrow \Big \{ \begin{array}{cc} 0 (j = 1) \\ \infty (j \ne 1) \\ \end{array} \)

手順1 \( 終了 (K = P) \)

\( O(m)=\min \{O(i)|iはLの元 \}となるLの元mを選ぶ. (K \ne P) \)

手順2 \( K \leftarrow K \cup \{m \}（Kに要素mを加えた集合を新たにKとする。）\\ L \leftarrow L \setminus \{m \}（Lからその要素mを除いた集合を新たにLとする。） \)

\((m,j)\)が\(V\)の元で,かつ,\(j\)が\(L\) の要素となる全ての\(j\) に対して以下の手続き[]を繰り返す。

[もし\(O(j) \gt O(m)+L(m,j)\) ならば \( O(j) \leftarrow O(m)+L(m,j) \quad R(j) \leftarrow m \) そうでなければ何もしない.]

手順1にもどる。

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

\(O(j)\)には節点\(1\)から節点\(j\)への最短の長さ, \(R(j)\)には節点\(1\)から節点\(j\)への最短路で,節点\(j\)の直前の節点の番号

が書き込まれている.

以下このDijkstraの方法を図5の例に適用してみる.

図5.5は、

\( P=\{1,2,3,4,5,6\} \\ V=\{(1,2),(1,4),(2,3),(2,5),(3,6),(4,5),(5,6)\} \\ L(1,2)=10, L(1,4)=20, L(2,3)=25, \\ L(2,5)=10, L(3,6)=20, L(4,5)=20, \\ L(5,6)=30 \)

準備 \( K \leftarrow \phi \\ L \leftarrow \{1,2,3,4,5,6\} \\ O(1) \leftarrow 0 \\ \)

\(\infty\) を999として

\( O(2) \leftarrow 999, O(3) \leftarrow 999, \\ O(4) \leftarrow 999, O(5) \leftarrow 999, \\ O(6) \leftarrow 999 \)

手順１(1回目) \( K \ne Pなので終了ではない O(m)=min\{O(1),O(2),O(3),O(4),O(5),O(6)\} =O(1) =0 \)

となり、m=1を選ぶ｡

手順２(1回目) \( K \leftarrow \{ 1\} L \leftarrow \{2,3,4,5,6\}\\ [ ~~j=2のとき ~~O(2)=999 ~~O(1) + L(1,2)=0+10=10なので ~~O(2) > O(1) + L(1,2) となり ~~O(2) \leftarrow 10 ~~R(2) \leftarrow 1 \\ ~~j=3のとき ~~(1,3)はVの元ではない。 \\ ~~j=4のとき ~~O(4) = 999 ~~O(1) + L(1,4) = 0 + 20 = 20 ~~O(4) > O(1) + L(1,4)となり ~~O(4) \leftarrow 20 ~~R(4) \leftarrow 1 \\ ~~j=5,6のとき ~~(1,5),(1,6)はVの元ではない ~] \)

手順１(2回目) \( K=\{1 \}なのでK \ne Pとなり終了ではない \\ O(2)=10, O(3)=999, O(4)=20, O(5)=999, O(6)=999なので O(m)=min\{O(2),O(3),O(4),O(5),O(6)\} =O(2) =10 \)

となり、\(m=2\)を選ぶ｡

手順２(２回目) \( K \leftarrow 　\{1\} \cup \{2\}=\{1,2\} \\ L \leftarrow \{3,4,5,6\} \\ [ ~~j=3のとき ~~O(3)=999 ~~O(2) + L(2,3)=10+25=35なので ~~O(3) > O(2) + L(2,3) となり ~~O(3) \leftarrow 35 ~~R(3) \leftarrow 2 \\ ~~j=4のとき ~~(2,4)はVの元ではない。\\ ~~j=5のとき ~~O(5) = 999 ~~O(2) + L(2,5) = 10 + 10 = 20 ~~O(5) > O(2) + L(2,5)となり ~~O(5) \leftarrow 20 ~~R(5) \leftarrow 2 \\ ~~j=6 ~~(2,6)はVの元ではない ~] \)

手順１(３回目) \( K=\{1,2\}なのでK \ne Pとなり終了ではない \\ O(3)=35,O(4)=20,O(5)=20,O(6)=999なので O(m)=min\{O(3),O(4),O(5),O(6)\} =O(4)　 =20 となり、m=4を選ぶ｡ \)

手順２(３回目) \( K \leftarrow \{1,2,4\} \\ L \leftarrow \{3,5,6\} \\ [ ~j=3のとき ~(4,3)はVの元ではない \\ ~j=5のとき ~O(5)=20 ~O(4) + L(4,5) = 20 + 20 = 40 ~O(5) < O(4) + L(4,5)となり,何もしない \\ ~j=6 ~(4,6)はVの元ではない ~] \)

手順１(４回目) \( 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 \)

となり、\(m=5\)を選ぶ｡

手順２(４回目) \( K \leftarrow \{1,2,4,5\} \\ L \leftarrow \{3,6\} \\ [ ~~j=3のとき ~~(5,3)はVの元ではない \\ ~~j=6のとき ~~O(6)=999 ~~O(5) + L(5,6) = 20 + 30 = 50 O(6) > O(5) + L(5,6)となり ~~O(6) \leftarrow 50 ~~R(6) \leftarrow 5 ~] \)

手順１(５回目) \( K=\{1,2,4,5\}なのでK \ne Pとなり終了ではない \\ O(3)=35,O(6)=50なので O(m)=min\{O(3),O(6)\} =O(3) =35 \)

となり\(m=3\)を選ぶ｡

手順２(５回目) \( K \leftarrow \{1,2,3,4,5\} \\ L \leftarrow \{6\} \\ ~~[ ~j=6のとき ~O(6)=50 ~O(3) + L(3,6) = 35 + 20 = 55 ~O(6) < O(3) + L(3,6)となり何もしない ] \)

手順１(６回目) \( K=\{1,2,3,4,5\}なのでK \ne Pとなり終了ではない \\ O(6)=50なので O(m)=min\{O(6)\} =O(6) =50 \)

となり、\(m=6\)を選ぶ｡

手順２(６回目) \( K \leftarrow \{1,2,3,4,5,6\} \\ L \leftarrow \phi \\ [ Lの要素がない ] \)

手順１(７回目) \(K=\{1,2,3,4,5,6\}\)なので\(K=P\)となり終了

節点1から節点\(6\)への最短の長さ \(O(6)=50\) 節点1から節点6への最短路で節点6の直前の節点の番号 \(R(6)=5\)

無向グラフ

最短路問題ではラベル付き有向グラフを扱ったが,ここでは,弧で結ばれている節点間は, 双方向に行き来できるものとする。

従って,図示した場合も始点,終点といった「向き」はない。 このようなグラフ\(G\)は無向グラフと呼ばれる。これは \( (1)節点の集合P (2)Pの点の非順序対\{a,b\}( a,bはPの点)の集合V \)

からなる。

\(\{a,b\}=\{b,a\}\)である.

この非順序対\{a,b\}も弧と呼ぶことにする。有向グラフのような始点,終点はない．

(図5.7)

のように表すことができる。有向グラフと同様に枝のまたは弧の図をつなぎ合わせば, グラフ\(G=(P,V)\)を平面図で表すことができる。

(図5.8)

\( P=\{a,b,c,d,e,f\} V=\{\{a,b\},\{a,c\},\{b,d\},\{b,e\},\{c,e\},\{d,f\},\{e,f\}\} \)

ラベル

有向グラフと全く同様に無向グラフG=(P,V)の弧にも,長さや,所要時間などのデータでラベル付け することができる。

(図5.9)

路

有向グラフと同様に節点の多重対 \((p_1,p_2,\cdots,p_k)\)で,各\(\{p_1,p_2\},\{p_2,p_3\},\cdots,\{p_{k-1},p_k\}\) が\(V\)の元,すなわち弧であるものを 路と呼ぶことにする。

上の図では,\((a,b,e,f),(a,c,e),(b,d,f)\)などが路である.

巡回セールスマン問題

さて,簡単にするため,集合\(P\)が\(n\)個の節点からなっているとして

\(P=\{1,2,\cdots,n\}\)とし,夫々の弧に付けられている,ラベルはその弧を移動する 費用は表すものとしておく。

(図5.10)

弧をつなぎ合わせて作られる路を移動する費用は,それを構成している弧の費用の和で 表します。上の図で路\((1,3,4,2)\)の費用は,20+20+40で80である.

巡回セールスマン問題は,各節点を,例えば都市に,費用を運賃として,都市１を出発して各都市\((2,3,4)\)を巡回（1回だけ訪れて）して, 再び都市１に戻ってくる,路の内費用最少の ものを求めるといった問題である.

(図5)の例では,路\((1,3,4,2,1)\)と\((1,2,4,3,1)\)が解で,費用が130である.

可能な路を全てを調べても,１番目の都市3通り\(\times\)2番目の都市2通り\(\times\)３番目の都市1通り=3!通りで順序を 逆に回っても同じであるから2で割って,結局3!/2通りである.しかし,都市の数が増えると非常に難しくなる。

D.P.の適用

有グラフ最短路問題と同様に最適性の原理を使って組織的に調べることができる。

例えば,都市\(1\)を出発して,\(\{2,3,4\}\)を巡回して,

最後に都市\(2\)を訪れるまでの最小費用を\(Cost(\{2,3,4\},2)\)で表すと, その最小になる路を通ってさらに都市\(1\)に戻ってくるまでの費用は

　　\(Cost(\{2,3,4\},2)+L\{2,1\}\)

である.全く同様に,費用最少で,\(\{2,3,4\}\)を巡回後,都市3を訪れ,都市\(1\) に戻る費用は

　　\(Cost(\{2,3,4\},3)+L\{3,1\}\)

\(\{2,3,4\}\)を巡回して,最後に都市4を訪れ,都市1に戻る費用は

　　\(Cost(\{2,3,4\},4)+L\{4,1\}\)

である. 結局,最小の費用は

\(min\{Cost(\{2,3,4\},2)+L\{2,1\},Cost(\{2,3,4\},3)+L\{3,1\} , Cost(\{2,3,4\},4)+L\{4,1\}\}\)

であり,その最少費用を実現する路が求めるものである.

有グラフの場合と同様に\(Cost(\{2,3,4\},2)\)も再帰的に, 　都市1を出発して,\(\{3,4\}\)を巡回して,最後に都市2を訪れるまでの 最小費用であるから

　都市1を出発して,\(\{3,4\}\)を巡回して都市3を訪れ,ついで都市2を訪れる費用

　\(Cost(\{3,4\},3)+L\{3,2\}\)

　都市1を出発して,\(\{3,4\}\)を巡回して都市4を訪れ,ついで都市2を訪れる費用

　\(Cost(\{3,4\},4)+L\{4,2\}\)

のうち何れか小さい方：

\(min\{Cost(\{3,4\},3)+L\{3,2\},Cost(\{3,4\},4)+L\{4,2\}\}\)

で求められる。

さらに,

\(Cost(\{3,4\},3)\)は路\((1,4,3)\)の費用であるから\(L\{1,4\}+L\{4,3\}=30+20=50\)

\(Cost(\{3,4\},4)\)は路\((1,3,4)\)の費用であるから\(L\{1,3\}+L\{3,4\}=20+20=40\)

である.

結局,最小の費用は以下の再帰的な計算により求めることができる。

\( min\{Cost(\{2,3,4\},2)+L\{2,1\},Cost(\{2,3,4\},3)+L\{3,1\},Cost(\{2,3,4\},4)+L\{4,1\} \} =min\{ 80+50,110+20 ,120+30 \} =130 \\ (1,3,4,2,1)または (1,2,4,3,1) \\　 Cost(\{2,3,4\},2) =min\{Cost(\{3,4\},3)+L\{3,2\},Cost(\{3,4\},4)+L\{4,2\}\} =min\{50+60,40+40\}=80 路は(1,3,4,2) \\ Cost(\{3,4\},3)=L\{1,4\}+L\{4,3\}=30+20=50 \\ Cost(\{3,4\},4)=L\{1,3\}+L\{3,4\}=20+20=40 \\ Cost(\{2,3,4\},3) =min\{Cost(\{2,4\},2)+L\{2,3\},Cost(\{2,4\},4)+L\{4,3\}\} =min\{70+60,90+20\}=110 路は(1,2,4,3) \\ Cost(\{2,4\},2)=L\{1,4\}+L\{4,2\}=30+40=70 \\ Cost(\{2,4\},4)=L\{1,2\}+L\{2,4\}=50+40=90 \\ Cost(\{2,3,4\},4) =min\{Cost(\{2,3\},2)+L\{2,4\},Cost(\{2,3\},3)+L\{3,4\}\} =min\{80+40,110+20\}=120 路は (1,3,2,4) \\ Cost(\{2,3\},2)=L\{1,3\}+L\{3,2\}=20+60=80 \\ Cost(\{2,3\},3)=L\{1,2\}+L\{2,3\}=50+60=110 \\ \)

しかしながら,この方法は組織的ではあるが,「全件探索」(全ての可能な候補を全て当たる) であり,都市の数が１0～20ぐらいまでが限界である.

分岐限定法

　ここで扱っている,巡回セールスマン問題には,解法の「決定打」はない。 問題の難しさを表す場合によく出てくる「NP困難問題」の一つである. 種々な方法が考案されている。「分岐限定法」もその一つである.