巡回セールスマン問題と凸図形の関係
１． 初めに
筆者の巡回セールスマン問題の解法はアルゴリズムによるものです。従って数学的にＮＰ問題などの解法を求めている方には参考にならないかもしれません。
また、Ｎ！を多項式に展開することを目的としているのではなく、いかに最小の計算量で求めるかを目的としています。
なお、以下の記述はユークリッドの２次元空間を前提としています。
２． 最短パスは交差する線分を含まない
図１
図２
２．１ 図1の説明
図１においてＰ１とＰ２は、ノードＡＢＣＤ以外のノードを含むパスとします。
また図1で線分ＡＢと線分ＣＤは交差しています。
注意点は交差する交点が線分ＡＢと線分ＣＤの内部に存在することであって、例えば線分ＡＢを無限線に延長したとき、線分ＣＤと交差した交点のケースは当てはまりません。このケースは線分の外部で交差しているとみなします。
２．２ より最短に
図２を使って線分ＡＢの距離＋線分ＣＤの距離が、線分ＡＤの距離＋線分ＢＣより長いことを証明したいと思います。
ＡＤ＜ＡＥ＋ＤＥ・・・①
ＢＣ＜ＣＥ＋ＢＥ・・・②
①式と②式を足すと
ＡＤ＋ＢＣ＜ＡＥ＋ＢＥ＋ＣＥ＋ＤＥ・・・③
③式の右辺を整理すると
ＡＤ＋ＢＣ＜ＡＢ＋ＣＤとなり、証明が終了しました。
２．３ パス全体をみると
Ｐ１＋Ｐ２＋ＡＤ＋ＢＣ＜Ｐ１＋Ｐ２＋ＡＢ＋ＣＤを整理すると
ＡＤ＋ＢＣ＜ＡＢ＋ＣＤとなりパス全体においても交差する線分を最短につなぎかえられることがわかります。
３． 凸図形を構成するノード集合の最短パス
「凸図形を構成するノード集合は巡回セールスマン問題において外周が最短距離となる」（外周とは凸図形を描画する線分そのものを意味します。）
３．１ 証明
① 凸図形の外周以外の任意の線分（線分ＡＢ）を１つ選択します。
② すべてのノードを線分ＡＢの左右（あるいは上下）に分類してノード集合Ｃとノード集合Ｄを作ります。このとき、ノード集合Ｃ、Ｄは絶対に空集合とならないことを確認してみてください。
③ 巡回セールスマン問題の解は全てのノードを1回だけ含むことが条件となりますから、
線分ＡＢのノードＡ、Ｂとノード集合Ｃ、Ｄの全てのノードを含む必要があります。となるとノード集合Ｃのいずれかのノードとノード集合Ｄのいずれかのノードをつなぐ機会（線分）が最低1回は必要となります。この線分は必ず線分ＡＢと交差しますので確認してみてください。これは「２」で証明した「最短パスは交差する線分を含まない」という条件に反します。故に、 凸図形の外周以外の任意の線分は最短パスには含まれない。従って、残る凸図形の外周だけが最短パスを構成することになります。
４ 最後に
途中、証明を省いた部分がありますが、そう難しくないものなので興味のある方は証明してみてください。この記事は厳密な論文を書くことを目的としていないので筆者の怠慢をお許しください。
