無向グラフ

: 整数計画法 : 最短経路問題 : D.P.(ダイナミック・プログラミング)と最短路

無向グラフ

最短路問題ではラベル付き有向グラフを扱いましたが,ここでは,弧で結ばれている節点間は, 双方向に行き来できるものとします。従って,図示した場合も始点,終点といった「向き」はありません。このようなグラフ

は無向グラフと呼ばれます。これは

$\begin{eqnarray*} &&(1)節点の集合P\\ &&(2)Pの点の非順序対\{a,b\}( a,bはPの点)の集合V \end{eqnarray*}$

からなります。

$\{a,b\}=\{b,a\}$ です。

この非順序対{a,b}も弧と呼ぶことにします。有向グラフのような始点,終点はありません。

(図5.7)

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

(図5.8)

$\begin{eqnarray*} &&P=\{a,b,c,d,e,f\}\\ &&V=\{\{a,b\},\{a,c\},\{b,d\},\{b,e\},\{c,e\},\{d,f\},\{e,f\}\} \end{eqnarray*}$

ラベル
有向グラフと全く同様に無向グラフ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\}$ がの元,すなわち弧であるものを路と呼ぶことにします。
上の図では, などが路です。
巡回セールスマン問題
さて,簡単にするため,集合が個の節点からなっているとして
$P=\{1,2,\cdots,n\}$ とし,夫々の弧に付けられている,ラベルはその弧を移動する費用は表すものとしておきます。
下の図では,節点の番号と区別できるよう(）付の数字で表しておきます。

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

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

(図5)の例では,路とが解で,費用が130です。
可能な路を全てを調べても,１番目の都市3通り $\times$ 2番目の都市2通り $\times$ ３番目の都市1通り=3!通りで順序を逆に回っても同じですから2で割って,結局3!/2通りです。しかし,都市の数が増えると非常に難しくなります。
D.P.の適用
有グラフ最短路問題と同様に最適性の原理を使って組織的に調べることができます。
例えば,都市を出発して, $\{2,3,4\}$ を巡回して, 最後に都市を訪れるまでの最小費用を $Cost(\{2,3,4\},2)$ で表すと,
その最小になる路を通ってさらに都市に戻ってくるまでの費用は　　

$\begin{displaymath}Cost(\{2,3,4\},2)+L\{2,1\}\end{displaymath}$

です。全く同様に,費用最少で, $\{2,3,4\}$ を巡回後,都市3を訪れ,都市に戻る費用は　　

$\begin{displaymath}Cost(\{2,3,4\},3)+L\{3,1\}\end{displaymath}$

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

$\begin{displaymath}Cost(\{2,3,4\},4)+L\{4,1\}\end{displaymath}$

です。
結局,最小の費用は

$\begin{displaymath}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\}\}\end{displaymath}$

であり,その最少費用を実現する路が求めるものです。
有グラフの場合と同様に $Cost(\{2,3,4\},2)$ も再帰的に, 　都市1を出発して, $\{3,4\}$ を巡回して,最後に都市2を訪れるまでの最小費用ですから
　都市1を出発して, $\{3,4\}$ を巡回して都市3を訪れ,ついで都市2を訪れる費用　

$\begin{displaymath}Cost(\{3,4\},3)+L\{3,2\}\end{displaymath}$

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

$\begin{displaymath}Cost(\{3,4\},4)+L\{4,2\}\end{displaymath}$

のうち何れか小さい方：

$\begin{displaymath}min\{Cost(\{3,4\},3)+L\{3,2\},Cost(\{3,4\},4)+L\{4,2\}\}\end{displaymath}$

で求められます。さらに, $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$
です。
結局,最小の費用は以下の再帰的な計算により求めることができます。

$\begin{eqnarray*} &&min\{Cost(\{2,3,4\},2)+L\{2,1\},Cost(\{2,3,4\},3)+L\{3,1\} ... ...{3,2\}=20+60=80\\ &&Cost(\{2,3\},3)=L\{1,2\}+L\{2,3\}=50+60=110 \end{eqnarray*}$

しかしながら,この方法は組織的ではありますが,「全件探索」(全ての可能な候補を全て当たる) であり,都市の数が１0～20ぐらいまでが限界です。
分岐限定法
　ここで扱っている,巡回セールスマン問題には,解法の「決定打」はありません。問題の難しさを表す場合によく出てくる「NP困難問題」の一つです。種々な方法が考案されています。「分岐限定法」もその一つです。
かなり作為的ですが,以下の例を考えます。

(図5.11)
都市1を出発し,各都市を1回ずつ訪れ,都市1に戻ってくる路を全て,逆周りも含めて,列挙すれば,

$\begin{displaymath} (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) \end{displaymath}$

です。これらの路は1番目,2番目,3番目に訪れる都市によって分類できます。例えば,1番目に訪れる都市に注目して
(Ⅰ)1番目の都市が2のもの

$\begin{displaymath}(1,2,3,4,1),(1,2,4,3,1)\end{displaymath}$

(Ⅱ)1番目の都市が3のもの

$\begin{displaymath}(1,3,2,4,1),(1,3,4,2,1)\end{displaymath}$

（Ⅲ）1番目の都市が4のもの

$\begin{displaymath}　(1,4,2,3,1),(1,4,3,2,1)\end{displaymath}$

です。Ⅰ,Ⅱ,Ⅲの中でそれぞれ,最少費用の路を探す問題は部分問題と呼ばれます。さらにⅠ,Ⅱ,Ⅲの分類を2番目,3番目によって,細かく分類ができます。解の候補の「分岐」がでてくるわけです。

ここで,解の候補として路のを選んだとします。この路の費用は130です。部分問題Ⅲ,すなわち,Ⅲの分類の中で費用最少を調べ見ると：　路（弧)だけで,既に費用が130であり,費用がマイナスの弧はないのですから, このⅢの分類のものの最少費用は130より大です。従って,これ以上細かく調べる必要はありません。
すると,解は,路のを含む,（Ⅱ）か（Ⅰ）から探せばよい事になります。
このようにして,探すべき解の候補の「枝」のうち,無駄なものを削除する事ができます。

さらに,路も費用が130ですから,これらの後の節点がなんであろうと,費用は 130より大きくなります。この例では,以後の分岐はありませんので,これが判っても効用はありませんが,もしさらに分岐があるなら,無駄な「枝」を削除できることになります。

この様にして,結局,

$\begin{displaymath}　(1,3,4,2,1),　(1,2,4,3,1) \end{displaymath}$

にたどりつきます。
　無論,問題のよって,また,部分問題にの作製（分類）の仕方によって,最悪,全ての路を調べる事になる場合もあります。以上のような解法を一般的に表すと,
最小化問題が与えられたとして：

(1)

　から,部分問題の集合 $L=\{P_0,P_1,P_2,\cdots,P_n\}$ を作り,
　　　初期解を適当に選択してその値を求める。
以下の手続きをの元の全てについて行う

(2)

　最小問題の解の下限値を求め,　
　　　　　　なら　 $L \leftarrow L \setminus \{P_i\}$

(3)

　最小問題の解を求め　
　　　　　　　なら　 $C_0 \leftarrow min P_i$ 　とする

図5.10の問題について,「分岐限定法」を適用すると例えば以下のようになります。これは、本大学院の社会人学生久保さんにやっていただいたものです。上の例よりスマートな解法です。

都市1を出発し,各都市を1回ずつ訪れ,都市1に戻ってくる路を全て,逆周りも含めて,列挙すると,

$\begin{displaymath} (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) \end{displaymath}$

です．これらの路は費用最小の $\{1,3\},\{3,4\}$ の両方を通るものと，通らないものに分類できます．

(Ⅰ) $\{1,3\},\{3,4\}$ の両方を通るもの
　

$\begin{displaymath}(1,2,4,3,1),(1,3,4,2,1)\end{displaymath}$

(Ⅱ){1,3},{3,4}の両方は通らないもの
　

$\begin{displaymath}(1,2,3,4,1),(1,3,2,4,1),(1,4,2,3,1),(1,4,3,2,1)\end{displaymath}$

です．
ここで,解の候補として(Ⅰ)から路を選んだとします．この路の費用は130です．

部分問題(Ⅱ)で費用を調べて見ると,費用20の路が1つしか通れないことから，各路の費用はで，この中から4つを選ぶことから下限値は140となる．
140>130なので，Ⅱは削除できます．

残った（Ⅰ）から探せばよい事になりますが，路(1,3,4,2,1)の費用も130となり，

$\begin{displaymath}(1,3,4,2,1),(1,2,4,3,1)\end{displaymath}$

にたどりつきます．

図5.11の問題について,「D.P.」を適用すると：
これは、本大学院の社会人学生「たなかさん」にやっていただいたものです。

$\begin{eqnarray*} &&min\{Cost(\{2,3,4\},2)+L\{2,1\},Cost(\{2,3,4\},3)+L\{3,1\} ... ...3,2\}=20+80=100\\ &&Cost(\{2,3\},3)=L\{1,2\}+L\{2,3\}=50+80=130 \end{eqnarray*}$

: 整数計画法 : 最短経路問題 : D.P.(ダイナミック・プログラミング)と最短路

Yasunari SHIDAMA