Books-Science: 2004年11月アーカイブ
インターネットで便利な検索のひとつが経路検索。例えば乗換案内ではＡ駅からＢ駅まで、どのような交通機関を乗り継いでいけば最短でたどりつけるかが分かる。MapFan.netなら地図上に通過する道を表示させることができる。
・インターネット地図ソフト「MapFan.net」のご案内
http://www.mapfan.net/welcome/mfw/index3.html
こうした空間情報システムのアルゴリズムとはどんなものだろうか。
この本は代表的な空間情報検索の問題、
・最短経路問題
・制約条件付経路問題
・巡回セールスマン問題
・施設最適配置問題
などを取り上げ、その計算手法を分かりやすく説明する小冊子。
例えばこんな絵があるとして、円の中に●がいくつあるか。人間なら瞬時に3つと答えられるけれど、コンピュータが計算で求めるとなると、テクニックが必要になってくる。まずは円の内側にあるのか、外側にあるのかをどう判断する必要があるし、点を認識する必要もある。どう空間全体をデジタル情報に置き換えるかもやり方は複数ある。
また、3つ以上の点（ノード）を線（アーク）で結び、ＡからＢへの経路が複数できた場合、どれが最短かを求めるのは、少しややこしい問題になってくる。ノードとアークの数が数千や数万もできてしまうと幾何級数的に計算量が増大し、現状のコンピュータ処理能力では事実上困難なケースもあると言われる。さらに特定のノードを、特定の順番で回りたいなどの制約条件がついた場合、さらに解決はかなり難しくなる。
技術的な面白さだけでなく、社会問題を解く鍵としても使えることが示される。施設の最適配置問題の例では、住居、保育園、会社の分布を分析する。住民は朝、住居を出て保育園にこどもを預けて会社へ行き、帰りに子供を迎えに行って帰宅する経路をたどっている。現状では、時間制限を考えると10％程度の住人しか保育園を利用することができないのだが、保育時間を前後に少しだけ延長するだけで大半の住民が利用できるようになったり、次に保育園を設置するならばどこにすべきかが計算で求められる。
この本の全体の感想は、空間で考えるというのはコンピュータにとっては難しいことなのだなということ。地図を見て「こことここはつながっている」ということは人間ならば直感的につかめても、コンピュータは同じことをするのに膨大な量の計算を必要とする。
この本にはなかったが「いかなる地図も、隣接する領域が異なる色になるように塗るには4色あれば十分だ」を証明する四色定理の証明は、コンピュータを使って、印刷すると数千枚の数式として解が出てくると聞いたことがある。いまだ人の手で証明することができないそうだ。
関連情報：
Passion For The Future: 私的距離検索実験Geogeo
http://www.ringolab.com/note/daiya/archives/000412.html
四色定理 - Wikipedia
http://ja.wikipedia.org/wiki/%E5%9B%9B%E8%89%B2%E5%95%8F%E9%A1%8C
・楽らくスケジューラー
http://www.odakyu-group.co.jp/rakuraku/
箱根と江ノ島、鎌倉に対応。「行きたい場所やお店を選ぶだけで、出発地から目的地まで各スポットに必要な時間を自動計算。最も効率よくまわれるコース＆スケジュールをアッという間に作成します。」
