2001-12-24[n年前へ]
■サンタが街にやってくる 
複数サンタクロースの巡回問題
簡易に書き直した2011年版もあります。
幼い頃、クリスマスの夜を清里の聖ルカ教会で過ごしたことがある。今では、「アイスクリーム」で有名になってしまった聖ルカ診療所の隣の教会だ。清里を通る小海線が蒸気機関車からディーゼル列車に切り替わった頃だった。私の住んでいた野辺山から一番近い病院がその聖ルカ診療所だった。今はどうなのか判らないけれど、あの病院の中の風景はまるで高原の療養所のようで（高原の診療所なのだから大して違いはないのだけれど）、とても不思議だった。
さて、クリスマスの人気者と言えば、やはりサンタクロースである。世界中の子供達から待ち焦がれられ、プレゼントを配って歩くのだから、クリスマスイヴのサンタは大忙しなのである。一体、サンタクロースはどんな風にプレゼントを配って歩くのだろう、と思った私は「サンタクロースの巡回問題」について考察をしてみることにした。
知らない人のために書いておくと、「巡回サンタクロース問題（TSP:TravelingSanta Problem)」というのは「巡回セールスマン問題(TSP:Traveling SalesmanProblem)」の特殊例である。そもそも「巡回セールスマン問題」というのは「n人の顧客の場所が与えられたとき、全ての顧客を一回ずつ経由して巡回する際に、移動距離が最小になる経路を求める。」という問題である。計算幾何分野で最もメジャーな話であって、カーマーカー特許などこれに関係するものである。つまりは、色々なものを配達する際には「配達経路を考えるのは実は結構大変なのだ」という問題なのである。
これまで「巡回サンタクロース問題」を考えた人がいなかったか、と言うとそんなことはなくて、試しにinfoseekで"サンタ"AND"巡回"で検索すると、既に素晴らしい研究がなされている。それが
- サンタクロース研究
- ( http://www.geocities.co.jp/HeartLand-Suzuran/5872/santa.html )
そこで、そんなこれまでの「巡回サンタクロース問題」に関する研究を踏まえながら、「できるかな?」ではさらに「サンタクロース巡回問題」を考え、そして、できることであればサンタの隠された真実にさらに迫ってみようと思う。「サンタクロース巡回問題」の中には、サンタクロースの真実に近づく鍵が含まれている、と私は何故か感じるのである。
まず、始めに問題提起をしてみよう。
「果たしてサンタは一人なのか？」
どのような事件においても(別に事件ではないが)、単独犯か複数犯かというのはとても重要な問題である。犯人が単独犯か複数犯かで証拠の指し示す意味は異なってくる。サンタは一人、と私たちは何故か思い込んでいるが、そんな先入観は正しい捜査のたまには捨てる必要がある。
そこで、まずはサンタの歴史から調べてみると、Ｓａｎｔａさんの起源、クリスマスページ!によれば、サンタクロースの起源であるSt.Nicolausは西暦4世紀頃の人であるという。その頃の人口は現在よりもはるかに少なかった。それは、サンタの労働量がはるかに少なかったということだ。なるほど、この時代であれば、サンタは一人でも不思議ではないかもしれない。
とはいえ、Ｓａｎｔａさんの起源の中の色々なサンタの目撃情報を見ると、本当にサンタは一人なのか疑問を感じるのもまた確かである。色々なサンタが目撃されている、ということはサンタは実は複数犯の可能性が高いのではないだろうか？
また、世界の人口は人口増加に示されている全世界の人口増加の様子を見れば明らかなように爆発的に増えている。ちなみに、そこに示されているグラフを対数軸にし、近似式を加えたものが以下である。
 |
St.Nicolausのいた西暦4世紀頃に比べて現在の人口は4桁、すなわち、10000倍に増えている(近似式によれば。ホントのところは知らない)。これでは、サンタクロースは年々仕事量が驚異的に増えていることを意味する。もし、サンタが単独犯であるとするならば、過労死はまぬがれそうにない。
サンタの単独犯説に対する疑問は「サンタクロース巡回問題」からも示される。N人の顧客(今回の例ではN人の良い子供)が与えられたとき、サンタが計算しなければならない経路の総数は(N-1)!/2で与えられる。2で割っているのは「対称巡回サンタクロース問題(A家からB家間での距離と、B家からA家間での距離が同じという性質がある場合)」であるからだ。
子供の家N=100までの場合の、サンタが計算しなければならない経路の総数(N-1)!/2を以下に示してみる。
 |
どうだろうか、Nが少し増えると爆発的にサンタが計算しなければならない経路の総数(N-1)!/2が増えていくのがわかると思う。一軒多くなるだけで、ものスゴイ数の計算をしなければならなくなるのである。サンタが実際に配達して回るのも大変だが、その前に配達経路を決める計算量は実はもっと大変なのである。
先の人口増加の割合をこれに加えるならば、「サンタが計算しなければならない経路の総数」は天文学的数字になることは明白である。
そこで、私はやはりサンタ複数犯説が真実に近いと思うのである。サンタ複数犯説が正しいとするならば、ッ実はこの「サンタクロース巡回問題」は遥かに容易に解くことができるようになるのである。
それでは、複数サンタがいるときの「サンタクロース巡回問題」を考えてみよう。サンタが複数のm人いる場合を考える≠ニA「サンタが計算しなければならない経路の総数」はm*(N/m-1)!/2で示される。
一例として、サンタが1,2,10人の場合を示してみる。
 |
このグラフからサンタが複数いる場合と、単独の場合とで巡回経路を考える手間が全然違うのがわかるだろう。サンタが2人いると、計算量は半分になるのではなく、ものすごく少なくなるのである。
実際の巡回においての仕事量は、サンタがm人いれば1/mになる。しかし、その前準備はサンタがm人いれば((N-1)!/2)/(m*(N/m-1)!/2)分の一になるのだ。簡単に言えば、メチャクチャ楽になるのだ。サンタが一人では事実上サンタがプレゼントを配ることは不可能だけれど、複数犯であれば容易にプレゼントを配ることができるのだ。
このように「複数サンタクロース巡回問題」を考えることにより、サンタは複数いることが明らかだと私は思うのだ。
ただこれだけでは、不十分だ。全世界の子供達も年を経るに従って、爆発的に増えている。サンタが複数いるにしても、それでもやはり大変だ。サンタ達の人数も爆発的に増えていかなければ、とてもじゃないがやってられないことだろう。
それを解決する一つの答えはこうだ。「子供が増える割合に従って、サンタも増える」と考えるのだ。子供が一人増えると、サンタも一人増えるのだ。そうすれば、何の問題もない。子供が一人現れると、サンタも一人増えるのであれば何の問題もなくなる。
ところで、「子供が一人現れると、サンタも一人増え、サンタの数が子供と同じ比率で増えていく」ということは、子供たちがいずれサンタになるという考えが自然だとは思えないだろうか。そうだ、子供達がサンタになるのだ。子供達が大人になって、そしてサンタになるのだ。
もしかしたら、それはサンタという名前ではないのかもしれない。普段は他の名前で呼ばれているのかもしれない。けれど、クリスマスだけはサンタという名前になるのだ。電話ボックスで着替えるちょっと情けないスーパーマンのように、クリスマスイヴだけは彼らは変身するのだ。
こうして、サンタ達は子供の枕元にやってくる。むかし子供だったサンタ達が子供達の枕元にやってくる。そして、夢を見ている子供達が起きてしまわないように、そっと枕もとにプレゼントを置く。
サンタなんかこれまで私の枕元には来なかった、という人たちも多いのかもしれない。けれど、きっと、そんな人たちもまたサンタになっていくのだろう、そして、その時、本当にサンタがいる、ということに気づくのだろう。
2004-12-23[n年前へ]
■化学の本だな / サンタが街にやってくる
明後日はクリスマス。だから、明日はクリスマスイヴ。「化学の本だな のインタビュー記事」にも書かれた通り、「できるかな?」の話の中で一番好きで、一番意外な結果だったのが「サンタが街にやってくる- 複数サンタクロースの巡回問題 -」です。だから、この話が二冊目の本の中に選ばれなかったのは(私にとっては)少し意外に思った覚えがあります。 from 思い出したきっかけは YAMDAS現更新履歴
2008-10-11[n年前へ]
■自分で作る「問題」と「答え」
以前、月刊化学5月号の【化学の本だな】でこんな内容のことを答えました。これ以外の場でも、同じようなことを数度聞かれますが、いつも同じようなことと答えたように思います。
Q: 調べていて，意外な結論が導きだされたりすることはあるのですか？
A: いいえ、結論（オチ）まで考えてから実際の計算や 実験に取りかかるので，意外な答えに至ることはありません。ただ、一回だけ、「意外な答え」に気づき驚いたことがあります。それは、「サンタが街にやってくる」という話です．数字上の答えは当初の設定そのものでしたが，そこから導きだされた本当の「サンタの正体」は，とても意外なほどに素敵なものでした。
サンタというものの正体、あるいは、サンタに変身する人を突き動かすものの正体、そんなものに気づかされたように思ったときには、自分が考えもしなかった「答え」を見つけたような気がしました。
いつか、科学童話本を書いてみたい、と思っています。 私と二度めに出会う「水」 / サンタが街にやってくる / あなたと見たい、流星群 / 遠い空のはて？ / 七夕の夜に願うこと / 「雪だるま」がいる景色 / あの頃流れた電波の行方 / 街の灯 (City Light) / 14ミリグラムの「いろんな気持ち」 / 「夕焼けこやけ」の茜蜻蛉（あかとんぼ) / 「海面に写る太陽」の不思議 .... そんな小文や日記の中で少し真面目に書いたことを集めて、科学童話本をつくることができたらいいなぁ、と思うのです。
2009-12-18[n年前へ]
■論理の先にある非論理的なサンタの正体
時間をかけ、目に見えて役立つように見えるわけでもない文章をただ書き続ける、ということがなかなかできません。以前は、「できるかな?」と題して、そういうことができていたような気がしますが、最近は「技術の話、けれど、技術だけでもない話」というものを書くことができていないように思います。けれど、そういうことを、また再開していこう、と考えています。
「できるかな？」では、（特に初期以外の時期は）「技術的な計算をしていくと、その計算結果を通して（何らかの）「オチ」にたどり着き、話が終わる」ということを意識して書いていました。それはなぜかというと、「○×が良ければ良いほど、△□は良い」といったような、何かの特異点や境目がないような話、つまりオチ（境目）のないは、何だかつまらない当たり前の技術問題に過ぎないように思えたからです。
逆に言うと、その「技術が解き明かすオチ」を思いついてから（ある程度そうなるだろうと確信してから）、初めて計算を始め・文章にまとめていました。それは、少し研究・論文書き、といったことと似ているのかもしれせん。
だから、時に、（たとえば月刊化学でされたような）こんな質問をされても、
Q: 調べていて，意外な結論が導きだされたりすることはあるのですか？いつも、こんな感じの答えをしていました。
A: いいえ、結論（オチ）まで考えてから実際の計算や 実験に取りかかるので，意外な答えに至ることはありません。ただ、一回だけ、「意外な答え」に気づき驚いたことがあります。それは、「サンタが街にやってくる」という話です．
クリスマスシーズンが近づいてきました。だから、もう一度この「サンタが街にやってくる」という話を、ここに挙げておこうと思います。「できるかな？」の内容は3度ほど書籍化されていますが、この話は、一番最初に出版された幻の本「できるかな?―うれしはずかし無敵の科学 (ホームページ・ブックス)
最初は少し数学的な話から入りますが、その論理的な計算から導き出される答えは、実に非論理的な「答え」です。けれど、それが私が一番心で納得できた「答え」です。だから、数学部分を乗り越えて、最後まで読んで欲しいと願います。
ちなみに、、「サンタが街にやってくる」では珍しくBGMをつけてあります。静かに読みたい方は、消音ボタンを押してから、リンクをクリックして頂ければ、幸いです。
2009-12-21[n年前へ]
■続 「サンタが街にやってくる」
自分が間違えて使っていたことを、「それは間違っているよ」と指摘して頂くのは本当にありがたいことです。
サンタのオチは秀逸だと思います。でも、「犯」とは呼ばないと思います。新明解辞書で、「犯」という言葉をひきました。すると、こんなような言葉が出てきました。
犯す＝そうすれば当然罰せられることをするあぁ、本当に仰られる通りなんですね。「犯」ではないですね。言葉を考え直します。心から、感謝させて頂きます。
」など。