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

凸型図形

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

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

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

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

内包されるノードの次数

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

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

部分の凸型図形

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

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

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