freecontentのブログ

日々の出来事から思い、動物、科学にわたって様々な自由な内容です。

にほんブログ村 猫ブログ 猫 多頭飼いへ
にほんブログ村

にほんブログ村 科学ブログへ
にほんブログ村

第19話 階乗数の分解

 最初にお断りしておきたいのだが、以下の内容(前話までもだが)は教科書には載っていない。さらには知る人もいないと思われる。従って、誰かが検証したものでなく、何処かに欠陥があっても不思議ではない。
 コンピュータ・プログラムを組んだことのある人ならば、2分探索や2分木、ソートなどの用語や意味を理解しているものと思っている。それらは互いに密接な関係があり、相性も持ち合わせている。どういうことかというと、2分探索はソートされた1次元要素に適用されて用いられるが、ソートされた1次元要素を2分木に逐次投入していくと、2分木は1本の線木となってしまう。そうなると2分木は全く意味をなさなくなる。そもそも、2分木は配列された1次元要素の並び次第で末端ノードの深さが異なり、ある意味安定性のない検索手段となる。それを回避する手段も存在するが、ここでの主題はそれではない。
 残念ながら2次元要素をソートする手段をわたしは知らない。存在しないはずだと思っていて、それができれば一躍脚光を浴びるのではないかと思っている。2次元要素から4分木のツリー構造を作成することは、比較的容易にできる。わたしはこれを平成2年ころに見つけて、あるシステムに応用したことがある。当時その手法は世に知られていなくてシステム実現の最大のネックとなっていた。最大というのは正確ではなく、最大は矩形と矩形の関係検索であり、それが今でも未解決である(どこかで書いたような記憶が)。
 さて、同種のノード(点)からなる完全グラフを分解していきたい。用いるアルゴリズムは2分木(2分ツリー)の応用である。応用であるから2分ツリーのイメージとはかなりの部分でイメージが異なってくるが、ツリーの整合性はとれているはずである。もしも、とれていなければその時点で破綻となり、このブログも終了となる。
「第17話 ようやく宇宙の分解と繋がった」で、
 ノードの集合:P={P0、P1、P2、...PN}
 線分の集合:S={S0、S1、S2、...SN^2}
ここで集合Pが定まれば、集合Sが一意に定まるのは明白である。
とスタートを切ったつもりである。
 ツリーの親ノードは、集合Sの要素全てになる。全てになるから大量の親ノードの数となるが、問題としている計算量と比べればNの2乗程度のものなので“たかだか”である。尚、Nは集合Pの要素数である。集合Sの要素は全て同種のものなので任意の要素を1つ選択する。
 第14話の図-001より、集合PをPLとPRに2分する。P= PL+PRであるから過不足はないはずである。
 図-002より集合SをSC、SX、SL、SRに4分する。S=SC+SX+SL+SRである。
次話で集合Sの4分の説明をしたい。

×

非ログインユーザーとして返信する