遭難者を捜せ：日経サイエンス

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

HOME ＞パズリング・アドベンチャー＞遭難者を捜せ

ご購入のご案内

検索方法はこちら

サイト内検索結果に戻る

遭難者を捜せ

デニス･シャシャ

　ハイカーが１辺10kmの正方形状の原野のどこかで大怪我をしてしまった。歩けないので救難信号を発信しているが，この信号の到達距離は2kmだ。救助隊がその電波の到達範囲に入れば，方向探知機を使って直ちに遭難者を助けに行くことができる。あなたの任務は，救難信号の届く範囲に，できるだけ早く，確実に入ることだ。ただし救助隊の四輪駆動車は，この正方形の辺上であれば，どの地点から進入してもよいものとし，連続した線に沿ってのみ動けるものとする。また，その速度は10分に1kmとする。

ウォーミングアップ

　ウォーミングアップとして，長方形の原野の問題を考えよう。原野の面積は100km²のままとする。長方形の各辺の長さがどのようになっているとき，救難信号を最短時間で確実にキャッチすることができるだろうか？答えを下に示した。

　１辺が10kmの正方形の問題に戻って，300分以内に確実にハイカーを見つける方法を考えてもらいたい。これが今月の問題だ。
　このパズルにはいろいろなバリエーションが考えられる。たとえば，救助隊が２チーム以上ある場合はどうだろう？複数の経路に沿って動くと探索は簡単になるだろうか？私が最も面白いと思うのは，救難信号が変化する問題だ。たとえば，信号が１分ごとにオンとオフを繰り返すのはどうだろう。その場合，350分以内にハイカーを見つける方法があるだろうか。

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

　捜索時間が最短になるのは長さ25km，幅4kmの長方形の場合だ。四輪駆動車は一方の短辺の中央から入り，対辺の中央に向かってまっすぐに進む。この25kmを進むのに250分かかるが，その間に長方形内のあらゆる点から2km以内の地点を通る（訳注：米国の読者がこれよりもさらに短くてすむ解を見つけている。詳しくはこちら）。

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

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

	Dennis E. Shasha

	ニューヨーク大学クーラント研究所教授。専門は計算機科学。原題名 Missing Hiker （SCIENTIFIC AMERICAN September 2003）


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