8 フレームワーク（１）
8 フレームワーク（１）
「さて、想の理論を聞かせてもらうもん」
「聞かせてやるが、ついてこいよ」
「当たり前だもん」
「この理論は集合と変形木構造からなるアルゴリズムだ」
「数式は使わないもん」
「そうだ。使いたくても使えない。というか使うところがない」
「いいもん。いいもん。脱関数だもん」
「一番わかりやすい例は*完全グラフの分解になる。それに*巡回セールスマン問題を絡めて説明しよう」
「心の準備はOKだもん」
「ここにNノード数の完全グラフがあるとする。さて、巡回セールスマン問題を力づくで解くとき何通りのルートを計算しなければならないか。わかる人はいるかな？」
「はい、はい。というかわし一人しかいないもん。でも答えは言うもん。O（N！）だもん」
「おお、いきなり*O記法を持ちだしたな。ではNノード（都市）の都市の巡回セールスマン問題の辺道はいくつかな？」
「O(N＾2)本だもん」
「ぶっぶ～。結果にO記法は便利だけど、計算途中にO記法を用いると落とし穴に落ちる時がある。正解はN（N-1）/２本だな。それに辺道を完全グラフでは単にエッジ（辺）と呼ぶ。そしてエッジを過不足なく繋いだルートをパスと呼ぶ。巡回セールスマン問題はそのパスの中でも最短のものを結果とする。点を繋いでも同じだが、このアルゴリズムはエッジに主眼をおく」
「ふむ。了解だもん」
「ここで、ノードの全体集合Pとエッジの全体集合Eを考える。この2つの全体集合が木構造のルートになる。ここまではいいか」
「OKだもん」
「次にこの集合を分解する。今回は簡単な分解条件によって2つに分解することにする。この分解条件が後々重要な意味を持つから忘れないようにな」
「OKだもん。忘れたら聞くもん」
「分解条件は、”パスの中のエッジは交差しない”だ。さて、全体集合Eからエッジを1本抜き出す。そしてそのエッジをルートの属性とする。つまりルートはエッジの数だけ存在する」
「深呼吸するもん。ややこしいからエッジ1本だけ考えるもん。他のエッジも同じだもん」
「そう、それが賢明だ。次にルートのエッジ（原エッジ）とそれ以外の全てのエッジ（対象エッジ）を考える。そしてその関係を4つに分類する。①対象エッジの両端が原エッジの右側に存在する。②対象エッジの両端が原エッジの左側に存在する。③対象エッジと原エッジが辺の内部で交差する。④対象エッジと原エッジが辺の外部で交わる」
「理解の限界が近いもん」
「もう少しで今日は終わりにしよう。①と②は単純だからいいとして③は”パスの中のエッジは交差しない”という分解条件に反するから除外④は交差はしないけど、両端が左右に分かれる。この④は①の集合と②の集合を繋ぐ大事な役割を担う」
「降参だもん。宿題だもん」
「もう少しだ。①に含まれるノードは②に含まれない。②も同様だ。エッジで分けたからノードが重複するが、同じノードは１ノードとカウントする。③は除外だから④を考える。右側にくるノードと左側にくるノードに分けられる。そして、右側のノードは必ず①のノード集合に含まれる。左側も同じだ。もし、含まれなければ、アルゴリズムが根本から間違っているかエッジが孤児であることを意味する」
「想、もう勘弁してくれもん」
「わかった。ではまとめよう。①のノード部分集合をRN1集合、エッジ部分集合をRE1集合②のノード部分集合をLN1集合、エッジ部分集合をLE1集合③は破棄④のノード部分集合をCRN1集合とCLN1集合、エッジ部分集合をC1集合とする。CRN1とCLN１は冗長的で後で除外するかもしれないが、取り合えず残しておきたい。これで完全グラフがコネクション付きで2分されたことになる」
「ふ～～～だもん」
「そうそう、原エッジ上に他のエッジの端点が乗っかるときは特例として後で考える。今考えると混乱のドツボに嵌るからな」
想にいつこのアイディアが生まれたのか定かではないが、もしかするとあのアルコール依存症騒ぎのときだったかもしれない。まだ、アルゴリズムのアイディアは緒に就いたばかりであるが、これがこれから世界に影響を与えることになる。
*完全グラフ： N個のノード（点）が存在するとき、全てのノードから全てのノードへ結線したグラフである。必ず、同じ結線が2度現れるから一方は無視する。
*巡回セールスマン問題：N個のノード（点）（都市）が存在するとき、全てのノード（都市）をちょうど一度ずつ巡り出発地に戻る巡回路の総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。
*O記法：O()と表記する。（）は式の動値辺（右辺または左辺）の最も変化量の多い項を漸化した式を表す。O()は、O記法による漸化式と呼ばれる。()の内部以外の項はしばしば高々の変化量の項である評価される。また定数も高々の変化量であるとして（）内から除外される。O(n!)、O（ｎ＾ｎ）などは超高計算量の例である。また、ランダウのO記法と呼ばれることもある。
