ナップサック問題をポケコンで解く

ナップサック問題は重いらしい

手元に舞い込んできたとある資料によると

ks.gif

この問題は,14個ある荷物を入れるか入れないかで考えるので 214 = 16,384 通りの組合せとなり,すべての組合せをコンピュータに計算させると最適な組合せ(解)を見つけるのに数十分もかかってしまいます。(中略)遺伝的アルゴリズムを用いると,わずか数秒で答を求めることができます

要するにGAの優位性を訴えているのですが、この程度の問題に、どうやったら数十分もかかるのか疑問で仕方ありません。というわけで実際に試してみました。

C言語で解いてみる

Pentium3@800MHzの、今となっては決して速くないCPUとgcc3.3を使いこの問題を総当たりで解いてみました。ソースファイルはこちら

nabe~$ gcc -O2 ks.c -o ks.o
nabe~$ time ./ks.o
Best pairing : 0(A) 1(B) 2(C) 4(E) 6(G) 7(H) 9(J)
Best value   : 530

real    0m0.005s
user    0m0.001s
sys     0m0.004s

プログラムの起動時間を入れても5ms、実際に問題を解いている時間だけみれば1msです。数秒をうたっているGAよりもはるかに速い結果です。困ったことになってしまいました。どうやら実験に使った環境が速すぎたようです。

JavaScriptで解いてみる

遅いマシンをすぐに用意できればよかったのですか、今更Pentium(初代)レベルのマシンやそれ以前のマシンを用意するのも大変です。マシンを遅くする代わりに処理系を遅くしてしまうことにしました。きっとコンパイルしてマシン語に変換されたのが問題だと思うので、処理が遅い言語としてインタプリタを使用することします。

ブウラザがあればどこでも動くJavaScriptによる実装です。

14個の荷物について計算します
最大重量 = 200
組み合わせ : A B C E G H J
最的値 = 530
計算時間 = 90 ms

実行マシンはCeleronの1GHzで、gccと比べても実行環境として100倍以上遅いのですが1秒を切ってしまいました。単純計算で100MHz程度のマシンをもってきても1秒程度で答えが出るようです。どうしましょう、数十分どころか、数秒と言われるGAよりも高速です

考えが甘かった。まだまだマシンが速すぎたようです。もっと決定的に遅いマシンならいいのですが、身近に、もっと遅くてプログラマブルのコンピューターがなかなか思い当たりません。ファミコン? 携帯? あーこれがありましたっ!

ナップザック問題をポケコンで解いてみる

pc-g815.jpg

まず簡単にスペックをおさらいしておきましょう。

型番SHARP PC-G815
CPUZ80相当 3.58MHz
メモリ(RAM)32KB

3.58MHzです! 今までより格段に遅いマシンです。最近のマシンと比較すれば1000分の1のクロックで「64ビットだー!」と世間が騒がしいこのご時世に8bit。単純計算で8分の1ですが、潜在的な能力差はその数倍にも昇ります。

これだけのマシンを持ってくれば誰も速いなんて文句を付けるような無粋な人間はいないと思いますが、念には念を入れて次の選択をしました。

プログラム言語BASIC

(パソコンと比べれば)劇遅なZ80の上で動くBASICインタプリタ。もはや文句はないでしょう。

さて実際にプログラムを打ち込むのですが、たった4行の狭い画面に打ち込むのが大変な上、BASICの文法が(CやPerlに慣れた今になっては)違和感ありまくりで一苦労でした。できあがったソースはこちら

きちんと正解が出るのか走らせてみましょう。多少緊張しつつ、RUNと入力します。

pc-g815_kekka.jpg

解けました、解けました。さて気になる時間は135秒!(手動計測) 2分15秒ですから、さすがに時間掛かってます。ですが、数十分どころか、数分にすらなりません! わざわざインタプリタでこれですから、普通にCで書いたとして一体どんなマシン持ってきたら数十分になるでしょう。誰か教えてっ!!