経路問題
提供: Internet Web School
(→手順1) |
(→Dijkstraの方法) |
||
(間の45版分が非表示) | |||
1 行: | 1 行: | ||
- | + | ==有向グラフ== | |
- | + | 有向グラフは,ここでは<math>G</math>で表すが,コンピュータや,ネットワークにもよく使われる。有向グラフ<math>G</math>は | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | 有向グラフは,ここでは<math>G</math> | + | |
- | + | ||
33 行: | 26 行: | ||
順序対<math>(a,b)</math>は向きのついた枝,あるいは弧と呼ばれ, | 順序対<math>(a,b)</math>は向きのついた枝,あるいは弧と呼ばれ, | ||
- | (図5.1) [[ファイル:Fig5.1.gif]] | + | (図5.1) [[ファイル:Fig5.1.gif|300px]] |
のように表すことができる。<math>a</math>は始点,<math>b</math>は終点と呼ばれる。 | のように表すことができる。<math>a</math>は始点,<math>b</math>は終点と呼ばれる。 | ||
40 行: | 33 行: | ||
- | (図5.2) [[ファイル:Fig5.2.gif]] | + | (図5.2) [[ファイル:Fig5.2.gif|400px]] |
53 行: | 46 行: | ||
<math>G</math>をラベル付き有向グラフといいます。 | <math>G</math>をラベル付き有向グラフといいます。 | ||
- | (図5.3) [[ファイル:Fig5.3.gif]] | + | (図5.3) [[ファイル:Fig5.3.gif|400px]] |
===路=== | ===路=== | ||
68 行: | 61 行: | ||
<math>G</math>をラベル付き有向グラフとする。ただし, | <math>G</math>をラベル付き有向グラフとする。ただし, | ||
- | (図5.4) [[ファイル:Fig5.4.gif]] | + | (図5.4) [[ファイル:Fig5.4.gif|400px]] |
の<math>(b,e,f,d,b)</math>のように「閉じた路」は含まないものとする。 | の<math>(b,e,f,d,b)</math>のように「閉じた路」は含まないものとする。 | ||
77 行: | 70 行: | ||
表すものとしておく。 | 表すものとしておく。 | ||
- | (図5.5) [[ファイル:Fig5.5.gif]] | + | (図5.5) [[ファイル:Fig5.5.gif|400px]] |
弧をつなぎ合わせて作られる路の長さは,それを構成している弧の長さの和で | 弧をつなぎ合わせて作られる路の長さは,それを構成している弧の長さの和で | ||
94 行: | 87 行: | ||
- | (図5.6) [[ファイル:Fig5.6.gif]] | + | (図5.6) [[ファイル:Fig5.6.gif|400px]] |
節点<math>a</math>から節点<math>d</math>への最短路が与えられたとする。その路が途中に節点<math>b</math>を経由しているとすると, | 節点<math>a</math>から節点<math>d</math>への最短路が与えられたとする。その路が途中に節点<math>b</math>を経由しているとすると, | ||
140 行: | 133 行: | ||
R(i,k)= \Big \{ | R(i,k)= \Big \{ | ||
\begin{array}{cc}(i,k) \quad & O(i,k)=L(i,k)のとき \\ | \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,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} | \end{array} | ||
163 行: | 156 行: | ||
のうち,最短のものが<math>O(i,k)</math>であるという意味である. | のうち,最短のものが<math>O(i,k)</math>であるという意味である. | ||
- | (図5.5) [[ファイル:Fig5.5.gif]] | + | (図5.5) [[ファイル:Fig5.5.gif|400px]] |
188 行: | 181 行: | ||
===Dijkstraの方法=== | ===Dijkstraの方法=== | ||
- | DPの原理を使った効率的な方法として, | + | DPの原理を使った効率的な方法として,Dijkstraの方法が知られている. |
- | + | [https://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95 Dijkstraのアルゴリズム] | |
+ | (Wikipedia) | ||
- | + | '''準備''' | |
<math> | <math> | ||
K \leftarrow \phi \\ | K \leftarrow \phi \\ | ||
203 行: | 197 行: | ||
</math> | </math> | ||
- | + | '''手順1''' | |
<math> | <math> | ||
- | + | 終了 (K = P) | |
- | 終了 | + | |
- | + | ||
- | + | ||
</math> | </math> | ||
- | = | + | <math> |
+ | O(m)=\min \{O(i)|iはLの元 \}となるLの元mを選ぶ. (K \ne P) | ||
+ | </math> | ||
+ | |||
+ | '''手順2''' | ||
<math> | <math> | ||
K \leftarrow K \cup \{m \}(Kに要素mを加えた集合を新たにKとする。)\\ | K \leftarrow K \cup \{m \}(Kに要素mを加えた集合を新たにKとする。)\\ | ||
219 行: | 214 行: | ||
<math>(m,j)</math>が<math>V</math>の元で,かつ,<math>j</math>が<math>L</math> | <math>(m,j)</math>が<math>V</math>の元で,かつ,<math>j</math>が<math>L</math> | ||
の要素となる全ての<math>j</math> | の要素となる全ての<math>j</math> | ||
- | + | に対して以下の手続き[]を繰り返す。 | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | [もし<math>O(j) \gt O(m)+L(m,j)</math> ならば | |
+ | <math> O(j) \leftarrow O(m)+L(m,j) \quad R(j) \leftarrow m </math> そうでなければ何もしない.] | ||
- | + | '''手順1にもどる。''' | |
255 行: | 241 行: | ||
</math> | </math> | ||
- | + | '''準備''' | |
<math> | <math> | ||
K \leftarrow \phi \\ | K \leftarrow \phi \\ | ||
270 行: | 256 行: | ||
</math> | </math> | ||
- | + | '''手順1(1回目)''' | |
<math> | <math> | ||
K \ne Pなので終了ではない | K \ne Pなので終了ではない | ||
280 行: | 266 行: | ||
となり、m=1を選ぶ。 | となり、m=1を選ぶ。 | ||
- | + | '''手順2(1回目)''' | |
<math> | <math> | ||
K \leftarrow \{ 1\} | K \leftarrow \{ 1\} | ||
- | L \leftarrow \{2,3,4,5,6\} | + | L \leftarrow \{2,3,4,5,6\}\\ |
- | + | [ | |
~~j=2のとき | ~~j=2のとき | ||
~~O(2)=999 | ~~O(2)=999 | ||
290 行: | 276 行: | ||
~~O(2) > O(1) + L(1,2) となり | ~~O(2) > O(1) + L(1,2) となり | ||
~~O(2) \leftarrow 10 | ~~O(2) \leftarrow 10 | ||
- | ~~R(2) \leftarrow 1 | + | ~~R(2) \leftarrow 1 \\ |
~~j=3のとき | ~~j=3のとき | ||
- | ~~(1,3)はVの元ではない。 | + | ~~(1,3)はVの元ではない。 \\ |
~~j=4のとき | ~~j=4のとき | ||
~~O(4) = 999 | ~~O(4) = 999 | ||
298 行: | 284 行: | ||
~~O(4) > O(1) + L(1,4)となり | ~~O(4) > O(1) + L(1,4)となり | ||
~~O(4) \leftarrow 20 | ~~O(4) \leftarrow 20 | ||
- | ~~R(4) \leftarrow 1 | + | ~~R(4) \leftarrow 1 \\ |
~~j=5,6のとき | ~~j=5,6のとき | ||
~~(1,5),(1,6)はVの元ではない | ~~(1,5),(1,6)はVの元ではない | ||
- | ~ | + | ~] |
</math> | </math> | ||
- | + | '''手順1(2回目)''' | |
<math> | <math> | ||
- | K=\{1 \}なのでK \ne Pとなり終了ではない | + | K=\{1 \}なのでK \ne Pとなり終了ではない \\ |
O(2)=10, O(3)=999, O(4)=20, O(5)=999, O(6)=999なので | 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(m)=min\{O(2),O(3),O(4),O(5),O(6)\} | ||
315 行: | 301 行: | ||
となり、<math>m=2</math>を選ぶ。 | となり、<math>m=2</math>を選ぶ。 | ||
- | + | '''手順2(2回目)''' | |
<math> | <math> | ||
- | K \leftarrow \{1\} \cup \{2\}=\{1,2\} | + | K \leftarrow \{1\} \cup \{2\}=\{1,2\} \\ |
- | L \leftarrow \{3,4,5,6\} | + | L \leftarrow \{3,4,5,6\} \\ |
- | + | [ | |
~~j=3のとき | ~~j=3のとき | ||
~~O(3)=999 | ~~O(3)=999 | ||
325 行: | 311 行: | ||
~~O(3) > O(2) + L(2,3) となり | ~~O(3) > O(2) + L(2,3) となり | ||
~~O(3) \leftarrow 35 | ~~O(3) \leftarrow 35 | ||
- | ~~R(3) \leftarrow 2 | + | ~~R(3) \leftarrow 2 \\ |
~~j=4のとき | ~~j=4のとき | ||
- | ~~(2,4)はVの元ではない。 | + | ~~(2,4)はVの元ではない。\\ |
- | ~~j=5のとき | + | ~~j=5のとき |
~~O(5) = 999 | ~~O(5) = 999 | ||
~~O(2) + L(2,5) = 10 + 10 = 20 | ~~O(2) + L(2,5) = 10 + 10 = 20 | ||
~~O(5) > O(2) + L(2,5)となり | ~~O(5) > O(2) + L(2,5)となり | ||
~~O(5) \leftarrow 20 | ~~O(5) \leftarrow 20 | ||
- | ~~R(5) \leftarrow 2 | + | ~~R(5) \leftarrow 2 \\ |
~~j=6 | ~~j=6 | ||
~~(2,6)はVの元ではない | ~~(2,6)はVの元ではない | ||
- | ~ | + | ~] |
</math> | </math> | ||
- | + | '''手順1(3回目)''' | |
<math> | <math> | ||
- | K=\{1,2\}なのでK \ne Pとなり終了ではない | + | K=\{1,2\}なのでK \ne Pとなり終了ではない \\ |
O(3)=35,O(4)=20,O(5)=20,O(6)=999なので | O(3)=35,O(4)=20,O(5)=20,O(6)=999なので | ||
O(m)=min\{O(3),O(4),O(5),O(6)\} | O(m)=min\{O(3),O(4),O(5),O(6)\} | ||
349 行: | 335 行: | ||
</math> | </math> | ||
- | + | '''手順2(3回目)''' | |
<math> | <math> | ||
- | K \leftarrow \{1,2,4\} | + | K \leftarrow \{1,2,4\} \\ |
- | L \leftarrow \{3,5,6\} | + | L \leftarrow \{3,5,6\} \\ |
- | + | [ | |
~j=3のとき | ~j=3のとき | ||
- | ~(4,3)はVの元ではない | + | ~(4,3)はVの元ではない \\ |
- | ~j=5のとき | + | ~j=5のとき |
~O(5)=20 | ~O(5)=20 | ||
~O(4) + L(4,5) = 20 + 20 = 40 | ~O(4) + L(4,5) = 20 + 20 = 40 | ||
- | ~O(5) < O(4) + L(4,5) | + | ~O(5) < O(4) + L(4,5)となり,何もしない \\ |
~j=6 | ~j=6 | ||
~(4,6)はVの元ではない | ~(4,6)はVの元ではない | ||
- | ~ | + | ~] |
</math> | </math> | ||
- | + | ||
+ | '''手順1(4回目)''' | ||
<math> | <math> | ||
K=\{1,2,4\}なのでK \ne Pとなり終了ではない | K=\{1,2,4\}なのでK \ne Pとなり終了ではない | ||
375 行: | 362 行: | ||
となり、<math>m=5</math>を選ぶ。 | となり、<math>m=5</math>を選ぶ。 | ||
- | + | '''手順2(4回目)''' | |
<math> | <math> | ||
- | K \leftarrow \{1,2,4,5\} | + | K \leftarrow \{1,2,4,5\} \\ |
- | L \leftarrow \{3,6\} | + | L \leftarrow \{3,6\} \\ |
- | [ | + | [ |
~~j=3のとき | ~~j=3のとき | ||
- | ~~(5,3)はVの元ではない | + | ~~(5,3)はVの元ではない \\ |
~~j=6のとき | ~~j=6のとき | ||
~~O(6)=999 | ~~O(6)=999 | ||
387 行: | 374 行: | ||
~~O(6) \leftarrow 50 | ~~O(6) \leftarrow 50 | ||
~~R(6) \leftarrow 5 | ~~R(6) \leftarrow 5 | ||
- | ~ | + | ~] |
</math> | </math> | ||
- | + | '''手順1(5回目)''' | |
<math> | <math> | ||
- | K=\{1,2,4,5\}なのでK \ne Pとなり終了ではない | + | K=\{1,2,4,5\}なのでK \ne Pとなり終了ではない \\ |
- | O(3)=35,O(6)=50なので | + | |
- | O(m)=min\{O(3),O(6)\} | + | O(3)=35,O(6)=50なので O(m)=min\{O(3),O(6)\} =O(3) =35 |
- | =O(3) | + | |
- | =35 | + | |
</math> | </math> | ||
- | |||
- | = | + | となり<math>m=3</math>を選ぶ。 |
+ | |||
+ | '''手順2(5回目)''' | ||
<math> | <math> | ||
- | K \leftarrow \{1,2,3,4,5\} | + | K \leftarrow \{1,2,3,4,5\} \\ |
- | L \leftarrow \{6\} | + | L \leftarrow \{6\} \\ |
- | ~~ | + | ~~[ |
~j=6のとき | ~j=6のとき | ||
~O(6)=50 | ~O(6)=50 | ||
~O(3) + L(3,6) = 35 + 20 = 55 | ~O(3) + L(3,6) = 35 + 20 = 55 | ||
~O(6) < O(3) + L(3,6)となり何もしない | ~O(6) < O(3) + L(3,6)となり何もしない | ||
- | + | ] | |
</math> | </math> | ||
- | + | '''手順1(6回目)''' | |
<math> | <math> | ||
- | K=\{1,2,3,4,5\}なのでK \ne Pとなり終了ではない | + | K=\{1,2,3,4,5\}なのでK \ne Pとなり終了ではない \\ |
O(6)=50なので | O(6)=50なので | ||
O(m)=min\{O(6)\} | O(m)=min\{O(6)\} | ||
423 行: | 409 行: | ||
となり、<math>m=6</math>を選ぶ。 | となり、<math>m=6</math>を選ぶ。 | ||
- | + | '''手順2(6回目)''' | |
<math> | <math> | ||
- | K \leftarrow \{1,2,3,4,5,6\} | + | K \leftarrow \{1,2,3,4,5,6\} \\ |
- | L \leftarrow \phi | + | L \leftarrow \phi \\ |
- | + | [ | |
Lの要素がない | Lの要素がない | ||
- | + | ] | |
</math> | </math> | ||
- | + | '''手順1(7回目)''' | |
<math>K=\{1,2,3,4,5,6\}</math>なので<math>K=P</math>となり終了 | <math>K=\{1,2,3,4,5,6\}</math>なので<math>K=P</math>となり終了 | ||
442 行: | 428 行: | ||
==無向グラフ== | ==無向グラフ== | ||
最短路問題ではラベル付き有向グラフを扱ったが,ここでは,弧で結ばれている節点間は, | 最短路問題ではラベル付き有向グラフを扱ったが,ここでは,弧で結ばれている節点間は, | ||
- | + | 双方向に行き来できるものとする。 | |
+ | |||
+ | 従って,図示した場合も始点,終点といった「向き」はない。 | ||
このようなグラフ<math>G</math>は無向グラフと呼ばれる。これは | このようなグラフ<math>G</math>は無向グラフと呼ばれる。これは | ||
<math> | <math> | ||
449 行: | 437 行: | ||
</math> | </math> | ||
- | + | からなる。 | |
<math>\{a,b\}=\{b,a\}</math>である. | <math>\{a,b\}=\{b,a\}</math>である. | ||
455 行: | 443 行: | ||
この非順序対\{a,b\}も弧と呼ぶことにする。有向グラフのような始点,終点はない. | この非順序対\{a,b\}も弧と呼ぶことにする。有向グラフのような始点,終点はない. | ||
- | |||
- | |||
- | |||
(図5.7) | (図5.7) | ||
+ | [[ファイル:Fig5.7.gif|300px]] | ||
+ | |||
のように表すことができる。有向グラフと同様に枝のまたは弧の図をつなぎ合わせば, | のように表すことができる。有向グラフと同様に枝のまたは弧の図をつなぎ合わせば, | ||
グラフ<math>G=(P,V)</math>を平面図で表すことができる。 | グラフ<math>G=(P,V)</math>を平面図で表すことができる。 | ||
- | |||
- | |||
- | |||
(図5.8) | (図5.8) | ||
+ | |||
+ | [[ファイル:Fig5.8.gif|400px]] | ||
+ | |||
<math> | <math> | ||
P=\{a,b,c,d,e,f\} | P=\{a,b,c,d,e,f\} | ||
V=\{\{a,b\},\{a,c\},\{b,d\},\{b,e\},\{c,e\},\{d,f\},\{e,f\}\} | V=\{\{a,b\},\{a,c\},\{b,d\},\{b,e\},\{c,e\},\{d,f\},\{e,f\}\} | ||
</math> | </math> | ||
+ | |||
481 行: | 469 行: | ||
(図5.9) | (図5.9) | ||
- | [[ファイル:Fig5.9.gif]] | + | [[ファイル:Fig5.9.gif|400px]] |
===路=== | ===路=== | ||
499 行: | 487 行: | ||
<math>P=\{1,2,\cdots,n\}</math>とし,夫々の弧に付けられている,ラベルはその弧を移動する | <math>P=\{1,2,\cdots,n\}</math>とし,夫々の弧に付けられている,ラベルはその弧を移動する | ||
費用は表すものとしておく。 | 費用は表すものとしておく。 | ||
- | |||
- | |||
- | |||
- | |||
(図5.10) | (図5.10) | ||
+ | [[ファイル:Fig5.10.gif|400px]] | ||
弧をつなぎ合わせて作られる路を移動する費用は,それを構成している弧の費用の和で | 弧をつなぎ合わせて作られる路を移動する費用は,それを構成している弧の費用の和で | ||
514 行: | 499 行: | ||
(図5)の例では,路<math>(1,3,4,2,1)</math>と<math>(1,2,4,3,1)</math>が解で,費用が130である. | (図5)の例では,路<math>(1,3,4,2,1)</math>と<math>(1,2,4,3,1)</math>が解で,費用が130である. | ||
- | |||
- | |||
+ | 可能な路を全てを調べても,1番目の都市3通り<math>\times</math>2番目の都市2通り<math>\times</math>3番目の都市1通り=3!通りで順序を | ||
+ | 逆に回っても同じであるから2で割って,結局3!/2通りである.しかし,都市の数が増えると非常に難しくなる。 | ||
===D.P.の適用=== | ===D.P.の適用=== | ||
523 行: | 508 行: | ||
例えば,都市<math>1</math>を出発して,<math>\{2,3,4\}</math>を巡回して, | 例えば,都市<math>1</math>を出発して,<math>\{2,3,4\}</math>を巡回して, | ||
+ | |||
最後に都市<math>2</math>を訪れるまでの最小費用を<math>Cost(\{2,3,4\},2)</math>で表すと, | 最後に都市<math>2</math>を訪れるまでの最小費用を<math>Cost(\{2,3,4\},2)</math>で表すと, | ||
その最小になる路を通ってさらに都市<math>1</math>に戻ってくるまでの費用は | その最小になる路を通ってさらに都市<math>1</math>に戻ってくるまでの費用は | ||
+ | |||
<math>Cost(\{2,3,4\},2)+L\{2,1\}</math> | <math>Cost(\{2,3,4\},2)+L\{2,1\}</math> | ||
+ | |||
である.全く同様に,費用最少で,<math>\{2,3,4\}</math>を巡回後,都市3を訪れ,都市<math>1</math> | である.全く同様に,費用最少で,<math>\{2,3,4\}</math>を巡回後,都市3を訪れ,都市<math>1</math> | ||
に戻る費用は | に戻る費用は | ||
+ | |||
<math>Cost(\{2,3,4\},3)+L\{3,1\}</math> | <math>Cost(\{2,3,4\},3)+L\{3,1\}</math> | ||
+ | |||
<math>\{2,3,4\}</math>を巡回して,最後に都市4を訪れ,都市1に戻る費用は | <math>\{2,3,4\}</math>を巡回して,最後に都市4を訪れ,都市1に戻る費用は | ||
+ | |||
<math>Cost(\{2,3,4\},4)+L\{4,1\}</math> | <math>Cost(\{2,3,4\},4)+L\{4,1\}</math> | ||
+ | |||
である. | である. | ||
結局,最小の費用は | 結局,最小の費用は | ||
+ | |||
<math>min\{Cost(\{2,3,4\},2)+L\{2,1\},Cost(\{2,3,4\},3)+L\{3,1\} , | <math>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\}\}</math> | Cost(\{2,3,4\},4)+L\{4,1\}\}</math> | ||
+ | |||
であり,その最少費用を実現する路が求めるものである. | であり,その最少費用を実現する路が求めるものである. | ||
540 行: | 534 行: | ||
都市1を出発して,<math>\{3,4\}</math>を巡回して,最後に都市2を訪れるまでの | 都市1を出発して,<math>\{3,4\}</math>を巡回して,最後に都市2を訪れるまでの | ||
最小費用であるから | 最小費用であるから | ||
+ | |||
都市1を出発して,<math>\{3,4\}</math>を巡回して都市3を訪れ,ついで都市2を訪れる費用 | 都市1を出発して,<math>\{3,4\}</math>を巡回して都市3を訪れ,ついで都市2を訪れる費用 | ||
+ | |||
<math>Cost(\{3,4\},3)+L\{3,2\}</math> | <math>Cost(\{3,4\},3)+L\{3,2\}</math> | ||
+ | |||
都市1を出発して,<math>\{3,4\}</math>を巡回して都市4を訪れ,ついで都市2を訪れる費用 | 都市1を出発して,<math>\{3,4\}</math>を巡回して都市4を訪れ,ついで都市2を訪れる費用 | ||
+ | |||
<math>Cost(\{3,4\},4)+L\{4,2\}</math> | <math>Cost(\{3,4\},4)+L\{4,2\}</math> | ||
+ | |||
のうち何れか小さい方: | のうち何れか小さい方: | ||
+ | |||
<math>min\{Cost(\{3,4\},3)+L\{3,2\},Cost(\{3,4\},4)+L\{4,2\}\}</math> | <math>min\{Cost(\{3,4\},3)+L\{3,2\},Cost(\{3,4\},4)+L\{4,2\}\}</math> | ||
+ | |||
で求められる。 | で求められる。 | ||
+ | |||
さらに, | さらに, | ||
+ | |||
<math>Cost(\{3,4\},3)</math>は路<math>(1,4,3)</math>の費用であるから<math>L\{1,4\}+L\{4,3\}=30+20=50</math> | <math>Cost(\{3,4\},3)</math>は路<math>(1,4,3)</math>の費用であるから<math>L\{1,4\}+L\{4,3\}=30+20=50</math> | ||
+ | |||
<math>Cost(\{3,4\},4)</math>は路<math>(1,3,4)</math>の費用であるから<math>L\{1,3\}+L\{3,4\}=20+20=40</math> | <math>Cost(\{3,4\},4)</math>は路<math>(1,3,4)</math>の費用であるから<math>L\{1,3\}+L\{3,4\}=20+20=40</math> | ||
+ | |||
である. | である. | ||
結局,最小の費用は以下の再帰的な計算により求めることができる。 | 結局,最小の費用は以下の再帰的な計算により求めることができる。 | ||
+ | |||
<math> | <math> | ||
- | min\{Cost(\{2,3,4\},2)+L\{2,1\},Cost(\{2,3,4\},3)+L\{3,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\},4)+L\{4,1\} \} | + | =min\{ 80+50,110+20 ,120+30 \} =130 \\ |
- | =min\{ 80+50,110+20 ,120+30 \} | + | (1,3,4,2,1)または (1,2,4,3,1) \\ |
- | =130 (1,3,4,2,1)または (1,2,4,3,1) | + | |
Cost(\{2,3,4\},2) | Cost(\{2,3,4\},2) | ||
=min\{Cost(\{3,4\},3)+L\{3,2\},Cost(\{3,4\},4)+L\{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) | + | =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\},3)=L\{1,4\}+L\{4,3\}=30+20=50 \\ |
- | Cost(\{3,4\},4)=L\{1,3\}+L\{3,4\}=20+20=40 | + | Cost(\{3,4\},4)=L\{1,3\}+L\{3,4\}=20+20=40 \\ |
Cost(\{2,3,4\},3) | Cost(\{2,3,4\},3) | ||
=min\{Cost(\{2,4\},2)+L\{2,3\},Cost(\{2,4\},4)+L\{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) | + | =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\},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,4\},4)=L\{1,2\}+L\{2,4\}=50+40=90 \\ |
Cost(\{2,3,4\},4) | Cost(\{2,3,4\},4) | ||
=min\{Cost(\{2,3\},2)+L\{2,4\},Cost(\{2,3\},3)+L\{3,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) | + | =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\},2)=L\{1,3\}+L\{3,2\}=20+60=80 \\ |
- | Cost(\{2,3\},3)=L\{1,2\}+L\{2,3\}=50+60=110 | + | Cost(\{2,3\},3)=L\{1,2\}+L\{2,3\}=50+60=110 \\ |
</math> | </math> | ||
- | しかしながら, | + | しかしながら,この方法は組織的ではあるが,「全件探索」(全ての可能な候補を全て当たる) |
であり,都市の数が10~20ぐらいまでが限界である. | であり,都市の数が10~20ぐらいまでが限界である. | ||
583 行: | 588 行: | ||
問題の難しさを表す場合によく出てくる「NP困難問題」の一つである. | 問題の難しさを表す場合によく出てくる「NP困難問題」の一つである. | ||
種々な方法が考案されている。「分岐限定法」もその一つである. | 種々な方法が考案されている。「分岐限定法」もその一つである. | ||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- | |||
- |
2020年11月27日 (金) 16:32 時点における最新版
目次[非表示] |
有向グラフ
有向グラフは,ここでは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のアルゴリズム (Wikipedia)
準備 K←ϕL←P O(j)←{0(j=1)∞(j≠1)
手順1 終了(K=P)
O(m)=min
手順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(1回目) K \ne Pなので終了ではない O(m)=min\{O(1),O(2),O(3),O(4),O(5),O(6)\} =O(1) =0
となり、m=1を選ぶ。
手順2(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の元ではない ~]
手順1(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を選ぶ。
手順2(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の元ではない ~]
手順1(3回目) 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を選ぶ。
手順2(3回目) 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の元ではない ~]
手順1(4回目) 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を選ぶ。
手順2(4回目) 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 ~]
手順1(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を選ぶ。
手順2(5回目) 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)となり何もしない ]
手順1(6回目) K=\{1,2,3,4,5\}なのでK \ne Pとなり終了ではない \\ O(6)=50なので O(m)=min\{O(6)\} =O(6) =50
となり、m=6を選ぶ。
手順2(6回目) K \leftarrow \{1,2,3,4,5,6\} \\ L \leftarrow \phi \\ [ 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\}も弧と呼ぶことにする。有向グラフのような始点,終点はない.
のように表すことができる。有向グラフと同様に枝のまたは弧の図をつなぎ合わせば,
グラフ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\}とし,夫々の弧に付けられている,ラベルはその弧を移動する 費用は表すものとしておく。
弧をつなぎ合わせて作られる路を移動する費用は,それを構成している弧の費用の和で 表します。上の図で路(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通り\times2番目の都市2通り\times3番目の都市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 \\
しかしながら,この方法は組織的ではあるが,「全件探索」(全ての可能な候補を全て当たる) であり,都市の数が10~20ぐらいまでが限界である.
分岐限定法
ここで扱っている,巡回セールスマン問題には,解法の「決定打」はない。 問題の難しさを表す場合によく出てくる「NP困難問題」の一つである. 種々な方法が考案されている。「分岐限定法」もその一つである.