最初にゴールに着く道は？：日経サイエンス

	日経サイエンスは米国の科学雑誌「SCIENTIFIC AMERICAN」の日本版です。
	HOME

HOME ＞パズリング・アドベンチャー＞最初にゴールに着く道は？

ご購入のご案内

検索方法はこちら

サイト内検索結果に戻る

最初にゴールに着く道は？

デニス・シャシャ

　ある町には南北方向に６本，東西方向に６本の自動車専用道路があり，それぞれが10km間隔で格子状に並んでいる（下図）。道路が交わる地点はすべて立体交差になっていて信号はなく，交わっている道路に移るには専用の分岐路を使うので余計な時間はかからない。このあたりの交通量は非常に少ないが，スピード違反に対しては警察が監視の目を光らせており，見つかれば厳罰が待っている。
　各道路の制限速度は奇妙なパターンで決められている。東西方向に走る道路は，最も南の道路が時速10km，その隣りが時速20kmというように時速10kmずつ増えていく（したがって，最も北の道路は時速60kmだ）。同様に，南北方向の道路も，最も西の時速10kmから最も東の時速60kmまで，時速10kmずつ増えていく。
　道路が交わる地点には，２本の道路の番号を用いて次のようにラベルをつけておく。格子の南西の角は（１，１），南東の角は（６，１），北西の角は（１，６），以下同様だ（第１要素は南北方向の道路の西からの番号，第２要素は東西方向の道路の南からの番号）。

ウォーミングアップ問題

　ウォーミングアップ問題として，（１，１）から（６，３）まで最短時間で行くルートを求めてほしい。

ウォーミングアップ問題の答え

　すぐにわかるように，最短時間で行くには何通りかのルートがある。１つの方法は，（１，１）から１時間で（２，１）まで進み，さらに１時間で（２，３）まで，最後に１時間20分で（６，３）へ行くというものだ。一方，最も時間がかかるのは，これと同じ距離のルートだけを考えると，５時間かけて（１，１）から（６，１）へ行き，そこから20分で（６，３）に達するものだ。

　今回の問題は，（１，１）から出発してすべての立体交差点を通過するルートのうちで，最短時間のものを求めることだ。出発点を変えることでもっと短い時間で回ることができるならば，その出発点を求めてほしい。私は出発点が（１，１）のままが一番良いと予想しているが，予想はしばしば裏切られるものだ。この予想は証明できるだろうか？

※画像をクリックしていただくと、大きな画像でご覧いただけます。

●道路網と制限速度　赤い線で示したのがウォーミングアップ問題の解の１つとなるルート。黄色い線は，同じ距離で最も時間がかかるルートだ。すべての立体交差点を通る最速ルートはどうなるだろう？

	田中裕一（たなか・ゆういち）

	アルティス・リサーチ代表。専門は計算機科学。

	Dennis E. Shasha

	ニューヨーク大学クーラント研究所教授。専門は計算機科学。　原題名 Grid Speed （SCIENTIFIC AMERICAN March 2004）


会社案内　\| 「日経サイエンス」はこんな雑誌　\|　個人情報の取り扱いについて　\|	Copyright 2005 NIKKEI SCIENCE Inc., all rights reserved