コスト最小化ルートに悩む「人生ナビ」 Dijkstra's algorithm

コスト最小化ルートに悩む「人生ナビ」 Dijkstra's algorithm
 
人生は選択の連続であ~る。

「今日のネクタイはどれにするか?」
「お昼はどこで何を食べるか?」
「お風呂でまずどこから洗うか?」

その一つ一つの選択で次の瞬間の展開が大きく違ってくる場合もあります。

「あの時あちらを選んでおけば良かった・・・」
何てことは長い人生で星の数ほど経験するものです。

何を選択するのが正しい答えなのか?
それが分かっていれば人生は楽勝なのです。

そんな人生の最適ルートを教えてくれる神アプリがあればどうでしょう。

「お昼はラーメンかカレーのどちらにすればいいの?」
「(神アプリ)・・・カレーにしなさい。」
なんてことになります。

もちろんその結果は当てずっぽうじゃなくて、ちゃんとした根拠があるのです。
そんな人生アシストなアプリを模索中です。

簡単にはナビソフトで、あれはよくできています。
出発地と目的地をセットすると出来るだけ最短でスムーズな道順を示してくれます。
最近では渋滞具合も加味して迂回したり、予想到着時間も教えてくれます。

これを人生に置き換えた「人生ナビ」アプリを作れば、あとはその指示に従えっていればいいのです。
例えば「億万長者になりたい」と指示をすれば完了です。

どうやってく作るか?
これが問題です。

ナビは各地点の座標とそれを繋ぐノードを地図情報してデータベース化されています。
そのデータから距離計算をして最適ルートを見つけます。
道が繋がっている限りローマにだって案内してくれるわけです。

ここで「距離」は「コスト」として置き換えられます。
各座標とそれを繋ぐ「ノード」はそれぞれの「関係」として整理できます。
これさえセットできれば人生ナビは可能なのです。


今回は入門的な「ダイクストラ法」で解いてみましょう。
このアルゴリズムは簡単ですが色々な活用が出ます。

前提として各評価ポイントとそれを繋ぐノードを用意ます。

今回はランダムに作成した標高地図を例題に、できるだけ最小コストで移動できるルートを探します。
一つのルールとして「坂道を登るのはしんどい、でも下りは楽ちん」としました。

つまり今の座標から次の座標に移動するとき、その標高差をコストとして計算します。
ダイクストラ法ではマイナス評価は扱えませんので、下りの場合は移動距離だけのコストとします。

解の求め方としては目的地から逆計算します。
そうすることで全ての座標から目的に向かう最適ルートを1回で計算できます。

最適なルート計算はこうです。
・現在地(目的地)から次の接続先までのコスト計算をします。
・コスト計算の結果を接続先が保持しているコストと比較します。
・比較の結果、新しいコストのほうが低ければコストを上書きして新たなルートとして追加します。
・この時、接続された元の座標も保存しておきます。
・追加されたルートから新たな接続先を見つけて評価を行います。
・これを繰り返して見つけた全てのルートの評価を行います。
・全ての計算が終わったあと、スタート座標から保存されたルート座標をたどれば目的地までたどり着けます。

ここでコストと評価基準は色々な計算式に置き換えられます。
つまり人生の目的とその満足点を表現すればいいわけです。
問題はその評価点の位置関係と接続関係をどう表現するかがポイントとなってきます。

例題としてプログラムしてみました。リンク先からご覧ください。
目的地である右下の座標に向かう3カ所からの最適ルートを表現しています。
地図をクリックすると新たな地図とその最適ルートを計算します。

Map Root Dijkstra's algorithm
http://www6.plala.or.jp/TimeTripper/html5/root.html

ここまで話をすると占いというものがいかにバカバカしいものか理解できるかと思います。
何の前提情報もなく、あてずっぽうで人生の道が当たるわけがないのです。

全ての占いは単なる乱数です。
優れた占いは正規乱数の計算式だったりします。
つまり偏りのない、常に予測不可能な答えを出してくれる占い方法が優れているわけです。

人生は一人ひとり違います。
その違う答えを導くためにはより複雑系の計算式が必要です。
そのために生まれた時間や星座を使ったりするわけです。

簡単にはサイコロです。
正確に作られたサイコロは正規乱数を教えてくれます。
6択の人生ならこれで十分です。

最近の天気予報が天気占いのレベルなのは、季節変動期に入った地球の気候モデル地図をセットできていないためです。
つまり過去の気候データをたよりにしても当たらないのです。
それこそスパコンよりサイコロを振ったほうが的中率が上がるかもしれません。

ということで、
今回のアルゴリズムを「人生ナビ」として適用するためには、
まず「人生地図」を自分で作成しなければなりません。

まっ、これが作れるくらいなら、すでに人生の勝利者になってると思いますが・・・
というか、人生の暇つぶしがテーマだったりします。(笑)