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)分の一になるのだ。簡単に言えば、メチャクチャ楽になるのだ。サンタが一人では事実上サンタがプレゼントを配ることは不可能だけれど、複数犯であれば容易にプレゼントを配ることができるのだ。
このように「複数サンタクロース巡回問題」を考えることにより、サンタは複数いることが明らかだと私は思うのだ。
ただこれだけでは、不十分だ。全世界の子供達も年を経るに従って、爆発的に増えている。サンタが複数いるにしても、それでもやはり大変だ。サンタ達の人数も爆発的に増えていかなければ、とてもじゃないがやってられないことだろう。
それを解決する一つの答えはこうだ。「子供が増える割合に従って、サンタも増える」と考えるのだ。子供が一人増えると、サンタも一人増えるのだ。そうすれば、何の問題もない。子供が一人現れると、サンタも一人増えるのであれば何の問題もなくなる。
ところで、「子供が一人現れると、サンタも一人増え、サンタの数が子供と同じ比率で増えていく」ということは、子供たちがいずれサンタになるという考えが自然だとは思えないだろうか。そうだ、子供達がサンタになるのだ。子供達が大人になって、そしてサンタになるのだ。
もしかしたら、それはサンタという名前ではないのかもしれない。普段は他の名前で呼ばれているのかもしれない。けれど、クリスマスだけはサンタという名前になるのだ。電話ボックスで着替えるちょっと情けないスーパーマンのように、クリスマスイヴだけは彼らは変身するのだ。
こうして、サンタ達は子供の枕元にやってくる。むかし子供だったサンタ達が子供達の枕元にやってくる。そして、夢を見ている子供達が起きてしまわないように、そっと枕もとにプレゼントを置く。
サンタなんかこれまで私の枕元には来なかった、という人たちも多いのかもしれない。けれど、きっと、そんな人たちもまたサンタになっていくのだろう、そして、その時、本当にサンタがいる、ということに気づくのだろう。
」など。