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-01-13[n年前へ]
■画像とテキストの両面から文書を検索できる新技術
そういえば、富士ゼロックスの「名前忘れた」はどうなったのでしょうか？（リンク）
2002-03-06[n年前へ]
■紙飛行機に乗ってた人達
Fair is foul, foul is fair II
先日、hirax.netの検索エンジン「ぐるぐる」宛にこんなメールが届いた。
私たちが折り紙を覚えるとき、一番最初に折ってみたのは紙飛行機だった気がします。もしかしたら、私だけでなくて多くの人たちもそうであるのかもしれません。そこでふとこんな疑問が浮かびました。よく、時代劇で折鶴、紙風船がでてくることがあるのに、なぜ紙飛行機は出てこないのでしょうか？折り方は一番簡単なのに…。この答えを探しに行った「ぐるぐる」はまだ帰ってこない。きっと何処かで「紙ひこうきの歴史」を調べているところなのだろう。あるいは、何処かで道草でもしているのかもしれない。
昔は、飛ばして遊ぶ折り紙はなかったのでしょうか？もしそんなものが何かあったとしたら、それを一体なんと呼んでいたのでしょうか。折り方でいちばん簡単な三角翼、いわゆるジェット機に似た形のものが有ったとしたら、それを何と呼んでいたのでしょうか？
きっといつか「ぐるぐる」も戻ってきて、上の検索結果も判るとは思うのだけれど、今回はこのメールで思い出した「ある紙飛行機に乗ってた人達」の話をメモしておこうと思う。それは、昔から語り継がれているらしい少し不思議な紙飛行機の話である。
先日、スキーに行った帰りの車中で、私の会社の先輩にあたる人が「この話は二十年くらい前に大学の先輩から聞いた」と言って、私達にこんな話をし始めた。
「これは不幸にも墜落した紙飛行機に乗っていた人達の話です」と言って、ある人が聞き手の前でこんな風に紙飛行機を折っていく。
 |  |  |
 |  |  |
よくある紙飛行機ができあがる |  |
そして、話し手は、「ある日、この飛行機に過酷な運命が訪れる。その飛行機は、いつもと同じように乗客を乗せて、いつもと同じように飛行場を飛び立った。しかし、この飛行機は不幸にも翼の自由を奪われてしまう」と言いながら飛行機の翼を折り畳む。そしてさらに、「翼の自由を奪われたこの飛行機は何処かの場所に激突してしまう。紙飛行機には多くの乗客が乗っていたが、その人達を乗せたまま紙飛行機は真っ二つに割れてしまった…」とゆっくりと語り、その飛行機の胴体を二つに切ってしまう。
胴体を真っ二つに切断する  |
次に、話し手は「そしてこの不幸な飛行機の胴体は、紙飛行機に乗っていた人達と共にバラバラに散らばってしまった…」と言って、紙飛行機のカケラを散らばらせる。目の前で、全部で九つある紙のカケラはバラバラになっていく。
そして、その散らばったカケラの中の一番大きな一つを拾い、折り畳まれたカケラをゆっくりと開きながら、「飛行機に乗っていたほとんどの人は天国に行った」と呟く。すると、確かに話し手の掌の中で拡げられていく紙のカケラは、いつの間にか十字架の形に変わっていく。
 |
そして、まだ目の前に散らばっている残りの八つのカケラを話し手は拾い、それをゆっくりと並べながら「残りの罪ある悪しき人々は地獄へ行く」と話す。すると、その言葉のままに、残りの紙飛行機のカケラはいつの間にか姿を変えて"HELL"という文字に変わっていくのである。
 |
そして、最後には話し手と聞き手の間には、紙飛行機が姿形を変えた「十字架と地獄」だけが残り、「紙飛行機に乗ってた人達」は「善き人々と悪しき人々」に分けられて「天国と地獄」へそれぞれ別れていく、という話なのである。
 |
この話を聞いたときに、その「一見普通に見える」紙飛行機がバラバラになって、そしてそのカケラを並べ直すといつの間にか「十字架の形」と「"HELL"という言葉」に形を変えるなんて、とても不思議で少し不吉な話だなぁと小心者の私は思った。
そして、この話がどんな風に作られて、どんな風に語られているかを知りたくなった私は、この話に関連しそうな話を探してWEBサイトを辿ってみた。すると、キリスト教の説法の一つとして、この「十字架と地獄」という話をいくつもWEB上で見かけることができた。そのほぼ全ては「天国と地獄」「十字架と地獄」といった「善と悪」の話だった。また、その話は「天国へのチケット」という風に、もとの形が飛行機でないものも多かった。
そして、さらにいくつかの情報源を辿っていると、他とは少し変わった終わり方の話を見かけた。その話の中でも、全部で九つの紙のカケラの内の一つはやはり十字架になり、「飛行機に乗っていたほとんどの人は天国に行く」というところまでは他の話と全く同じだった。しかし、その話の中では残りの小さな八つのカケラが形作る文字が"HELL"という文字ではないのだった。
 |
その残りの八つのカケラは並べ直すと、姿を変えてこんな風に"LOVE"という文字を綴るのである。そして、語り手はその文字を指しながら「残りの敬虔な人々も深い愛で包まれる」と終わるのだった。この形で終わる話を眺めて、ようやく、この「紙飛行機に乗っていた人達」の話は「とても不思議で少し不吉な話」から「とても不思議な話」だと私は思えるようになったのである。
紙飛行機が何処かに激突して二つに分かれてしまう。ある人が語る話の中では「紙飛行機に乗ってた人達」は「善き人々と悪しき人々」に分けられて「天国と地獄」へそれぞれ別れていくと語られる。そして、また違う人は「紙飛行機に乗ってた人達」は「飛行機に乗っていたほとんどの人は天国に行き」「残りの敬虔な人々も深い愛で包まれる」と語られる。同じカケラが、語り手次第で「地獄へ行く罪ある悪しき人々は」だったり、「深い愛に包まれる敬虔な人々」だったりする。
マクベスの冒頭の"Fair is foul, foul is fair."という言葉ではないけれど、何が善で何が悪かはほんの少しの視点の違い次第だ。それはもちろん、この八枚の紙のカケラに限らない。
2002-03-24[n年前へ]
■パズルのカケラ
ジグゾーパズル的プラグインを作る
hirax.netが誇る超手動検索エンジンぐるぐる（旅に出たっきり戻ってこないが）宛に、先日こんな依頼が届いた。大きな写真を20ピクセル四方くらいで分割して、それをタイルのように並び替えてくれて、分割したカケラを自分であとで自由に移動できたり、個別に画像調整もできて…、そんなPhotoshopのプラグインが欲しいので探して下さい。 もしなかったら、作ってくれてもいいです。今回のような、こんな具体的な依頼であれば、何を探したら良いか実にわかりやすい。よくある「ぐるぐる宛のメッセージ」はあまりに短くて、何を探したら良いのかぐるぐるが困ることも多い。何しろ、「愛」とか「幸せ」とか一言で言われても超手動なので困ってしまうのである。「愛」や「幸せ」を探してくれって言われても、そんなのこっちが知りたいつーのー、ってこぼしたくなるのである。まれに「バスト90cmでDカップ超の巨乳」というような超具体的な検索キーワードが送られてくることもあるのだけれど、そんなこと言われてもなー、とぐるぐるは頭を抱えるばかりなのである。
それはさておき、今回の依頼も実に判りやすいのだが、もしなかったら作ってくれてもいいです、とは優しい口調でとんでもない依頼だ。いや、実際のところ依頼というよりほとんど命令である。人を（いや違った、ぐるぐるを）ドラえもんか何かと間違えているんじゃないかー、と聞き返したくなったりするのである。
しかし、これまで「できるかな?」では「たくさんのカケラを並べて、一枚の絵にするモザイク」で遊んでみることが多かったが、そんなこれまでとは逆のアプローチ、「一枚の絵をたくさんのカケラにばらばらにしてみる」という、まるで一枚の絵をジグゾーパズルのピースに分解してしまうような遊びをしてみるのも面白いかも、ともふと思った。そこで、今回はこの依頼に応えてそんなPhotoshopのジグゾーパズル的プラグインを作ってみることにした。名付けて、Midinette(= 女性店員,、針子さん)プラグインである。「糸のこで切り抜いたパズル」はJjigsawpuzzleだけれど、そんなジグゾーパズルを切り張りしたり繋げあわせたりする賢い女性店員・針子さんという気持ちを込めてみた。
さて、普通なら、Photoshopのプラグインと言えば、普通はフィルター・プラグインなのだろうけれど、今回は「分割したカケラを後で動かしたい」という注文がついているので、アクション・プラグイン（通常のアクションではなくて、あくまでもプラグイン）で適当にちょちょいと作ってみることにした。まずは、このプラグインを使った場合のサンプル画像を下に示してみる。
 |  |
アクションプラグインはPhotoshop5.0以降に導入されたものであるが、今回のプラグインは6.0以降の機能も使っているので、Photoshop56.0以降が動作環境となる。また、Windows2000でしか動作チェックしていないので、もしかしたらその他の環境では動かない場合があるかもしれない。その場合はその旨知らせてもらえれば、コンパイルし直したものを作る予定だ。で、いつもと同じようにアルファ版のものをここに置いておく。これをPhotoshopのPlug-Insディレクトリに置けば、ファイル→自動作業からMidinetteが使えるようになる。
- Midinette.lzh ( 29kB )
この手のジグゾーパズル系のプラグインとしては他にAVBros. Puzzle Proなどがあるが、ピースの形状の自然さはともかく、各ピースを(それぞれレイヤーに変換することで)自由に後で動かすことができるという点で今回のこのプラグインは面白いのではないか、と思う。
ちなみに、下の画面がMidinetteのダイアログである。現時点で設定可能なパラメータの内容は
- Horizontal Division : 横方向の分割数
- Vertical Division : 縦方向の分割数
- Inclination :長方形からの変形量 (3〜5)
- JigsawPuzzle : 丸い突起部の大きさ(6〜7)
- Scattering : ピースをバラバラにするかどうか
- LayerEffects : ピースの立体効果をつけるかどうか
 |
パラメータを変えると、ピースの形がある程度変えられるので例えば、こんな風にもなる。ここでは各ピースをバラバラにしている（ちゃんとバラバラにしていないのはご愛敬だが…）。
 |  |
ところで、このプラグインが作るパズルのカケラは、本来のジグソーパズルのカケラの形とは違う。本来、ジグゾーパズルでは各のピースはどれも違う形だけれど、このプラグインではどれも同じ形になる。今回のプラグインでは、それぞれのカケラ、ピースを並べ替えたあとでも、どのピースも形の上ではきちんとはまって、きれいに一枚の絵になる方が便利だろうと考えてどのピースも同じ形にしてみた。
だから、今回のMidinetteが作るパズルのカケラはどの場所に置いてもきちんとはまってしまう。だから
どのピースをどこに置くかはユーザー次第だ。もちろん、元画像がちゃんと再現するように並べてみても良いけれど、それでは元画像そのままだ。それは全然面白くない。せっかくばらばらのカケラにする意味がない。やっぱり、ここは自分の好みにまかせて、それぞれのパズルのカケラを好きな場所に置くべきだろう。
一旦、元の画像を頼りにならないとなってしまえば、あとはもう別に一つの答えがあるわけじゃないし、もう気の向くまま風の向くまま、「自分の感覚」だけを頼りにして、色々いじればきっと面白いはずだ。頭の中で色んな思考のカケラを並べてみるように、このMidinetteでパズルのカケラを自分の好きなように並べて遊んでみてもらえたら、とてもうれしい。 byぐるぐる
2002-04-20[n年前へ]
■今日のGoogleイメージ検索
"First Kiss"。なかなかキレイかな。（リンク）
」など。