NHK番組「世界を変える魔法！ アルゴリズミ子研究所」(全3回)の感想です。
（※以下、今回の話の結末まで書いてありますのでご注意ください）
■世界を変える魔法！ アルゴリズミ子研究所 - NHK
http://www4.nhk.or.jp/P3285/
NHK Eテレでの視聴です(放送日：2015年7月16日(木)、23日(木)、30日(木) の 23:30〜23:55)。
■番組概要
＞話題の最新機器の意外な“しかけ”とは？コンピューター世界の女神、アルゴリズミ子（橋本環奈）が出す難問によゐこ有野晋哉が挑戦。解明に挑む。
2014年9月30日(火) 23:00〜23:45に放送した番組の続編。全３回。コンピューターを動かすための仕組み「アルゴリズム」を解説するバラエティ番組。
（※2014年版感想→ http://d.hatena.ne.jp/Perry-R/20141001/p1）
第３回 カーナビ編
■内容
＞スマホ、掃除ロボットなど続々と登場する最新機器の意外な“しかけ”とは？そこには世界を動かす魔法=アルゴリズムの存在があった。開発者の「目からウロコの解決策」を見破れるか？コンピューター世界の女神、アルゴリズミ子（橋本環奈）が出題する難問によゐこ有野晋哉が挑戦、アルゴリズムを解明。子どもから大人まで一緒になって頭をひねり「考える力」が鍛えられるEテレ発、知的エンターテインメント。第三回「カーナビ編」
網の目のように分岐している道路で、カーナビで出発地点から目標視点までのルート検索の方法を考える。
コンピューターに与える命令は以下の３つ。
1. スタート地点とゴール地点を決める
2. （？）
3. ルート決定
さて、２番に入る命令は以下のどれか？
(a)早い（所要時間の短い）順に道を選ぶ
(b)全ルートの所要時間を比較
(c)まず手近な範囲に絞って所要時間を比較
正解は(c)。
(a)の、目先の所要時間の早い順に道を選ぶと、以下のような問題が発生する。
スタートのA地点からB地点までは２分
スタートのA地点からC地点までは１分、C→Dは５分、D→Bは３分、
の場合、Ａから直接Ｂに行けば２分で済むのに、目先の所用時間が早いＣに進んでしまい、Ｃ→Ｄ→Ｂと遠回りして、結局９分かかる、という事態が発生する。目先の所要時間だけ考えていたのではダメ。
(b)の全ルート検索は、間違いではないが所要時間がかかりすぎ、現実には不可能。碁盤の目のような「１１×１１」のルートの総ての組み合わせを考える場合、最新のコンピューターでも『２９０億年』かかる（※ちなみに宇宙が誕生したのは１３８億年前である）。こういう枝分かれをいちいち調べる際に、パターンが非常に多くなることを「組み合わせ爆発」という。
ということで(c)のように、まずある程度限定した範囲で組み合わせを調べて、一番早いルートを調べて他のルートは切り捨て、次に少し範囲を拡大して、先に見つけた一番早いルートに繋がる道を調べて、他の道は切り捨て、という方法で全ルートを確定する。これを「ダイクストラ法」という。
■感想
ほーう、ちょっと勉強になった。
