freecontentのブログ

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

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

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

第17話 ようやく宇宙の分解と繋がった

 ここから数話は、書かなくて済むものなら書きたくないのだが、本当に書きたいことのための前提として必須のようである。もっとも、本当に書きたいことが実を結ぶのか怪しいものだからここ暫くは、無駄なことを書いているのかもしれない。それでも書くことがあるということは嬉しいもので子猫の近況を織り交ぜながらこのブログを進めたいと思っている。
 元々、巡回セールスマン問題と直接出会ったのではなかった。若い頃に職の課題として持っていたのが、CADシステムを作ることであった。当時のパソコンでCADを実現することは不可能であるとさえ言われていたが、何人(何組)かの人がそれに挑戦していた。わたしもその一人で、他の人がどのような問題を抱えていたか知る由も無いが、わたしが抱えた大きな問題は、矩形と矩形の関係を最適な時間で検出するというものであった。この問題もNP問題に含まれるらしいのだが、未だにその解法を得ていない。得ていないのはその問題を放棄したからで、巡回セールスマン問題を解けばこの問題も解けると思い込んでしまったのだ。その当時NP問題というものがあるとは知らず、さらにはこの問題が世界でも未解決だとは全く知らなかった。いくつもの文献を漁ったのだが、問題の解決方法が載っていないのは当然でわたしを苦しませもさせ楽しませてもくれた。
 さて、N!(階乗)数をどのように分解していったものか考え続ける日々が延々と続いたが、数年前に次のことに気がついた。ノードを並び替えることに執着してはいけなかったのだ。着目すべきはノードとノードを結ぶエッジにあった。エッジとは線分のことである。ここでようやく「第14話 宇宙の分解」と話が繋がってくる。
 N点のノードを全て結ぶと何本のエッジ(線分)となるのであろうか。グラフ理論での完全グラフをイメージしてもらえばよい。有向グラフか無向グラフかは無視しても構わない。結果として有向グラフとなるが、それは全てが解けた後のことなので思考過程では考える必要はない。完全グラフの線分数はNの2乗となる。「それはおかしい」という方の思考は正しく正確にはNの2乗とはならない。しかし、その差はたかだかのもので、思い煩う必要はない。計算量を扱う分野では「たかだか」という文言が多く見られて、例えば、ランダウの記号O()に見られるように多項式の最も変化量の多い項だけを抽出する考え方もある。従って、プログラムなど厳密なものに取り組もうとされる方以外は概算で十分である。
 完全グラフの線分数(Nの2乗)の全てが親ノードとなる。任意の線分を選んで、「第14話 宇宙の分解」の図-001と002の無限直線と線分0とする。ここで与えられている集合は次の2つである。
 ノードの集合:P={P0、P1、P2、...PN}  線分の集合:S={S0、S1、S2、...SN^2} ここで集合Pが定まれば、集合Sが一意に定まるのは明白である。

×

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