密輸品を追え：日経サイエンス

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

HOME ＞パズリング・アドベンチャー＞密輸品を追え

ご購入のご案内

検索方法はこちら

サイト内検索結果に戻る

密輸品を追え

デニス･シャシャ

　いくつかの敵対国の間で危険な物資の密輸が行われている。偵察衛星が暴いたコンテナの数をもとに，どの国からどの国へ，いくつのコンテナが運ばれたのかを知りたい。密輸品のコンテナは，出発国を船出したあと，少なくとも1つの中立港を経由する。港では，コンテナはいったん倉庫に入れられ，その中で行き先別にまとめられて船積みされる。したがって，個々のコンテナを出発国から目的国までずっと追跡することはできない。しかし，各行程で船に積まれたコンテナの数は偵察衛星が教えてくれる。さらに，すべてのコンテナは目的地まで最短経路をとることがわかっている。

　ウオーミングアップ問題として，下のチャート図を考えてみよう。

　矢印の横にある数字はA，B，C国と中央にある中立港との間を行き来したコンテナの個数だ。中立港からB国へ運ばれたコンテナはないので，C国を出たコンテナはすべてA国に行ったと推測できる（最短経路を通ることから，出発国には戻らない）。中立港からA国に行ったコンテナは2個だけなので，B国からの2個のコンテナは，中立港でA国から来た3個のコンテナと一緒にされてC国に行ったに違いない。

　さて，5つの国と3つの中立港からなる場合を考えよう。A国からD国に運ばれた可能性のあるコンテナ数の最大値と最小値はいくつか（舳先の数字がコンテナの数だ）。A国からE国の場合はどうか。

※画像をクリックしていただくと大きな画像がご覧になれます

　次に，運ばれたコンテナの数が下のチャート図のようになった場合，この最大値と最小値はどう変わるだろうか？

	山崎秀記（やまさき・ひでき）

	一橋大学商学部教授。専門は計算機科学。

	Dennis E. Shasha

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


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