経路問題
提供: Internet Web School
=={最短経路問題}
目次[非表示] |
ラベル付き有向グラフ
有向グラフ
有向グラフは,ここではGで表しますが,コンピュータや,ネットワークにもよく使われ ます。有向グラフGは
(1) 節点の集合P
(2) Pの点の順序対(a,b)(a,bはPの点)の集合V
からなる.
a≠bのとき(a,b)≠(b,a)である.
また
(a,b)=(c,d)⇔(a=c and b=d)
VはPの自乗直積 P×P={(a,b)|a,bはPの要素} の部分集合である. すなわち,
V⊆P×P
順序対(a,b)は向きのついた枝,あるいは弧と呼ばれ,
のように表すことができる。aは始点,bは終点と呼ばれる。 このような枝のまたは弧の図をつなぎ合わせば,有向グラフ G=(P,V)を平面図で表すことができる。
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をラベル付き有向グラフといいます。
路
節点の多重対 (p1,p2,⋯,pk)で,各(p1,p2),(p2,p3),⋯,(pk−1,pk)がV の元,すなわち弧であるものを 路といいます。
上の図では,(a,b,e,f),(a,c,e),(b,d,f)などが路である.
最短路問題
Gをラベル付き有向グラフとする。ただし,
の(b,e,f,d,b)のように「閉じた路」は含まないものとする。
さて,簡単にするため、集合Pがn個の節点からなっているとして
P={1,2,⋯,n}とし,夫々の弧に付けられている,ラベルはその弧の長さを 表すものとしておく。
弧をつなぎ合わせて作られる路の長さは,それを構成している弧の長さの和で 表します。例えば(図5)で路(1,4,5,6)の長さは,20+20+30で70である.
節点1から出発して,節点nへ行くための長さ最小の路をどう求めるかという問題を考えます。(図5.5)の例では,路(1,2,5,6)が解で,長さ50である.
Pの点の数が少なければ,路を全て調べてみるのも一つの方法であるが,数が多くなると 実用的ではない。
D.P.(ダイナミック・プログラミング)と最短路
D.P.の原理
節点aから節点dへの最短路が与えられたとする。その路が途中に節点bを経由しているとすると, その経路のaからbへの部分の路も,やはりaからbへの最短経路になっている.
実際,aからbへの別の最短路があったとすると,例えば,(図6)の 節点c,eを経由して,bに行く路がそうであったとすると
L(a,c)+L(c,e)+L(e,b)<L(a,b)
となり,これから
L(a,c)+L(c,e)+L(e,b)+L(b,d)<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)=∞ としておき,
O(i,k)=min{{L(i,k)}∪{L(i,j)+O(j,k)|j≠i,k,(i,j)はVの元}}(1a)
R(i,k)={(i,k)O(i,k)=L(i,k)のとき(i,R(j0,k))上記以外でO(i,k)=L(i,j0)+O(j0,k),j0≠i,(i,(j0,k))がVの元となるj0を一つ選択(1b)
という「再帰的」な定義ができる。
ここで,(i,(j,⋯,k))=(i,j,⋯,k)とする。
これは,節点iからの弧(i,j)が存在する節点jについて,
節点jから節点k までの最短の長さO(j,k)をもつ路(j,⋯,k)と 長さL(i,j)の弧(i,j) をつなげた路(i,j,⋯,k) の長さ
L(i,j)+O(j,k)
のうち,最短のものがO(i,k)であるという意味である.
に適用すると
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←ϕL←P O(j)←{0(j=1)∞(j≠1)
手順1
終了(K=P)
O(m)=min{O(i)|iはLの元}となるLの元mを選ぶ.(K≠P)
手順2
K←K∪{m}(Kに要素mを加えた集合を新たにKとする。)L←L∖{m}(Lからその要素mを除いた集合を新たにLとする。)
(m,j)がVの元で,かつ,jがL の要素となる全てのj に対して以下の手続きを繰り返す。
もし, O(j)>O(m)+L(m,j) ならば O(j)←O(m)+L(m,j)R(j)←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←ϕL←{1,2,3,4,5,6}O(1)←0
∞ を999として
O(2)←999,O(3)←999,O(4)←999,O(5)←999,O(6)←999
手順1(1回目)
K≠Pなので終了ではないO(m)=min{O(1),O(2),O(3),O(4),O(5),O(6)}=O(1)=0
となり、m=1を選ぶ。
手順2(1回目)
K←{1}L←{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)←10 R(2)←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)←20 R(4)←1 j=5,6のとき (1,5),(1,6)はVの元ではない >>
手順1(2回目)
K={1}なのでK≠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を選ぶ。
手順2(2回目)
K← {1}∪{2}={1,2}L←{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)←35 R(3)←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)←20 R(5)←2 j=6 (2,6)はVの元ではない >>
手順1(3回目)
K={1,2}なのでK≠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を選ぶ。
手順2(3回目)
K←{1,2,4}L←{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の元ではない >>
手順1(4回目)
K={1,2,4}なのでK≠Pとなり終了ではないO(3)=35,O(5)=20,O(6)=999なのでO(m)=min{O(3),O(5),O(6)}=O(5)=20
となり、m=5を選ぶ。
手順2(4回目)
K←{1,2,4,5}L←{3,6}[[利用者:Moderator|Moderator]]<< j=3のとき (5,3)はVの元ではない j=6のとき O(6)=999 O(5)+L(5,6)=20+30=50O(6)>O(5)+L(5,6)となり O(6)←50 R(6)←5 >>
手順1(5回目)
K={1,2,4,5}なのでK≠Pとなり終了ではないO(3)=35,O(6)=50なのでO(m)=min{O(3),O(6)}=O(3)=35 となり、m=3を選ぶ。
手順2(5回目)
K←{1,2,3,4,5}L←{6} << j=6のとき O(6)=50 O(3)+L(3,6)=35+20=55 O(6)<O(3)+L(3,6)となり何もしない>>
手順1(6回目)
K={1,2,3,4,5}なのでK≠Pとなり終了ではないO(6)=50なのでO(m)=min{O(6)}=O(6)=50
となり、m=6を選ぶ。
手順2(6回目)
K←{1,2,3,4,5,6}L←ϕ<<Lの要素がない>>
手順1(7回目)
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\}も弧と呼ぶことにする。有向グラフのような始点,終点はない.
\vspace{2cm} \par
(図5.7)
のように表すことができる。有向グラフと同様に枝のまたは弧の図をつなぎ合わせば, グラフG=(P,V)を平面図で表すことができる。
\vspace{5cm} \par
(図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)
路
有向グラフと同様に節点の多重対 (p1,p2,⋯,pk)で,各{p1,p2},{p2,p3},⋯,{pk−1,pk} がVの元,すなわち弧であるものを 路と呼ぶことにする。
上の図では,(a,b,e,f),(a,c,e),(b,d,f)などが路である.
巡回セールスマン問題
さて,簡単にするため,集合Pがn個の節点からなっているとして
P={1,2,⋯,n}とし,夫々の弧に付けられている,ラベルはその弧を移動する 費用は表すものとしておく。 下の図では,節点の番号と区別できるよう()付の数字で表しておく。
\vspace{5cm} \par
(図5.10)
弧をつなぎ合わせて作られる路を移動する費用は,それを構成している弧の費用の和で 表します。上の図で路(1,3,4,2)の費用は,20+20+40で80である.
巡回セールスマン問題は,各節点を,例えば都市に,費用を運賃として,都市1を出発して各都市(2,3,4)を巡回(1回だけ訪れて)して, 再び都市1に戻ってくる,路の内費用最少の ものを求めるといった問題である.
(図5)の例では,路(1,3,4,2,1)と(1,2,4,3,1)が解で,費用が130である. 可能な路を全てを調べても,1番目の都市3通り×2番目の都市2通り×3番目の都市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=50Cost({3,4},4)=L{1,3}+L{3,4}=20+20=40Cost({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=70Cost({2,4},4)=L{1,2}+L{2,4}=50+40=90Cost({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=80Cost({2,3},3)=L{1,2}+L{2,3}=50+60=110
しかしながら,この方法は組織的ではありますが,「全件探索」(全ての可能な候補を全て当たる) であり,都市の数が10~20ぐらいまでが限界である.
分岐限定法
ここで扱っている,巡回セールスマン問題には,解法の「決定打」はない。 問題の難しさを表す場合によく出てくる「NP困難問題」の一つである. 種々な方法が考案されている。「分岐限定法」もその一つである.
かなり作為的であるが,以下の例を考えます。 \vspace{5cm} \par
(図5.11)
都市1を出発し,各都市を1回ずつ訪れ,都市1に戻ってくる路を全て,逆周りも含めて,列挙すれば, (1,2,3,4,1),(1,2,4,3,1),(1,3,2,4,1),(1,3,4,2,1),(1,4,2,3,1),(1,4,3,2,1)
である.これらの路は1番目,2番目,3番目に訪れる都市によって分類できる。 例えば,1番目に訪れる都市に注目して
(?)1番目の都市が2のもの (1,2,3,4,1),(1,2,4,3,1)>
(?)1番目の都市が3のもの (1,3,2,4,1),(1,3,4,2,1)>
(?)1番目の都市が4のもの (1,4,2,3,1),(1,4,3,2,1)>
である.?,?,?の中でそれぞれ,最少費用の路を探す問題は部分問題と呼ばれる。 さらに?,?,?の分類を2番目,3番目によって,細かく分類ができる。解の候補の「分岐」がでてくるわけである.
ここで,解の候補として路の(1,3,4,2,1)を選んだとする。この路の費用は130である. 部分問題?,すなわち,?の分類の中で費用最少を調べ見ると: 路(弧)</math>(1,4)</math>だけで,既に費用が130であり,費用がマイナスの弧はないのであるから, この?の分類のものの最少費用は130より大である.従って,これ以上細かく調べる必要はない。 すると,解は,路の(1,3,4,2,1)を含む,(?)か(?)から探せばよい事になります。 このようにして,探すべき解の候補の「枝」のうち,無駄なものを削除する事ができる。
さらに,路(1,2,3),(1,3,2)も費用が130であるから,これらの後の節点がなんであろうと,費用は 130より大きくなります。この例では,以後の分岐はないので,これが判っても効用はあり ませんが,もしさらに分岐があるなら,無駄な「枝」を削除できることになります。
この様にして,結局, (1,3,4,2,1), (1,2,4,3,1) にたどりつく。
無論,問題のよって,また,部分問題にの作製(分類)の仕方によって,最悪,全ての路を調べる事に なる場合もあります。以上のような解法を一般的に表すと,
最小化問題Pが与えられたとして:
===(1)=== Pから,部分問題の集合L={P0,P1,P2,⋯,Pn}を作り,
初期解を適当に選択してその値C0を求める。
以下の手続きをLの元Piの全てについて行う
===(2)===最小問題Piの解の下限値infPiを求め,
infPi> C0なら L←L∖{Pi}
(LからPiを削除)
===(3)=== 最小問題Piの解minPi<m/ath>を求め <math>minPi < C0なら C0←minPi とする
図5.10の問題について,「分岐限定法」を適用すると例えば以下のようになります。
これは、本大学院の社会人学生久保さんにやっていただいたものである.上の例より
スマートな解法である.
都市1を出発し,各都市を1回ずつ訪れ,都市1に戻ってくる路を全て,逆周りも含めて,列挙すると,
(1,2,3,4,1),(1,2,4,3,1),(1,3,2,4,1),(1,3,4,2,1),(1,4,2,3,1),(1,4,3,2,1)>
である.これらの路は費用最小の{1,3},{3,4}の両方を通るものと, 通らないものに分類できる.
{1,3},{3,4}の両方を通るもの
(1,2,4,3,1),(1,3,4,2,1)>
\item{(?)}\{1,3\},\{3,4\}の両方は通らないもの
(1,2,3,4,1),(1,3,2,4,1),(1,4,2,3,1),(1,4,3,2,1)>
である.
ここで,解の候補として(?)から路(1,2,4,3,1)を選んだとする. この路の費用は130である.
部分問題(?)で費用を調べて見ると,費用20の路が1つしか通れないことから, 各路の費用は 20,30,40,50,60 で,この中から4つを選ぶことから下限値は140となる. 140>130なので,は削除できる.
残った()から探せばよい事になるが,路(1,3,4,2,1)の費用も130となり, (1,3,4,2,1),(1,2,4,3,1)> にたどりつく.
図5.11の問題について,「D.P.」を適用すると:
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,140+130}=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{150+80,40+40}=80路は(1,3,4,2)Cost({3,4},3)=L{1,4}+L{4,3}=130+20=150Cost({3,4},4)=L{1,3}+L{3,4}=20+20=40Cost({2,3,4},3)=min{Cost({2,4},2)+L{2,3},Cost({2,4},4)+L{4,3}}=min{170+80,90+20}=110路は(1,2,4,3)Cost({2,4},2)=L{1,4}+L{4,2}=130+40=170Cost({2,4},4)=L{1,2}+L{2,4}=50+40=90Cost({2,3,4},4)=min{Cost({2,3},2)+L{2,4},Cost({2,3},3)+L{3,4}}=min{100+40,130+20}=140路は(1,3,2,4)Cost({2,3},2)=L{1,3}+L{3,2}=20+80=100Cost({2,3},3)=L{1,2}+L{2,3}=50+80=130