ニコニコ大百科

これ始めて知ったんだけど、「最速降下線」を求める「変分法」とまるで原理が違って面白い。

編集者です。とりあえず図だけ描いておきます。
記事内参照用URL :

OSPFというルーティングプロトコルはこういう計算によってルーティングテーブルが決まったりします。
あと、駅すぱあと作った人もこういうことのプロじゃないかしら。

ＯＳＰＦはダイクストラ法やね

>>2の図の各地点への最短ルートです。
この絵を基にしています！ 記事内参照用URL :

消した部分を白くペイント、ゴミの消去。
この絵を基にしています！ 記事内参照用URL :

紙に図を書いて、端と端をくっつけて最短距離～♪　・・・なぁんてネタを予想した結果がこれだよ。

マジレスすると、アルゴリズムを考えるうえでそれはなんの役にも立たないからな
1年以上も前のレスだけど

電車の乗り換え案内だと

乗り換えに発生する移動時間
・AからBに行くとき、乗り換えなしで行くと10分かかる
・A→Cは5分、C→Bは3分なのでCで乗り換えたほうがいいように見える
・が、C駅で乗り換えるのに3分かかるので、実際には乗り換えると損する

電車の密度
・AからBに行くとき、乗り換えなしで行くと10分かかる
・A→Cは5分、C→Bは3分、C駅での乗り換えは1分なので乗り換えたほうがいいように見える
・が、C→Bの路線は1時間に1本しか走っていないため、よほど乗り継ぎが良くないと待たされてしまうので損する

客のわがまま
・なるべく早いルートにしたい
・なるべく安いルートにしたい
・乗り換え回数を減らしたい
・可能な限り座っていけるルートにしたい
・ある駅までの定期を持っているので可能な限り定期を使いたい
・雨が降ってるけど傘を忘れてしまったので、乗り換える際に地上に出たくない
・もし目的地のすぐ近くに別の駅があるなら、そちらの駅に行って歩いても構わない

等、単純な最短経路問題には落としにくい様々なパラメータがあって、
これをどのように解くかが各社の腕の見せ所

塩入り寒天を壁にした道を作って、スタートと分岐点とゴールに餌を置いて、出発点に粘菌を置いとけばアラ不思議。どんなに複雑でも最適解が出るんだとか。場合によってはスパコンより早いそうで。
ちなみにこのネタ、二度もイグノーベル賞取ってるんだよね。都心圏の鉄道・道路網を再現しやがった、という話は本当に驚いた。

>>10
軽く見たことがあるんだけど粘菌でこんなことできるのかあと感心したよ
あと少し凄い発見があれば本家ノーベル賞も取れるレベルな研究だとは思うんだけど

解説わかりやすかった!! ありがとう!!

>>10 >>11
今更レスするのもあれなんだけど、
それの応用として「粘菌は強い光を嫌う」というのを組み合わせると
「粘菌があまり通りたがらないエリア」というのも実現できる

どういうことかというと、山や大きな川なんかの
できれば避けたいエリアを迂回するべきなのか突っ切るべきなのかまで
粘菌に解かせたりもできるんだな

つまり目的地に効率的に辿り着きたいなら
googleマップに頼るより粘菌を育てたほうがよいってことだな