§４．巡回セールスマン問題

---

　郵便配達問題によく似た(本質的には異なる)問題で、現在もうまい方法が見いだされず、研究がすすめられている問題に、巡回セ−ルスマン問題というのがある。

　もちろんこれは巡回セ−ルスマン問題の解法であるが、実はこの解法には大きな問題点がある。それは、ここでは巡る都市の個数が東京を含め、たった５都市であるが、１０都市になれば

　　９×８×７×６×５×４×３×２×１÷２＝１８１４４０ （通り）

1000都市になれば、１０2567通りという数になり、全コ−スを上の総当たり法で比較し解決しようとすると、現在かなり高性能のス−パ−コンピュ−タを宇宙の年齢といわれている150億年間フルに動かしても計算できないそうである。
　真の解をすばやく求めるうまい方法は現在も発見されていない。しかし、近似解を求める方法がいくつか発見されている。

　近似解の説明に入る前に、図18に示されている各都市間の航空運賃を下の表19のように整理してみることにする。

　パリ、ニュ−ヨ−ク間の運賃は図18より、７万円 であるから、表19では赤字７ であらわす。また、同じ都市 間の運賃を表す部分には０を入れる。
　さらに、東京＝v1,シンガポ−ル＝v2,パリ＝v3,ロンドン＝v4, ニュ−ヨ−ク＝v5 で表し、表19をさらに簡単に図20のような行列であらわすことにする。例えば、図20の行列では v2−v4 間(ｼﾝｶﾞﾎﾟ-ﾙ−ﾛﾝﾄﾞﾝ間)の運賃を表している。ここでは、v2→v4 の運賃と v4→v2の運賃は同一であるから２行４列の数と４行２列の数は同一になる。

（近似解法）

　各都市間の運賃を距離に置き換えて考えても同じことなので、ここでは行列の数字を各都市間の距離と見なし、最短距離で５都市を回るコ−ス捜しの問題として考えてみることにする。
　まず、５点 v1,v2,v3,v4,v5より１点を任意に選ぶ。

�@　v1を選んだ場合
　次にv1から最も近い点を選ぶ。図20の行列の第１行を見ると、２列の数字が最も小さいので、v2を選ぶ。そして、今、
　　　　　　　　　　v1−v2−v1
というコ−スを考える。
　次に、このコ−ス上の点から最も近い、コ−ス上にない点を１つ選ぶ。行　列より、v1に最も近い、コ−ス上にない点はv5であり、距離は８である。また、v2に最も近い、コ−ス上にない点はv3であり、距離は９である。したがっ　て、選ぶ点はv5である。そこで、v1の前にv5を置き、
　　　　　　　　　　v1−v2−v5−v1
というコ−スを考える。
　さらに、今と同様に、このコ−ス上の点から最も近い、コ−ス上にない点を選ぶ。選ぶ点は、行列よりv4となり、v4はコ−ス上の点v5に最も近い点であるから、v5の前に置き、
　　　　　　　　　　v1−v2−v4−v5−v1
という新コ−スを考える。
　残るはv3のみであり、v3はコ−ス上の点v4に最も近いので、v4の前にv3を置き、求めるコ−スは、
　　　　　　　　　　v1−v2−v3−v4−v5−v1
となる。

�A　v5を選んだ場合
　上と同様の方法をとると、v5に最も近い点はv4であるから、
　　　　　　　　　　v5−v4−v5
というコ−スを考える。
　このコ−ス上の点から最も近い、コ−ス上にない点はv3であり、コ−ス上の点v4に最も近い点なので、v4の前にv3を置き、
　　　　　　　　　　v5−v3−v4−v5
というコ−スを考える。
　以下同様に、つぎのようにコ−スを求めていく。
　　　　　　　　　　v5−v3−v4−v1−v5
　　　　　　　　　　v5−v3−v4−v2−v1−v5

　最初にv1を選んだ場合求まるコ−スは
　　　　　　　　　　v1−v2−v3−v4−v5−v1で、
総距離は
　　　　　　　　　　５＋９＋３＋６＋８＝31
である。

　最初にv5を選んだ場合求まるコ−スは
　　　　　　　　　　v5−v3−v4−v2−v1−v5で、
総距離は
　　　　　　　　　　７＋３＋10＋５＋８＝33
である。

このように、最初に選ぶ点の違いによって求まるコ−スが変わり、当然、最短コ−スがもとまるわけではない。しかし、この方法で求めたコ−スは最短のコ−スの２倍の長さよりも常に短いことがわかっており、最初の６通りの点の選び方に対してそれぞれ求まったコ−スの内、最短コ−スをとれば、真の最短コ−スにより近いコ−スを求めることができる。
　この場合、真の最短コ−スは、
　　　　　　　　　　v1−v2−v3−v4−v5−v1
であり、総距離は31である。したがって、この方法で求めた解が、たまたま真の解に一致した。

　現在、この方法以外にもっと精度の高い近似法がいくつか発見されている。　1993年９月には、日本IBM東京基礎研究所の岩野和夫、味園真司両氏が「グランド・ツア−(ＧＴ)法」を独自に開発している。これにより、ＩＣ回路のプリント基盤に穴をあけるためのドリルの移動時間が平均70％短縮され、全行程所要時間も15％短縮された。これは大きな経費節減、生産量の拡大へとつながる。

　巡回セ−ルスマン問題は、完全グラフの各線に数が対応し、グラフの全ての点をちょうど１回ずつ通り、元に戻るコ−スの、各線上に対応する数の和が最小になるコ−スを考える問題である。
　グラフ理論では、グラフの全ての点をちょうど１回ずつ通り、元に戻るコ−スをハミルトン閉路と呼んでいる。完全グラフにはハミルトン閉路は必ず存在するが、完全グラフでない一般のグラフには、存在する場合と存在しない場合がある。ハミルトン閉路が存在するグラフをハミルトングラフと呼ぶ。
　定理３・１で述べたように、グラフにオイラ−回路が存在するかどうか判定する方法は比較的簡単であるが、実は、グラフにハミルトン閉路が存在するかどうかをきちんと判定する方法は、未だ発見されていない未解決問題なのである。

中高校生のためのグラフ理論　Top Menu　へ