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

凸型図形

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

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

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

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

内包されるノードの次数

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

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

部分の凸型図形

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

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

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

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

前置き

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

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

さて、概要を再び簡単に説明すると、
・変形木構造である。
・木構造のルートは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という職によって生活を支えていました。

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

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

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

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

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

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

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

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