◇お題３　ダイクストラ法

ダイクストラ法

「　↑数字は距離だと思ってくれだぜ☆
Start から Goal まで、数字を足していって　一番少なくできる経路を　教えてくれだぜ☆」

「　ｅｄｂａじゃないか☆？」

「　その答えを出した方法を教えてくれだぜ☆」

「　まったく別の話題に移るのね」

きふわらべのやり方

「　まず　スタート地点の　ｅ　に着目する☆
これを　クエン （Current; カレント; 現在）としよう☆」

「　そこから伸びる　エーッチ （Edge; エッジ; 辺）は３本☆」

「　矢印の デスッテネーィション （Destination; デスティネーション; 先）側にある ノーゥット （Node; ノード; 節）に、
通った エーッチ （Edge） の点数を書くぜ☆」

「　過ぎたところは消す☆
これで今、 スターット （Start; スタート; 開始）地点は３つになったぜ☆」

「　同様に、デスッテネーィション（Destination）側にある　ノーゥット（Node）に、
通ったエーッチ（Edge）の合計を書くぜ☆　ここで☆」

「　ノーゥット（Node）には既に　点数が書かれているものもあると思う☆
ここでは　数の小さい方を残せだぜ☆」

「　じゃあ、ノードの点数には　パァーッ（Path; 経路）も　↓タグ付けしておく必要があるわね」

「　それもそうかだぜ☆」

「　同様に　過ぎたところは消す☆
ゴールは除くと、
スターット（Start）地点は６つになったぜ☆」

「　↑同様に、デスッテネーィション（Destination）側にある　ノーゥット（Node）に、
通ったエーッチ（Edge）の合計を書くぜ☆　ここで☆」

「　同様に、ノーゥット（Node）には既に　点数が書かれているものもあると思う☆
数の小さい方を残せだぜ☆」

「　他のルートでやったとこは、もう　やらなくていいんじゃないの？」

「　うーん、むずかしいものだな☆」

お父んのやり方

「　じゃあ　わたしが　やってみるかだぜ☆」

「　スタート地点を、壁に　釘で　打ち付けるとしよう☆
玉が　糸で　つながっているので、重力で　下に落ちるぜ☆」

「　うむむ☆」

「　↑次に第２世代で同世代決戦だぜ☆」

「　ここが　むずかしい☆」

「　↑隣から　やってきたときの合計も気になるが……☆」

「　↑端から　端へ移動したときの合計も気になるよな☆」

「　ヨコに進んでどうすんの？」

「　↑ヨコのつながりを　切ろうぜ☆？」

「　↑あっ、二分木になった！」

「　↑次は第三世代だな☆
ここは　ヨコの線を切らなくても、ゴールに最小で　たどり着いたもの勝ちだぜ☆」

「　あっさり読み切ったな☆　何でだぜ☆？」

「　↑ 下に行くだけ　という作戦勝ちだぜ☆
その作戦に持ち込むように、同世代決戦してヨコのつながりを切ったんだぜ☆」

ダイクストラのおっさんのやり方

「　もっと専門的に見ていくことにしよう☆
誰が　どこからコピーしたのか知らないが、　Ｗｉｋｉｐｅｄｉａの『ダイクストラ法』の日本語版のページには
英語版にはない説明が載っている☆　スペインや韓国とも違う☆　日本語版だけ　独自の世界に行っている☆」

「　↑大文字のＶは　型　だと思ってくれだぜ☆　ノーゥット（Node）型を　Ｖ　と書くとしよう☆」

「　↑小文字のｖは　インスタンス（Instance）　だと思ってくれだぜ☆　何でも指せる☆
しかし　何でも指せるのでは　逆に説明に使いづらい……☆」

「　↑そこで　小文字のｖは　ノーゥット（Node）型のインスタンス（Instance）　だけを示すと　縛りを入れるぜ☆」

「　↑ foreach v ∈Ｖ　と示せば、図中の各ノードのことを言ってるのが分かるな☆」

「　小文字のｓは　スタート地点の　ノーゥット（Node） を示しているとするぜ☆」

「　d(v)　という関数は　ディスタンス（Distance）の頭文字なのだろう☆
ｓ　からの経路の数の合計を出すぜ☆」

「　コンピューター・プログラミング　を　やり慣れていると　d(v)　という関数に値をセットする表記は　慣れないし、
英語版でも韓国版でもスペイン版でも　dist[v]　と配列になっているし、分かりやすい☆
日本語版のＷｉｋｉｐｅｄｉａだけ読んでたら　読み替えの　負荷が大きい☆」

「　スタートのノードには　０　を、
それ以外のノードには　コンピューターが表現できる整数型の最大値を入れておけばいいだろう☆」

「　同様に　prev(v)　には　Undefined を入れておけだぜ☆
べつに　None　でも　Null　でも　無いという意味なら　なんでもいい☆
prev(v) というのは、最短経路を辿っているとき、自分の１つ前のノードのことだぜ☆
もちろん英語版では　prev[v]　という配列になっている☆
日本語版Ｗｉｋｉｐｅｄｉａで数学を調べる場合は、
書いたおっさんコンピューター・プログラミングやってないな、ぐらいに思えだぜ☆」

「　また、空っぽの　Ｑ　というものがあるとしよう☆
キューゥ（Queue）の頭文字だと思うが深い意味は無いだろう☆　これは容器なんで、中身に何かを入れたり、抜いたりできるぜ☆
上図は　空っぽだぜ☆　空集合☆」

「　↑ある意味、Ｑ　というのは　Ｖ　の中身の　すべての組み合わせ　を取りうる何か状態のようなものだと言えるだろう☆」

「　↑そういう意味で、Ｑ　は　Ｖ　の部分集合ということができるぜ☆
困ったことに　⊂　記号の意味は　⊆　を兼ねる場合があるので、どっちの意味で使われているかは　そのとき考えろだぜ☆
ここでは、Ｖの中身に無いものはＱの中身にもない、ぐらいの意味だぜ☆」

「　↑で、各ｖについて、ｖをＱに入れろだぜ☆」

「　Ｖの中身を　Ｑに全部入れるだけの話が　長いな……☆」

「　ここまでが　前処理☆　次からが　本処理☆」

「　たいしたこと言ってないのに　数学は　むずかしく書くわねぇ」

「　↑本処理は、Ｑに何か入っている間、ずっと続くぜ☆
これが最初に出てくるということは、ノードを減らしていくのが　この問題を解くための　大戦略　ということだぜ☆」

「　消去して　組み合わせを減らしていくことが　一番よく効く　問題の本質への解決方法なのだろう☆」

「　↑d(v)　を表示してみるぜ☆」

「　↑ダイクストラの創始した方法では、Ｑから　d(v)　が一番小さい　ｖ　を取り除いて、それを　ｕ　とするぜ☆」

「　最初に　取り除くのねぇ」

「　↑数学では　foreach に条件を使うことで、絞り込みができる☆
プログラム言語では　絞り込んでから foreach するかと思う☆　まあ、読み替えろだぜ☆」

「　↑で、　日本語版の　Ｗｉｋｉｐｅｄｉａ　では　Ｑ　ではなく　Ｖ　から　ｖ　を取っている☆
誰が何考えて　どこからコピーしてきて　そう書いたのかは知らん☆
英語版では　Ｑ　から　ｖ　を取っている☆」

「　せっかく　Ｑ　でノードを減らしていってるのに、日本語版Ｗｉｋｉｐｅｄｉａでは
なんで　Ｖ　を使って　foreach　するの？？」

「　知らん☆」

「　アルゴリズム上、ｕとｖは隣接しているぜ☆
これは　セグメンッ（Segment; 線分） とか、 エーッチ（Edge; 辺） とか　いろいろな呼び方があるが、
ノードと　ノートの間には……☆」

「　↑数がある☆　これ　そのものに　名前は付いていないが、
Length(u, v)　で　この数を調べられることにしよう☆」

「　↑ d(u) と、Length(u, v)　の違いは　しっかり見分けてくれだぜ☆」

「　↑ｓからｖまでの長さを求めて、 alt に入れようぜ☆」

「　↑d(u) より小さな alt　を探しているわけだぜ☆」

「　それぐらい　わたしも　探していたが……☆
alt の方が小さいということは、より最小の経路を回ってきたということだな☆」

「　ｕ　は　Ｑに残っているｖの中で　最小のｄ（ｖ）　というのが　ダイクストラの工夫なのよ」

「　↑　より近道を見つけた場合は、ｖ　に関する記録を更新しろだぜ☆
それ以外は　何もしない☆」

「　プログラムで書けることを　数学風の書き方をしているけど、
計算機科学による説明の方が　読みやすいのだから、
日本語版Ｗｉｋｉｐｅｄｉａの数学の記事は　参考にしてはいけないのよ」

問題を作成しようぜ☆？

「　さて、プログラムの練習をしようにも、何から手を付ければいいのか……☆？」

「　ノーゥット（Node）を主とするか、エーッチ（Edge）を手とするかで分かれるな☆」

「　全体を１本の　セグメンッ（Segment）と考えて、それに　バイパース（Bypass）を　増やしていけばいいのよ！」

「　というと☆？」

「　↑まず　１つの　セグメンッ（Segment）　を作るのよ。
ここから　ランダムに　２つのノード　ｕ，ｖ　を選ぶの」

「　↑そして　新しいノード　ｗ　を作成し、　ｕ，ｗ　と　ｖ，ｗ　をつなげるのよ。
この操作なら　１本の線が　複線　になっているだけだから、　立体交差　が起こらないメリットがあるのよ」

「　Ｓコンビネーター感ある☆」

「　じゃあ、ここで　Ｋコンビネーターとか出てくるのかだぜ☆？」

「　↑同様に、新しいノード　v3　を作成し、　v2，v3　と　ｖ1，ｗ3　をつなげるのよ」

「　↑これを続けると　網　は作れそうだよな☆」

「　↑Bypassなしでひとつ飛びのノードをつないでもいいのよ！」

「　立体交差しそう☆」

「　↑じゃあ　複線　のメリットを残しつつ、長所を伸ばしていこうぜ☆
複線を作ったときに　その両端の　ｕ，ｖ　ともに　生えている　セグメンッ（Segment）の本数が３本以上の場合に限り……☆」

「　↑線分　ｕ，ｖ　は　削除して構わないことにしようぜ☆」

「　Ｋコンビネーター感ある☆」

「　それって　線分　ｕ，ｖ　の途中に　新しいノード　ｗ　を作るのと同じなのよ」

「　このアルゴリズムでは　将棋盤のようなグリッドも引けないと思うぜ☆」

「　立体交差しないように　工夫したからな☆　当然だろ☆」

「　十字交差　は　していいのでは☆？」

「　立体交差させずに　十字交差　させるのは　むずかしいのよ！」

「　↑人の目には　a　と　b　は　つなげても良さそうに見えるけど、
ａ　と　ｃ　は　他の線に交わってしまうので　つなげられないということを　説明することが　むずかしいのよ」

「　a　と　ｃ　の違いを　説明することが　むずかしいのよ」

「　a　と　c　は　XOR（エックス・オア）の関係にあるのでは☆？　例えば……☆」

「　↑こう見せれば　ｃ　の方がつながり、　a　の方は　つながらないように見えるぜ☆」

「　それは　線１本の違いよ」

「　このように　外を通っている線があれば　ｃ　は　ａ　の外側に回ることは　ないわよ」

「　輪っか　であることを説明できたら　ａ　と　ｂ　は　接続しても　他の線と交差しないことを　説明できるかもしれない☆」

「　輪っか　じゃ　わかんないのよ！」

「　↑全てが外側に面している円の円周上　にある２点は、複線　にしても　他の線と重複せず　描く方法があるぜ☆
見ようによっては　内側にしても同じだが……☆」

「　どうやって　それを判定するんだぜ☆？」

「　外周判定アルゴリズム　を作るのが先かだぜ☆」

「　あらゆる内側の空間　は、見ようによっては　外周　なんじゃないの？
服を裏返すみたいに　ネットワークの図形を裏返すのよ」

点と凹多角形の内外判定を行う

「　↑角度を使うと　内側か　外側かは　判定できるようだが……☆
外周かどうかは☆」

「　ジオメトリーを使わずに、ロジックだけで　判定できないものなのか☆？」

「　↑a から b に線を引いても、他の線と交わらないことを判定するアルゴリズムかだぜ☆」

「　他の線と交わることを判定するアルゴリズム　を作って、それを否定した方が早くない？」

「　まず　トーゥレス（Torus; トーラス）を作って、そこに線を引きましょう」

「　分からん言葉を使い始めた☆」

「　トーゥレスは　中身が詰まっていないドーナツの表面だな☆
ドラクエの地球の形で有名なやつだぜ☆」

「　↑しかし　内側も　外側も　なくなってしまった……☆」

「　目を覚ましなさい。　最初から　内側とか　外側　というものは　なかったのよ」

「　↑服を裏返して脱ぐ　のを　トーゥレス　で縛って禁じたわけかだぜ☆」

「　何を言っているか分からん☆　必殺技の解説は禁止だぜ☆」

「　↑a　と　ｂ　がいわゆる外周にいるかどうかは、
２通りのコースで　a と b がくっつけば　確認できると
アッサンプション （Assumption; 仮説）を立てましょう」

「　↑この絵では　f　と　e　が、向かって左側を通って１周して　他の線と交わらずに
線をつなげるような見た目をしているが、
実際には　a,f,b,d　の線に遮られるはずだろ☆　平面とは対応してないんじゃないのか☆？」

「　じゃあ　↑ サレンダァ（Sylinder; シリンダー; 筒）で十分だったのかしら」

「　内側と　外側が　分かれた……☆」

「　↑上図の　赤と　緑の　どちらかの線が　遮られたかどうかの判定というのは
できるものなのかだぜ☆？」

「　むしろ　遮られないものが　タテ一列に並ぶのよ。
ここにタテ一列に並んでいる２つのノードは　他の線と交差せずに　つながるの」

「　↑今見ているのは　この例　なので……☆」

「　↑ｃ　と　ｂ　は　線を横切ってしまうのが　どういうことなのか　絵にしてみるかだぜ☆
……、あれ、ｃ　と　ｂ　は　線を横切らずに　つなげることができるぜ☆」

「　↑このように都合よく見ることができるだろ☆」

「　↑だから　ｃ　と　ｂ　は　他の線と交わらずに　つなぐくとができる☆」

「　うぎぎぎぎ！」

「　↑これぐらい　格子を入れて　やっと　ｂ　と　ｃ　は　つながらない、ぐらいだぜ☆」

「　↑これだけやっても　ぐるっと　回ってくるからな☆」

「　↑なんだこれは……☆」

「　なんなのよ　これ！」

「　↑ｂ　も　この位置にいれば　立体交差してしまうわけだが、
ジオメトリーを使わず、ノードとノードの接続の関係だけ知っていて
立体交差のないグラフを描けると、判定する方法はあるだろうか☆？」

「　接続している辺の数でも数えれば　なんとかなるのだろうか☆？」

「　↑言ってしまえば　上図の　左図と　右図　を別クラスターに仕分ける判定方法は存在するか☆？」」

「　例が少なすぎてなんとも……☆
サンプルを増やせば　何か見えてくるのでは☆？」

「　あんたの直観で一発で仕留められないの？」

「　ノードの数が　６　に対して、
左図は　ノードの接続数が　５、４、４、３，３、３　と並んでいるのは　何かを感じるぜ☆
ノード数が　５　でも　このような比較の図は　作れるだろうか☆？」

「　やってみるぜ☆」

「　↑ｂ　と　ｄ　は　つながらないぜ☆」

「　↑ノードに接続しているエッジの数は　こうだな☆」

「　ノードの数が　５　に対して、
左図は　ノードの接続数が　４、４、３，３、２　と並んでいるのは　何かを感じるぜ☆」

「　なんらかの許容できる上限値があるのかしら？」

「　誰が　こういう問題に詳しいのかしら？」

化学構造情報とグラフ理論

「　↑バケ学だろ☆　調べて寝よう……☆」

＜書きかけ＞