第２９章 解法（２）
第２９章 解法（２）
第１話 結合
前章で「分解」した木構造を単純パスへと組み立てます。
１つだけ、確認していない事があります。
それは「奇数深さのノードのＣ集合＝空集合の時、兄弟ノードは存在しない」と、
考えています。
この確認は、取り敢えず、後回しにします。
完全グラフの時、上述の事は、成立すると確信しているからです。
これが、崩れると全てが、崩壊するかもしれません。
この文章の記述中に考えましたが、上述が成立する条件は、
「完全グラフの場合、Ｖの要素(点）をどのように辿っても一筆書き出来る」
しかも「単純パスは、交差しない」も条件に加わります。
やはり、後回しです。
Leafは、集合ＰＥ＝｛ｐ１、ｐ２．．．．ｐｎ｝の情報を
単純パスの一部として１本か、２本持っています。
そして、Leafの深さは、偶数です。
深さを上方に１つ上げます。（深さの数値は１つ減ります）
そこは、深さが奇数のノードです。
Ｃ集合を持っています。
Ｃ集合≠空集合の時、１つ兄弟ノードが存在するはずです。
この時、対になる兄弟ノードをＮＡ、ＮＢにします。
ＮＡ、ＮＢは、それぞれ複数の集合ＰＥを子ノードとして持っています。
これを、ＰＥＡ、ＰＥＢにします。
ＰＥＡとＰＥＢは、Ｃ集合の元（Ｅ）を介さないと、繋がる事が出来ません。
この時、出来る単純パスの一部は、ＰＥＡ数をＳＡ辺、ＰＥＢ数をＳＢ辺、
Ｃ集合の元の数をＣＮ辺とした時、
単純パスの最大の部分パス数＝ＳＡ×ＳＢ×ＣＮ辺となります。
つまり、複数の部分パスが構成されます。
そして、奇数ノードの親ノードに深さを１つ上げます。
その時、親ノードの子ノードはこの複数のパスに置き換わります。
Ｃ集合≠空集合の時で兄弟ノードが存在しない時、つまり、ＰＥＢ＝空集合の時、
ＰＥＡとＣ集合だけで、単純パスの一部のパスを構成します。
あれっ、上述の未確認項目は、必ずしも必須ではないようです。
もし、Ｃ集合＝空集合の時、兄弟ノードは存在しないので、
親ノードの子ノードは、Leafの集合ＰＥを継承します。
この繰り返しをＲｏｏｔまで行うと単純パスが複数出来ます。
その単純パスの最短距離が厳密解となります。
上述したのは、Leafのケースだけです。
深さが、Ｒｏｏｔに向かう事に従い、親ノードの下に置き換えられる
複数の部分パスは増えて行きます。
第２話 気付き
① どのくらいの計算量になるのか、はっきりしていない事に気付きました。
② 「完全グラフの場合、Ｖの要素(点）をどのように辿っても一筆書き出来る」
しかも「単純パスは、交差しない」も条件に加わります。
①については、対策を考えます。
手っとり早いのは、プログラムを組んで見る事です。
その他の手段は、考慮中と言う事にします。
②については、必須条件ではないかもしれません。
取り敢えず、考慮中と言う事にします。
第３話 凸凹図形
以前、凸凹図形について述べた事があります。
凸図形様に配置された集合Ｖは、凸図形になるように繋いだ頂点配列が、
単純パスの最短の距離となります。
そして、凹図形は、Ｃ集合の辺数が増えて、Ｘ集合の辺数が減ります。
Ｃ集合の辺数が増えると、単純パスの経路数が増えます。
この理由で、前章でも述べましたが、計算量を計算出来るという事は、
他に解法が存在すると同義になります。
凹んでいる頂点数や凹み方から、Ｃ集合とＸ集合の元数が異なって来ます。
逆に考えると、この事から解を求める事が出来るのかもしれません。
結論として「解法が未完成である」と、言えます。
良かったのは「僕の心」が、軽くなった事です。
他にトラウマを抱えているのかもしれません。
しかし、この問題が最大のものであった事は、僕自身が実感しています。
解法の続きは、折りを見て行いたいと思います。
論理矛盾や見忘れ等、指摘して貰えば幸いです。
