骨格となるアルゴリズムの概要

まず、巡回セールスマン問題の対象要素は完全グラフと同値であるというわたしの認識が前提となります。

アルゴリズムの骨格は変形木構造によって構成されます。

木ルート

ノード数N＝エッジ数EN=N（N-1）／２＝O(N＾２)としたとき、エッジはEN数存在します。

そして、木ルートはEN数全てのエッジとなります。

子ノード

次の２つの子ノードが交互に木構造を構成します。

・任意の統一条件で分割された子ノード（２つ以上）
このとき、子ノードは共有情報を親ノードに持ちます。

・分割された子ノードから一意的に生成されるエッジの子ノード

判定

子ノードを派生させる段階で、一定の条件を満たさなければそのルートそのものが最短ルートあるいはハミルトン閉路（ハミルトン閉路が完全に理解できていないので不確かです）の候補から除外されます。

また、子ノードに分割する統一条件により計算量が大きく異なります。

ALV木

２分木の例を次のweblio辞書から参照してもらえばわかるように

http://www.weblio.jp/content/ALV木

木構造の宿命（特性）として、最悪の木構造から最適な木構造までを構成します。

現在わたしが所有するアルゴリズムは、全ての木ルート（エッジ）を対象としたとき、必然的にこの最悪の木構造から最適な木構造を構成してしまいます。

課題

ALV木に代わるアルゴリズムを構築し、期待される最小の計算量を求めたいと思います。