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

前置き

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

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

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

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

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

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

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

破棄のロジック

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

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

課題

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

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

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

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

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