巡回セールスマン問題におけるノードの座標配置と計算量算出の難易度

凸型図形

ノードの座標配置が凸型図形の時、最短距離は一意に決定されます。

その証明として以下の参照先を根拠に

TSPの最短距離のパスのエッジは交差しない

求めようとする最短距離のパスに凸型図形の対角線エッジが含まれるると必ずその対角線エッジは他の対角線エッジと交差するため対角線は最短距離のパスに含まれません。

内包されるノードの次数

与えられたノードの集合から凸型図形を抽出したとき、残ったノードはその凸型図形に内包されるノードとなります。
このとき、凸型図形の対角線と内包されるノードから凸型図形の全てのノードを結んだエッジとの交点は内包されるノードの次数により増減します。
次数が高いほど、交点は増え、次数が低いと交点は減ります。
そして、次数が高いほど巡回セールスマン問題の解を求めるときの難易度は高くなります。

ところが、この次数を求める手段が現段階では確立できていません。
おそらく、この難易度が決定できるということが、解法に光明をあてると考えています。

部分の凸型図形

わたしのアルゴリズムで、木構造を構築するとき、子ノードに含まれるエッジ集合が凸型図形であるとき、その子ノードは最短距離の部分（一部）である可能性があり、その子ノードをさらに分解（子ノードの生成）していくことは無意味となります。

つまり、その子ノード以下の計算は凸型図形となった時点で打ち切りとなります。
これにより、ALV木 に近づくアルゴリズムが用意できます。

しかし、そのためには、ノードの集合が凸型図形であるか否かの判定アルゴリズムの高速化が必要になります。
この発想によるアプローチが有効か否かは今後の精進次第となります。

木構造破棄のロジックとアルゴリズム

前置き

メインアルゴリズムは変形木構造となります。
木構造となるので、木のルートから末端リーフ（木の底）への構造は偏りを持ちます。
そのため、木構造の構築の過程でその構築を破棄することが、計算量の減少に有効となります。

メインアルゴリズムの変形木構造

変形木構造の特長として次の２つが挙げられます。

・ノード数Nのとき、エッジ数EN=N(Nー１）／となり、木ルート数はENと自分自身を除くENとの組み合わせになります。
即ち、木ルート数TN＝EN（EN-1)＝O（N＾４）となります。

巡回セールスマン問題の計算量はN！ですから、O（N＾４）は、N！の後方から４つの数の掛け算分だけになります。
例えば、N=１０，０００のとき、１０，０００*９，９９９*９，９９８*９，９９７≒O（N＾４）となります。

・ルートの次の分枝は変形２進木となり、その次の分枝数は親ノードに含まれるエッジ数となります。
そして、この２つの構造を分枝できなくなるまで繰り返します。

従って、このままではメインアルゴリズムの計算量は最低でもO（N＾４）*木構造の構築計算量となります。
そのため、木構造の構築を中途で破棄したいのです。

破棄のロジック

破棄のロジックはいくつか考えられます。
例えば、変形２進木を構築しするとき、
・２つの分枝が結合できないとき（全体のパスを構成できない）
・２つの分枝の結合で閉じることができないとき（閉路が構成できない）
などですが、これらは木構造のルートそのものが無効であることを意味します。

・分枝の１方が凸図形またはそれに準ずるとき（準ずるときがこれからの課題となります）
その分枝は全体の最短経路パスの一部となる可能性を持つので有効としてそれ以降の分枝の構築は打ち切られます。

課題

上述の今後の課題とした準ずるときの考察の方向性を挙げておきたいと思います。

凸図形であるか否かの判定方法として、角度や内積／外積を用いる方法がありますが、これより計算量の少ないアルゴリズムを考察したいと思います。

また、ノード集合から凸図形（多角形）を構成するアルゴリズムも必要になります。

内外判定も関係してくるものと思います。
現在も使われている内外判定のアルゴリズムは少なくとも３０年前に考え出されたもので、わたしは３０年前に文献か他者よりこの手法を得ました。

改良の余地が存在するのか否かわかりませんが、上述のアルゴリズムの改善や向上を行いと思っています。

巡回セールスマン問題の計算量の概算

前置き

前記事まででわたしの持つ解法のアルゴリズムの概要を述べました。詳細については、実証の終了後投稿したいと思います。

そもそも、わたしの持つ解法のアルゴリズムの有益性（計算量または速度）がどの程度であるか不明であり、検証をどなたかにお願いすることも難しいようなので実証により有益性（または無益性）を確かめたいと思っています。

さて、概要を再び簡単に説明すると、
・変形木構造である。
・木構造のルートはN（ノード数）の４乗である。
・全てのルートとその配下の木構造によりN！パスの全体集合を網羅している（はずである）。

計算量の概算

前置きから計算量の概算はNの４乗×それぞれの木構造の計算量となります。
前記事までそれぞれの木構造の計算量を減らしたいと思いいろいろ考えていましたが、それは線形の傾きを小さくするアルゴリズムに近いだけなのではないかと思い始め、再考に迫られています。

もちろん、ALV木の代替えアルゴリズムは構築しなければなりませんが、考察の優先度が低くなったということです。

アルゴリズムの実装

そこで、アルゴリズムの骨格だけを用いてホームページ上にプログラムを実装したいと思います。
それによって、アルゴリズムの有益性が掴めるかもしれませんし、必要なアルゴリズムも見つかるかもしれません。

ファーストトライとなるので目標の速度や計算量はありませんが、何かが見えることを期待しています。
そして、β版を７月末日に予定しています。

難易度

座標配置による巡回セールスマン問題の難易度をあわせて調べていきたいと思います。
座標配置が凸図形を形成するのであれば、Nの４乗の木ルート配下の計算はほとんど不要となるはずなので、その検証も行いたいと思います。

TSPの最短距離のパスのエッジは交差しない

　

　巡回セールスマン問題において、出発点から全ての都市（ノード）を巡って出発点に戻ったとき、そのパスを構成するいかなる道（エッジ）も交差しない。

　どのような問題でもそうなのかもしれませんが、巡回セールマン問題の解法アルゴリズムにおいても小さな論理（定理）の積み上げ（組み合わせ）が重要になってきます。

　場合によっては、条件も必要になりますが、条件によってはその解法（主張）を一般化できないものと考えます。

　さて、わたしは学会などで定説となっている定理または巡回セールスマン問題についての特性などを知りません。

　従って、ここで述べる内容（主張）は、全て検証されていないはずだと思いますし、重複しているかもしれません。

　このことが、市井（民間）の数学者の悲しいところであります。

交差しない道（エッジ）

　この定理は巡回セールマン問題の解法のための絶対条件ではありませんが、この定理を条件としてアルゴリズムを構築するとN！個存在するパスの多くを計算から除外することができます。

　エッジは線分なので始点と終点を持つ有限直線となります。

また、解法の初期の段階では線分は向きを持たないので２つの端点は始点と終点の区別を持ちません。

　著者の今回の主張は、ユークリッド２次元空間が条件となっていますが、必ずしもユークリッド空間である必要はなく、拡張する場合は直線ではなく測地線を用いればよいのではないかと考えています。

　ただし、３次元以上の空間に対してはいくつかの考慮が必要になるかもしれません。

　さて、「交差する」とは、２つの線分が有限線分の内部で交差するということです。有限線分の延長上で交差する線分は対象となりません。

証明

　この記事の最上部に図ー１を用意しました。

線分AとCを結ぶパスAーCや線分BとDを結ぶパスBーDがいかなるノードを含むパスであってもこの証明に影響を与えません。

　問題となるのは、A～D点の結線の組み合わせだけとなります。

　この４点の結線の組み合わせは次の３通りだけとなります。

①　A-BとC-D

②　A-CとB-D

③　A-DとB-C

　ここで、②の組み合わせは２つのパスに分解されてしまいますので除外したいと思います。

つまり、①と③の距離のどちらが短いかということが問題となります。

　この証明は、三角形の性質を用いれば簡単なので省略したいと思います。

結論として道（エッジ）は交差しないということです。

　尚、球面上の三角形でもこの性質は受け継がれます。

市井の数学愛好家

　わたしは、大学などで学んだことはありません。

ましてやそういう類の研究所には所属しておりません。

そして、わたしには先生と呼べる存在はありませんでした。

　よって、論文などは１つも書いたことがありませんし、わからないことがあっても教えてくれる人も存在しません。

ネットでQ＆Aなどのサイトを利用したこともありましたが、納得できるクールな答えは返ってきませんでした。

　ただ小学生のころより、叔父や叔母が残した中学や高校の教科書がわたしの先生と呼べる存在でした。

　巡回セールマン問題に出会ったのは、３０歳台前半でしたが、それに類する問題への取り組みは２４歳のころに始まっています。

　その問題は、自作のCADを作りたいという願いから発したもので、「数百万本の線分データベースから画面に表示する線分を選び出す」という問題でした。

　点については３年くらい経た後に高速アリゴリズムを見つけ（現代では常識の範疇だと思います）たのですが、線分については未だに未解決です。

　いつのころからか（３０歳台前半なのは確かですが）、その問題は巡回セールマン問題と類似していることに気づき、もっぱら巡回セールマン問題を解くことが主題となっていったのです。

　そして、それがわたしのライフワークとなりました。

しかし、そのライフワークでは１円の収入にもならず、SEという職によって生活を支えていました。

　解けたと思ったのは、今から７年ほど前です。

そのときは、うれしくもあったのですが、ライフワークを失ったことにより虚無感にも襲われました。

当時、闘病のさなかであったこともあり、集中力も尽き、思考能力も低下する一方でした。

　現在も病持ちですが、回復傾向にあり集中力が戻ってきました。後は体力をつけたいと思っています。

何かをなすには、技術力と集中力＋体力が両輪であるというのが持論です。

　さて、最近７年ほど前に解けたと思ったのは、全体の数割でしかなかったことに気づき、基礎となる論理を積み重ねて行きたいと思っています。

　解法の部分々々は単純な論理ですが、解法の全体はその部分の特定の組み合わせによるものと確信しています。

　尚、わたしは２０１６年８月で５５歳になります。