ざつがく・どっと・こむ
ちょっと知的な雑学&トリビア

ナップサック問題

2001年11月08日 【コラム
Share...Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedIn

 今週は連想コラムみたいになっちゃったが、合言葉といえば、やはり暗号のことに踏みこまざるをえないか、と調べはじめる。ちょうど『暗号解読』という、古代から量子暗号までにいたるエピソードを盛りこんだ書籍がベストセラーになっているのでもある。
 とはいえこの問題、けっきょく現代の情報セキュリティの話にならざるをえず、ちょっと書きにくいなあ、なんて思いつつ調べを進めていたら、「ナップサック問題」という言葉に出会ったのだった。難解な数式の間にこのての話が出てくるとほっとする。
 ナップサック問題は、有名な巡回セールスマン問題などと並んで、組み合わせ最適化の解法に関する事例のひとつ。巡回セールスマン問題は、同じ道を通らずにすべての顧客を回る順路はあるか、あれば最短ルートを探せというもので、これの簡単なものは子ども雑誌にもクイズとして載っていたりする。
 ナップサック問題は、山を登るにあたってナップサックにどう荷物をつめればいいかを考える。たとえば背負える重さを10キロと限定する。全部はつめない。重い燃料をあきらめて小さな缶詰を多く詰めるのか、いや、燃料は必須で、残る範囲でほかの物を積んでいくか。
 この種の問題に対して、最適の答えを見つける公式、というか解法というか、そういうものが果たしてあるのかどうか、というところがポイント。じつはこれがまだわからないそうで、いまのところ無いんじゃないか、つまりしらみつぶしにあたっていくほかないんじゃないかと考えられている。だから、ナップサック問題を盛り込んだ暗号は、解くのに永遠に時間がかかるから有効だと。
 子どもが親を真似したがるので、アンパンマンのリュックを背負わせている。公園に行くとなると、好きなお菓子やボールやタオルなどを自分でつめている。大きな車のおもちゃも突っこんで。重いと思うのに、気にならないらしい。彼がナップサック問題に悩むのはいつからだろう、なんて考えている。抱っこと言われたとき辛くないよう、親の荷物はできるだけ減らしつつ。

Share...Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedIn

3 comments to...
“ナップサック問題”
Avatar
小橋昭彦

暗号についてはいいサイトが多いと思うのですが、とりあえずナップサック問題と関連して「暗号入門講座」「暗号について」などをご参照ください。で、「組合せ最適化って?」もどうぞ。書籍なら、『暗号解読』です。


Avatar
kenwinning

ナップサックというと一般的には小型のものを意味すると思うのですが…

ここで言う問題とは別にして実際の登山用パッキングの基本は『重いものを上にしろ』という定説があります。
重心を上げたほうが肩や腰にかかるプレッシャーを分散できトレッキングが楽になるのです。


Avatar
小橋昭彦

ああ、なるほど。ありがとうございます!

リュックサックの小型がナップサックですね。とするともしかして、「ナップサック問題」の語源は、リュックサックからナップサックに詰め替える、さあどれを残す、なんて設問にあったのかも。

などと空想しましたが、すみません、そのところまではあまり深くつっこんでいませんでした。いずれにせよ、ナップサックに10キロつむってのは無理かな。

気になって調べてみましたが、ナップザックという商品名の商品では、おおむね30から50リッターってところでしょうか。これなら大丈夫ですね。ほっ。




required



required - won't be displayed


Your Comment:

 木簡(もっかん)の利用法としておもしろいもののひとつに、奈良市の長屋王邸宅跡から見つかった例がある。中央に人名、横の端に三つの点。割れて文字が残ったというわけでもない。はじめは不明だったが、やがて画指(かくし)木簡だと判明する。 指を画(か)く。木簡の端に人差し指のつけ根をあて、指の先とそれぞれの関節ごとに印をつけたわけだ。人によって長さや関節の位置が違うから、本人かどうか識別できる。つまり、署名ができない人向けのIDカードだったわけ。 もっとも、当時出入りチェックに実用的に利用されていたかどうか、確かなところはわからない。子どもの奴婢(ぬひ)管理のためだったとも言われている。ま、少なくとも顔パスだけでは通じないほどの人数を抱えていたことは事実なのだろう。 誰何(すいか)の方法としていまひとつ思い浮かぶのは、合言葉だ。日本書紀に、天武天皇の時代に用いられた様子が記されているから、これが記録に残るもっとも初期の例のひとつだろう。有名なのは赤穂義士が使った「山」「川」だが、もともと浄瑠璃では、討入りの装束を調えた商人天河屋義平の屋号をとって、「天」「川」となっている。タイムスリップしたとき、お間違いの無いように。 ちなみに、小学館の日本大百科には、第二次大戦中に米国軍が「lollapaloosa(驚くべきこと)」を合言葉にした例が紹介されている。日本人はどうしたって「rorraparoosa」になっちゃうから、ばれてしまう。LとRの発音が苦手なのはいまの日本人もそうだけど、いやはや、運命をわけるとなれば、しっかり発音練習しなくちゃなあ。

前の記事

 珠玉のような作品が書けたら、なんてかなわぬ思いを抱きつつ、ほんとうの珠玉といえばやはり真珠かと文字から連想している。 貝があのように美しいものを生み出すなんて神秘的だが、世界大百科をひもとくと「貝殻を作るのと同じしくみ」と記述があり、なんだか納得した。真珠は内側から殻皮層、稜柱層、真珠層よりなっており、これは貝殻と逆の順序なわけだ。なるほど、そういえば貝の内側は美しいし、黒真珠が採れるクロチョウ貝を開いた写真を見ると、黒い光沢を放っていたりもするのだった。 天然真珠を生成する貝はおよそ1000種類あるという。古代エジプトではすでに装飾品として利用されており、真珠を飲み干したというクレオパトラの逸話が有名だが、中世ヨーロッパでは医薬としても利用されている。中国でも漢方の材料として知られ、楊貴妃が口にしていたと伝わる。炭酸カルシウムが成分なので、からだに良いというのも、あながちはずれているわけでもない。 日本では1890年代に御木本幸吉がはじめて養殖に成功している。そういえば修学旅行で訪れた三重県に記念島があった。旅行前の学習で真珠のことも調べたっけ。今ではすっかり忘れている。真珠のオンラインショップを開いていたPさん、退院されたと連絡もらったけど、その後いかがだろう。 真珠について書こうとするうち、文章はあちらへこちらへ飛び、珠玉からどんどん離れていく気がする。珠も玉も「たま」とよむ。すなわち「魂(たま)」。心をこめて書き連ねていれば、いつかは珠玉に出会える日もあるだろう。何も文章に限った話ではないが。

次の記事