小橋 昭彦 2001年11月8日

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

0

3 thoughts on “ナップサック問題

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

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

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

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

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

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

Leave a comment.

Your email address will not be published. Required fields are marked*