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)分の一になるのだ。簡単に言えば、メチャクチャ楽になるのだ。サンタが一人では事実上サンタがプレゼントを配ることは不可能だけれど、複数犯であれば容易にプレゼントを配ることができるのだ。
このように「複数サンタクロース巡回問題」を考えることにより、サンタは複数いることが明らかだと私は思うのだ。
ただこれだけでは、不十分だ。全世界の子供達も年を経るに従って、爆発的に増えている。サンタが複数いるにしても、それでもやはり大変だ。サンタ達の人数も爆発的に増えていかなければ、とてもじゃないがやってられないことだろう。
それを解決する一つの答えはこうだ。「子供が増える割合に従って、サンタも増える」と考えるのだ。子供が一人増えると、サンタも一人増えるのだ。そうすれば、何の問題もない。子供が一人現れると、サンタも一人増えるのであれば何の問題もなくなる。
ところで、「子供が一人現れると、サンタも一人増え、サンタの数が子供と同じ比率で増えていく」ということは、子供たちがいずれサンタになるという考えが自然だとは思えないだろうか。そうだ、子供達がサンタになるのだ。子供達が大人になって、そしてサンタになるのだ。
もしかしたら、それはサンタという名前ではないのかもしれない。普段は他の名前で呼ばれているのかもしれない。けれど、クリスマスだけはサンタという名前になるのだ。電話ボックスで着替えるちょっと情けないスーパーマンのように、クリスマスイヴだけは彼らは変身するのだ。
こうして、サンタ達は子供の枕元にやってくる。むかし子供だったサンタ達が子供達の枕元にやってくる。そして、夢を見ている子供達が起きてしまわないように、そっと枕もとにプレゼントを置く。
サンタなんかこれまで私の枕元には来なかった、という人たちも多いのかもしれない。けれど、きっと、そんな人たちもまたサンタになっていくのだろう、そして、その時、本当にサンタがいる、ということに気づくのだろう。
2005-06-25[n年前へ]
■「遠くの景色」
たださんの日記の写真を眺めた。この写真の画角の少し外、右の外に私はかつて6年間住んでいた。写真の右後ろに見える「丸山」の頂上まで歩いて5分で行ける、そんな場所に住んでいた。「丸山」の頂上までは5分ぽっちなのに、ランドセルを背負って通っていた分校までは歩いて1時間かかる、そんな場所だった。信じてもらえないかもしれないけれど、小学校に入るまでは蒸気機関車が唯一の公共交通機関であるような、そんな場所だった。テレビはもちろん、NHKしか入らなかった。ガチャガチャとチャンネルを廻す必要なんかなくて、スイッチが一つあればいい、そんな場所だった。
山の下からほんの1, 2分で登ることができる丸山の頂上は、景色も良くてとても気持ちが良かったけれど、赤蟻の巣がところどころにあって、気をつけて寝ころばないと泣きたくなるくらいに痛く噛まれてしまうそんな場所だった。空は藍色のように蒼く、蒼くない空があるということを知ったのは、10歳の時に東京へ引っ越してからだった。冷たくない水道水がある、ということを知ったのも東京へ越してからだ。
きっと、今頃の高原野菜の出荷シーズンの畑の中や、その一帯で数軒しかない店先には、あの頃の同級生達がいるに違いない。他の学年と違って、1学級に「11人もいた」あのクラスの同級生達が何処かにいるに違いない。きっとあそこに今もいるんだ、と何故だかとても信じてみたいような気がする。そこにいなくても、きっとみんな何処かにいるんだ、と考えてみたいような気もする。
2007-07-08[n年前へ]
■「分業・神の見えざる手」と「ワットの復水器・調速機」
『国富論』を書き"経済学の父"と称されるアダム・スミスは、蒸気機関を広めたことで有名なジェームズ・ワットと親しかったという。その影響もあってか、経済成長と技術革新、つまり、経済成長とイノベーションの繋がりを強調していた。
スミスは蒸気機関の改良で有名なジェームズ・ワットのお友達なんです。 だから、スミス自身は蒸気機関を使った産業革命・機械化の時代に先駆けた時代の人ですが、技術革新こそが経済成長の源泉だというような内容のことをものすごく強調しています。 栗田啓子ジェームズ・ワットというエンジニアと、哲学者であり経済学者であるアダム・スミスの間にとても深い親交があって、影響を受けあっていたというのは、興味深い。現代の私たちを取り巻いている技術革新が経済成長を生み出しているという事実を、そんな親交からスミスが見いだしたというのは、とても面白い。
そして、きっとそれだけではない、とも思う。
ジェームズ・ワットを「蒸気機関を発明した人」と捉えている人も多いだろう。しかし、ワットは決して蒸気機関の発明者ではない。ワットは、すでに存在していた蒸気機関の効率を飛躍的に向上させることで、経済的に引き合う蒸気機関を作り上げた、という存在である。すでにあった複数の技術を上手く組み合わせることで、蒸気機関を効率よく安定に動かすことを可能にし、産業革命を支えたのである。
産業革命の中で育ったワットは、…1757年にアダム・スミスのはからいで、グラスゴー大学構内で実験器具製造・修理店を開業した。 ここでニューコメン型蒸気機関と出会い、より効率のよい蒸気機関を造るつくるため、熱と力の関係を研究する。 Wikipedia 「ジェームズ・ワット」ワットが生み出した「経済的に引き合う蒸気機関」の重要なポイントは、少なくとも二つあるように見える。その一つは蒸気機関への復水器を導入であり、もう一つは、蒸気機関に調速機を採用したことだ。（続く）
2007-07-09[n年前へ]
■続「分業・神の見えざる手」と「ワットの復水器・調速機」
ワットは「経済的に引き合う蒸気機関」を生み出した。その過程を辿ってみると、興味を惹かれることが二つある。一つは蒸気機関へ復水器を導入したことで、もう一が、調速機を備えるようにしたことだ。
シリンダという同じ場所で水の温度を上げ下げし、水を液体にしたり気体にすることで動力を得るのではなく、シリンダは常に高温に保ち、シリンダから離れて置かれた復水器で水蒸気を冷やしつつ、動力を得るように変えたことだ。同じ場所で、水の温度を上げ下げすることで水に体積変化をさせるのではなく、離れ異なる場所に温度差を設け続け、その間に水を循環させることで非常に効率良く動力を得る。それは、経済世界の「分業」を連想させる。人と人の間で、あるいは、国と国でも「分業」することで富が増大し、多くのものが生産される、というアダム・スミスの考えのようだ。ジェームズ・ワットの蒸気機関が備える復水器は、異なる場所を異なる状態に保ち続けることで、動力を得るまさにアダム・スミスの「分業」に見える。
そして、ワットが蒸気機関に採用した「調速機」はアダム・スミスが言及した「神の見えざる手」そのものである。
遠心調速機は回転する軸の回りのおもりが遠心力により外に振れることを利用する。蒸気機関の場合であれば、おもりの外への振れがシリンダーへ蒸気を導くバルブを閉じる方向に作用するようにしておく。出力が上がり回転が速くなるとおもりが振れ、バルブを閉じようとし、出力を抑える。出力が下がるとおもりが戻りバルブを開こうとし出力を上げる。 この逆方向の制御（負帰還）の微妙なバランスにより機関の出力を一定に保つ。機関に負荷がある場合でも作用するのでより正しくは出力よりも名前通り速度調整を行うものである。 Wikipedia 「調速機」蒸気機関の回転が速くなると、重りが繋がれた「手」が遠心力で上に上がる。遠心力で上がる手は、蒸気機関のバルブを少しだけ閉じる。そして、回転速度が元に戻る。そして、回転速度が低下すると、重りを持つ「手」に働く重力が遠心力に勝り、手が下がる。そして、蒸気機関のバルブを開く。そして、蒸気機関の回転速度は元に戻る。これは、まさに「神の見えざる手」である。遠心力と重力のバランスを原動力として、オーケストラをタクトで指揮する指揮者のように、蒸気機関の回転速度を制御する「調速機」、これはまさに経済活動を操る「神の見えざる手」である。「人々が自らの欲求と窮乏の追求することが、経済を発展させ富を生み出す」という、「見えざる手」と瓜二つに見える。
...he intends only his own security; and by directing that industry in such a manner as its produce may be of the greatest value, he intends only his own gain; and he is in this, as in many other cases, led by an invisible hand to promote an end which was no part of his intention. Wikipedia 「国富論」アダム・スミスがジェームズ・ワットから得たものは、「技術イノベーションの重要性」だけでなく、実は「分業」や「神の見えざる手」といったものへのインスピレーションや、それらを確信するバックグラウンドでもあったのかもしれない。そんな想像をしながら、経済学と工学を繋げてみるのも面白いかもしれない。
2007-07-10[n年前へ]
■ワットの調速機と「正義」
ワットが蒸気機関に採用した調速機、遠心力と重力のバランスを原動力にして、蒸気機関の回転速度を制御する「調速機」は、フィードバック制御の典型的なものだ。状況を見て、出力が低下しているようであれば、出力が上がるように「制御」して、出力が高すぎるようであれば、出力が下がるように介入する。このフィード・バック制御は「神の見えざる手」に似ていると同時に、「正義」にも似ている。
「義」、確か中国語で、足りない物を補う、という意味じゃなかったかな。義手とか義足とか それから考えると、正義という意味は、正しい事が足りない状況に於いて、「正しさを注入して不均衡を均衡に戻す」って事じゃないですかね？旅先をする水戸黄門が、困っている人たちの状況を見て、助さんと角さんをその状況へ介入させる。状況を見て、足りない物を補う、そんな黄門さま御一行の旅は、フィード・バック制御の毎日だ。
負のフィードバックが働く場合は、出力の増加が反応にブレーキをかけ、出力が低下すると反応は加速されるので、うまく働けば出力を一定に保つことができる。 Wikipedia フィードバック
」など。