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

前置き

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

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

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

計算量の概算

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

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

アルゴリズムの実装

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

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

難易度

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