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)分の一になるのだ。簡単に言えば、メチャクチャ楽になるのだ。サンタが一人では事実上サンタがプレゼントを配ることは不可能だけれど、複数犯であれば容易にプレゼントを配ることができるのだ。
このように「複数サンタクロース巡回問題」を考えることにより、サンタは複数いることが明らかだと私は思うのだ。
ただこれだけでは、不十分だ。全世界の子供達も年を経るに従って、爆発的に増えている。サンタが複数いるにしても、それでもやはり大変だ。サンタ達の人数も爆発的に増えていかなければ、とてもじゃないがやってられないことだろう。
それを解決する一つの答えはこうだ。「子供が増える割合に従って、サンタも増える」と考えるのだ。子供が一人増えると、サンタも一人増えるのだ。そうすれば、何の問題もない。子供が一人現れると、サンタも一人増えるのであれば何の問題もなくなる。
ところで、「子供が一人現れると、サンタも一人増え、サンタの数が子供と同じ比率で増えていく」ということは、子供たちがいずれサンタになるという考えが自然だとは思えないだろうか。そうだ、子供達がサンタになるのだ。子供達が大人になって、そしてサンタになるのだ。
もしかしたら、それはサンタという名前ではないのかもしれない。普段は他の名前で呼ばれているのかもしれない。けれど、クリスマスだけはサンタという名前になるのだ。電話ボックスで着替えるちょっと情けないスーパーマンのように、クリスマスイヴだけは彼らは変身するのだ。
こうして、サンタ達は子供の枕元にやってくる。むかし子供だったサンタ達が子供達の枕元にやってくる。そして、夢を見ている子供達が起きてしまわないように、そっと枕もとにプレゼントを置く。
サンタなんかこれまで私の枕元には来なかった、という人たちも多いのかもしれない。けれど、きっと、そんな人たちもまたサンタになっていくのだろう、そして、その時、本当にサンタがいる、ということに気づくのだろう。
2002-06-03[n年前へ]
■カードサイズの「画像探偵セット」!?
お手軽線数メーターを作るのだ
「どんなものでも、自分の目で眺めてみた〜い」と、ワタシはいつでも思う。世の中スベテのものを、自分の目で眺めてみた〜いと思う。しょんべん小僧が空中に描き出す放物線、巨乳ギャルにロックオンするオッパイ星人の目の動き、ビデオにかかるモザイクの向こう、はたまた田代まさしが恋い焦がれるミニスカートの結界の秘密、とにかく世の中のものスベテを何でもかんでも眺めてみたい、覗いてみたい、とワタシはいつも思っているのである。（とはいえ、誤解されると困るので念のために書いておくが、もちろんミニスカートの中を覗いたりはしないのだ）
そんなわけで、ワタシのケータイのストラップには「ちっちゃなちっちゃな虫メガネ」がついている。この虫メガネを武器にして、ワタシは色んなモノを覗くのがクセになっている。スーツ姿で出張している時だって、おもむろにこの虫眼鏡を取り出して、色んなものを覗いてみたりしているのである。
 |
だから、毎朝届けられる新聞に折り込まれているチラシやカタログを眺めるときだって、そんなカタログに「ちっちゃなちっちゃな虫メガネ」を向けてみて、その「虫メガネ」を通して、カタログがどんな風に印刷されているかをよく眺めてみる。下の左のようなカラーの綺麗なカタログだって、「虫メガネ」を通して眺めてみると、右の拡大写真みたいに、四色（シアン、マゼンダ、イエロー、ブラック）が規則正しく並んでいるようすが見えてくるのである。離れてみればキレイな写真が「虫メガネ」を通して眺めてみるだけで、こんな風に様子が変わるなんてとても不思議な気分になったりするのである。まるで、女性の化粧のように不思議で、こんな四色の手品はとても面白いのである。
| （左上と右上部分はマゼンダとシアンだけを見やすくしてみた）
|
で、こんなカタログの拡大図を眺めていると、四色に分けられた色がどんな風に並べられ形作られているかを、知りたくてたまらなくなったりする。つまり、「どんな間隔でこの色は配置されているのだろう？」とか「一体、どんな角度でこの色は並べられているのだろう？」とか思うわけである。もちろん、この画像に二次元フーリエ変換などをかけさえすれば（周波数解析をすれば）、「どんな角度で・どんな間隔で色が並べられているか」ということは知ることができるけれど、まさかワタシの頭の中でそんな作業ができるわけはない。かといって、このカタログを読み込むための「画像読みとり装置」や「解析をするためのコンピューター」を毎日持ち歩くなんてこともできるわけもない。
そこで、「どんな間隔でこの色は配置されているのだろう？」とか「一体、どんな角度でこの色は並べられているのだろう？」とかいう疑問の答えがすぐ判るように、先日こんなカード、ぴったりクレジットカードサイズの透明シートに規則的なパターンを印刷したカード、を作ってみた。名付けて、Peco-Chartなのである。
これはもちろん、判る人には判るだろうが、ハンディ「線数メーター」というモノである。一言で言えば、画像の周波数解析をとっても簡単にすることができる手品の小道具のようなカードなのだ。
 |
例えば、さっきのカタログの上にこのPeco-Chartを重ねて置いてみると、アラ不思議、何やらヘンな模様、不思議なモアレ模様が浮かび上がってくる。下の左の写真、あるいは右の拡大写真を眺めてみればマゼンダとシアンの同心円がハッキリと浮かび上がっているのが見えるだろう。例えば、シアン色の場合は75°の角度で175線（175線/inch）位の位置、そしてマゼンダ色の場合は45°の角度で同じく175線位の位置を中心として、同心円状のモアレ模様が浮かび上がっている。
つまり、「このカタログはシアンは75°の角度方向に1インチ辺り175個のドットが並べられていて、マゼンダのドットは45°の角度方向に並べられている」、ということを、このPeco-Chartを重ねて置いてみさえすればたちどころに知ることができるのである。
 |  |
 |
こんなペラペラのカードで周波数解析ができるなんてとても不思議に思えたりもするけれど、ちょっと考えてみればこれはごく当たり前の話である。
でも似たようなことをしたように、モアレというものは「二種類以上の何らかの模様（パターン）が干渉して発生する」ものである。つまり、ある意味「二つのパターンの相関をとる」ということである。そしてまた、少し考えてみれば「画像の周波数解析」というものは「対象となる画像」と「基準関数（三角関数etc.）」の間で相関を調べることと同じである。だから、「基準となるパターン」を「対象となる画像」の上に重ねてみた時に見えるモアレのパターンは「対象となる画像」の周波数解析結果を実は示していると考えてみても良いのである。だから、このPeco-Chartはクレジットカードサイズのペラペラなちっぽけなヤツではあるのだけれど、実は色んな画像の周波数解析をしてくれるスゴイヤツだったのである。そして、こんなポケットに入るほど小さい線数メーターははなかなか無いので、、カード入れからコイツを華麗に取り出してみせたりすると、うらやましがる人もとても多く（仕事柄、画像出力に関わる人達が多いから）、なかなかに気持ちが良いのである。 とはいえ、自慢してばかりでは何なので、さらに大量に配布すべく新たなPeco-Chart二号機をデザインしてみた。それが、下の名付けてPecochartproである。
 |
このPecochartproの謳い文句はその名の通り「プロ仕様」というわけで、画像出力に関わっている何人ものベータテスター達（自分も含めて）の感想をもとにして、
- 70線から350線までの線数とスクリーン角度の測定ができる「線数・角度メーター」（分解能を2線単位から1線単位へと二倍向上、スクリーン角度のガイドは2.5度刻み）
- 90線から410線までの線数を高精度（0.25線刻み）に計測することができる「線数メーター」（新機能）
- 線・文字の太さを計測できる「線幅スケール」（新機能）
- 〜30級、〜30ポイントまでの文字サイズ（級数、ポイント）測定ができる「文字スケール」（Peco-Chartと同じ）
- 「8cm定規」（Peco-Chartと同じものを使い勝手はそのままにコンパクト化）
- そして、便利な「画像に関する換算表」（内容を従来比75%増量）
それにしても、何か自分に役に立つツールを作るというのは本当に楽しい作業だった。手作りツールぎゃらりい脇色彩研究所ではないけれど、こんな「hirax.netオリジナルグッズ」をいっぱい作って「探偵セット」ならぬ「できるかな?セット」として、面白メールをくれた方にプレゼントとかしてみたら楽しいんだろうなぁ、と思うのである。というわけで、そんなツールをせっせと作るのだぁ、なんてことを実は計画中なのでした、ハイ。
2002-06-24[n年前へ]
■明日からプレゼン研修
明日から三日間のプレゼン研修。なので、その宿題用のプレゼン資料を作った。ほぼ五分間のビデオ。三時間くらいかかった…。目が回りそうな一日だー。
で、明日からの研修はTechnical Presentation研修ではないし、おそらくビデオ報告時の私のスタイル(自称CNNスタイル)にそのまま導入できることは少ない、と思うけれどきっと基礎体力向上に役に立つハズ…。
2002-06-25[n年前へ]
■Regular Presentation研修一日目
朝はまずいきなりプレゼン一回。カメラが二台回ってる。受講メンバーで開発系は私だけ。とりあえず、一個目のプレゼンはよくやる自分のスタイルでという指定なので、試しにCNNスタイルで。講師も含めて目が点なのだ。
2002-06-26[n年前へ]
■Regular Presentation研修二日目
朝、漫談のように口だけでのプレゼン（資料は昨日作成…しんどかった…）。夕方は三日目の朝用のプレゼン資料作成…。うむむ…、ハードだ…。
英語だけの三日間というのもしんどいかと思ったが、しんどいのはそういうところじゃないなこりゃ。
」など。