みんなが幸せになる町づくり：日経サイエンス

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

HOME ＞パズリング・アドベンチャー＞みんなが幸せになる町づくり

ご購入のご案内

検索方法はこちら

サイト内検索結果に戻る

みんなが幸せになる町づくり

デニス・シャシャ

　鉄道の貨物駅の隣に住みたいと思う人はまずいないだろうが，スーパーまで歩いて行かれる所なら多くの人が住みたいと思うだろう。一方，スーパーは倉庫の隣でも気にならないだろうし，倉庫会社の経営者は近くに貨物駅がある場所を望むだろう。近所にあって好都合なもの・不都合なものは立場によって違う。今月のパズルではこれを数学的に解析して，みんなの満足度を高める都市計画を考えよう。

GARY ZAMCHICK

　問題を単純にするために，いま考えている仮想的な町を格子で区切られたセルで表現する。各セルには，そこの住人のタイプ（一般住宅，輸送業など）を表す数を入れる。あるセルとその隣接セルとの間で「幸福関係」を定義し，さらにすべての隣接セルとの幸福関係の和を「幸福度」とする（隣接セルは上下左右だけで，斜めは考えない）。
　隣接セル間の幸福関係は，以下のようにする。相手のセルの数値と自分の数値が１だけ離れているときに１とする。また，相手と自分が同じか，差が２のときには０とする。相手と３以上離れているときは不幸な住環境なので，幸福関係は－１とする（訳注：幸福関係は，相手から見ても同じ値になることに注意）。もし，隣接セルとの間の幸福関係がすべて正ならば，そのセルに対して「完璧な区画分け」ができたと見なす。

　たとえばタイプ６のセルが，４辺をタイプ５や７のセルで囲まれているときには，その幸福度は４となる。右図で，回りを囲まれている６のセルは，上下の６や８との間では幸福関係が得られず，左の７からは＋１が，右の３からは－１が得られる。その結果，このセルの幸福度は１＋(－１)＝０となる。

ウォーミングアップ問題

　３×３の格子にタイプ１～９のセルが１つずつ入っている町を考えよう。町全体の幸福度を最大にするには，各タイプのセルをどう配置したらよいだろうか。

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

左のように配置すると，町全体として最大の幸福度８が達成できる。

今月の問題：いずれも６×６の格子で考えてもらいたい。

問１：36個のセルに，２つのサイコロを振ったときの目の和の分布と同じように数が入っている（２と12が１カ所，３と11が２カ所，４と10が３カ所，５と９が４カ所，６と８が５カ所，７が６カ所）。これを６×６の形にうまく配置して，どのセルに対しても，そのすべての隣接セルとの間で正の幸福関係を持つようにできるだろうか。つまり，すべてのセルに対して完璧な区画分けができるかということだ。それが無理ならば，どこまで完璧に近づけられるだろうか。

問２：すべてのセルに１から36までの数を１個ずつ入れる場合，どのセルの幸福度も負にならないように配置することができるだろうか。

問３：すべてのセルに１から36までの数を１個ずつ入れる場合，どのセルに対しても，すべての隣接セルとの間の幸福関係が負にならないような配置はあるだろうか（これは前問よりも厳しい条件になる）。

問４：すべてのセルに１から36までの数を１個ずつ入れる場合，全セルの幸福度の合計の最大値は，私の知る限り20だ。この値をさらに大きくすることはできるだろうか？

　このパズルの設定をより現実に近づけて，町やセルの形，住民のタイプ，タイプ間の好都合・不都合の判定基準などを一般化すれば，問題を解く素晴らしいアルゴリズムを編み出すことができるかもしれない。もしそれが完成したら，あなたのアルゴリズムを使わせてほしいと言う市町村が出てくることは確実だ。

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

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

	Dennis E. Shasha

	ニューヨーク大学クーラント研究所教授。専門は計算機科学。　原題名 Perfect Zoning （SCIENTIFIC AMERICANのウェブサイト http://www.sciam.com/より）


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