第２８章 解法（１）
第２８章 解法（１）
第１話 分解
僕のＴＳＰの解法を記述したいと思います。
完全グラフＧ（Ｖ，Ｅ)が、あるとします。
この時、集合Ｖの頂点数をＮとします。
集合Ｅの辺数は、Ｎ（Ｎ－１）／２となります。
単純パス数は、Ｏ（Ｎ！）となります。
ここで、集合Ｅの全ての元は、有限線分です。
必ず、始点と終点を持ちます。
――――――――――――――――――――――――――――――――――――――――
「絶対条件＝（ＡＢＳ）」
グラフＧの単純パスが最短距離をとる時、その単純パス内のＥの、
どの２つの元をとっても、有限線分の内側で交差しない。
――――――――――――――――――――――――――――――――――――――――
この事は、既に証明されていると思います。
証明する事は、簡単に出来ます。
なので、ここでは省略します。
――――――――――――――――――――――――――――――――――――――――
「定義」
点集合Ｖを｛ｎ：ｎ１，ｎ２，．．．ｎｎ｝とする。
辺集合Ｅを｛ｅ：ｅ１，ｅ２，．．．ｅｎ｝とする。
グラフＧは無効グラフである。
ｎは、座標を持つ。
（すると、ｅは、距離を持つ。）
――――――――――――――――――――――――――――――――――――――――
ステップ－１
ステップ－１－１
集合Ｅから任意の元ｅ１を選びます。
ＴＳＰは、完全グラフなので、集合Ｅのどの元を選んでも、問題ありません。
そして、元ｅ１を木構造のＲｏｏtとします。
ｅ１は、始点と終点からＹ＝ａＸ＋ｂで表現出来ます。
この時、ｅ１と集合Ｅの全ての元（ｅ）との関係は次のいずれかです。
① 不等式 Ｙ＜ａＸ＋ｂに（ｅ）の始点と終点は含まれる。…集合Ｌ
② 不等式 Ｙ＞ａＸ＋ｂに（ｅ）の始点と終点は含まれる。…集合Ｒ
③ 等式 Ｙ＝ａＸ＋ｂとなる（ｅ）は存在しない。
（何故なら、その（ｅ）は点となるからである）
不等式 Ｙ＜ａＸ＋ｂ に始点か終点を持ち、
不等式 Ｙ＞ａＸ＋ｂ のその反対側の端点を持つ。
この時、ｅ１と（ｅ）は交点を持つ。
その時、
④ 交点がｅ１の線分の内側にある。…集合Ｘ
⑤ 交点がｅ１の線分の外側にある。…集合Ｃ
ここで、集合Ｅ＝Ｌ＋Ｒ＋Ｘ＋Ｃとなります。
「＋」表記を用いたのは、集合Ｌ、Ｒ、Ｘ、Ｃが交わる事がないからです。
ここで、（ＡＢＳ）より集合Ｘは、単純パス候補から外れます。
ステップ－１－２
① 集合Ｌの始点と終点から点を抽出します。…集合ＰＬ
② 集合Ｒの始点と終点から点を抽出します。…集合ＰＲ
③ 集合ＣからＹ＜ａＸ＋ｂに属する点を集合ＰＬ に加えます。…集合ＰＬＣ
④ 集合ＣからＹ＞ａＸ＋ｂに属する点を集合ＰＲ に加えます。…集合ＰＲＣ
くどいかもしれませんが、③の点と④の点は、集合Ｃの始終点の対になります。
これは、次と等価です。
点集合Ｖの元（ｎ）を座標（ｎｘ，ｎｙ）とした時、
① 不等式 ｎｙ＜＝ａｎｘ＋ｂ…集合ＰＬＣ
② 不等式 ｎｙ＞＝ａｎｘ＋ｂ…集合ＰＲＣ
③ ｎｙ＝ａｎｘ＋ｂを始点か終点に持つ（ｅ）は集合Ｃに属する。
ステップ－１－３
ここで、Ｒｏｏtが持つ情報は、集合Ｃの情報と、
ｅ１の情報だけです。
ここで、ｅ１の情報を集合ＰＥ＝｛ｐ１、ｐ２｝とします。
ステップ－１－４
これらの集合の特徴は、集合ＰＬと集合ＰＲは、完全に独立している事です。
集合ＰＬと集合ＰＲがパスを構成するためには、必ず集合Ｃを介さなければなりません。
ステップ－１－計算量
計算を簡単にするために、集合Ｘを空集合とします。
また、集合ＰＬＣとＰＲＣは均一に分割されるものとして計算します。
ここで、不均一性に触れると本論から外れて、記述が複雑になるためです。
不均一性の問題は、後回しとしたいと思います。
Ｒｏｏtが持っていた集合Ｖの頂点数Ｎは、
集合ＰＬＣと集合ＰＲＣに分割される事により、それぞれＮ／２となります。
集合ＰＬＣと集合ＰＲＣは、深さ＝１(奇数深さ）の子ノードとなります。
奇数深さには、意味があります。
それは、ステップ２で記述します。
尚、集合Ｃは「結合」の時に必要になります。
現在は「分解」の段階です。
ステップ－２
集合ＰＬＣについて考えます。（集合ＰＲＣも考え方はＰＬＣと同じです）
集合ＰＬＣは、深さ１のノードです。
奇数ノードは、その親ノードとＣ集合情報を共有します。
次の子ノードは、集合ＰＬＣの元全てになります。（Ｎ／２個）
深さ＝２（偶数深さ）となります。
ここで、集合ＰＥ＝｛ｐ１、ｐ２｝は、｛ｐ１、ｐ２、ｐｎ｝となります。
そして、ステップ－１－１に戻ります。
この時、ｅ１＝｛ｐ２、ｐｎ｝として考えます。
確認のためです。
集合ＰＥの元は、子ノードには含まれません。
ステップ－３
Ｌｅａｆは、奇数深さの点数が１以下になった時の直前のノードです。
計算量
集合ＬとＲは均一に分割されるものとして計算します。
集合Ｘを空集合として計算します。
上述の両方ともに絶対ありえません。
しかしながら、不均一性の計算量を計算出来るという事は、別な解法の存在を、
意味します。
残念ながら、僕には考え付きませんでした。
なので、上述で計算量を計算したいと思います。
と、思いましたが厳密に計算出来ません。
ただ、木の深さが２×ｌｏｇＮ（低は２）となります。
今、思いついたのですが、集合Ｃが空集合の時、全ての単純パスが、
存在しない事を意味するのではないか？
直感的には、未だ受け入れられていません。
機会を見つけて確認して見ます。
確認できれば「一筆書き」の可否の判定に利用できるかもしれません。
但し、そのためには、Ｒｏｏｔを任意とする事は出来ないと思います。
第２話 章の最後に
数年前は、この事を表現するために１０倍以上の記述をした記憶があります。
今、思うのは「大した事じゃなかったのかも？」と、言う事です。
「ほっ」と、一安心です。
また、集合の記述方法も多くは必要ありませんでした。
数年前には、必須と思っていました。
グラフ理論を少し学んだ事が、この結果（簡略な表現）を生んだのかもしれません。
本当に「ほっ」と、一安心です。
次章は「結合」について、考えたいと思います。
