第6話 ツリー構造
第6話 ツリー構造
親ノードには、N(N－1)／2本の線分（グラフ理論のエッジ）が生成される。つまり、N(N－1)／2個のツリーができることになる。親ノードが所有する情報は、親となる線分TLと完全グラフの集合PとLである（線分TLは除外する）。ここで一定の条件とは次のことである。
TLの直線の方程式をy＝ax+bとしたとき、線分TLと集合Lの要素の線分は次のいずれかになる。ここで集合Lの要素の線分の両端の点をP1、P2とする。y＝ax+bにP1、P2を代入する。（P1、P2がy<ax+bかy>ax+bの判定）
①P1とP2のいずれもが正の値の時
②P1とP2のいずれもが負の値の時
③P1とP2の値が正と負でP1とP2からなる線分と線分TLとの交点がTL上（内部）にある時
④P1とP2の値が正と負でP1とP2からなる線分と線分TLとの交点がTL上（内部）にない時
尚、P1とP2が0の値をとるときがあるが、ここでは説明が複雑になるだけなので考慮しないこととする。これはアルゴリズムであって厳密な理論ではないから例外的なケースの処理は如何様にでも処理できる。
上記の一定の条件（実は条件ではなく、単なる分枝の手法なのであるが他の命題への応用のため条件としている）から集合PとLは①～④の4本に分枝される。ところが、③は初期条件である“最短ルートには交差する線分は存在しない”に反するためツリーから除外されていく。④の交点は線分の外に存在するから初期条件には反しない。4本に分枝されるとしたが、実は①＋④と②＋④の２本に分枝されることになる。つまり、親ノードの集合は、２つに分割されることになる。分枝された２つの集合を集合LとRと呼ぶことにする。集合LもRも同じ構造を持つため、主として集合Lの構造だけ述べることにする。集合Pは完全に２つに分割されて点集合PL（PR）となるが、線分集合Lは集合LL（LR）に④の線分集合LCを加えたものとなる。つまり、線分集合Lは線分集合LCで重なり合う２つの線分集合に分割されることになる。尚、点集合PLから線分集合LLは一意に決定されるいわば可逆的に同じものである。
ここで線分集合LCの意味合いを述べたい。集合LLと集合LRは直接繋がることはできない。何故なら双方とも線分の両端が片側にのみ位置するからである。そこで線分集合LCを介して集合LLと集合LRは繋がれることになる。
このような構造を分割できなくなるまで繰り返しツリーを構築すれば、点集合Pと線分集合Lは分割されたことになる。
次に行う処理は、ツリーの底部から線分を繋ぎ合わせて最終的に複数の“交差する線分が存在しないルート”が生成される。この複数のルートから最短のものを選択すれば、巡回セールスマン問題の解となる。尚、最終的に残るルートの数はハミルトン閉路の性質からおおよそN／2本となる。また、ハミルトン閉路については詳しく調べなかったので、詳細は専門家に尋ねることをお勧めしたい。この解法の重要な部分はハミルトン閉路とは直接関係無いので容赦願いたい。
