Toy problemsは役立たずか(Floydの問題)

U = {√1, √2, …, √50}を2つのグループに分け、グループ毎の和を求める。和の差がなるべく小さくなるようなグループ分けを、制限時間10秒で見つけよ。

goal = (√1 + √2 + … + √50) / 2 ≈ 119.517900301760392247020223113… としたときに、{√1, √2, …, √50}のサブセットで、和がgoalに最も近いものを求めればよい問題です。

1881526917Bob Floydによって提供されたというこの問題は、Knuthによって1977年に発表されました(Selected Papers on Computer Scienceに再掲されています。参考文献リストあり。索引あり。)。

学生だったときに研究室(の一部)でこの問題を話題にしたことがあります。遺伝的アルゴリズム(Genetic Algorithm, GA)と呼ばれる最適化手法を研究する人が多くいた研究室でしたが、GAではあまりよい解は見つかりませんでした。(エージェントアプローチ人工知能 第1版のp.624によれば、GAは何かをする上で3番目によい方法だそうです。)

4274200183伊庭先生の『進化論的計算手法』でこの問題が取り上げられているのは、そのような経緯のためと思われます(ちなみに、この本の第1版のまえがきによると、私は第5章の共著者ということになっていますが、第6章の間違いですね。)

すべてのグループ分けは2の49乗通りありますが、当時のコンピュータで10秒でこれを全探索するのはおそらく不可能だったはずです。当時のコンピュータでよい解を見つけるには、大量のデータを処理する方法と計算時間を見積もる方法を知る必要がありました。ですから、このようなtoy problemsからも、いろいろ学ぶことがあるというのがKnuthの主張でした。

学ぶことがあるという点は今日でも変わりませんが、コンピュータは圧倒的に速くなっているので、この問題から学べることは少なくなっているかもしれません。それでも、やったことがない人は、ちょっとプログラムを書いて試してみてください。楽しめることは間違いありません。

doubleで計算するとこんな感じになります(最良解は1つではありません)。

119.517900301760391812422312796: goal
119.517900301760320758148736786: {1,4,5,7,8,9,12,13,15,16,20,25,27,30,31,33,37,38,41,43,44,46,47,48,49}
119.517900301760462866695888806: {2,3,6,10,11,14,17,18,19,21,22,23,24,26,28,29,32,34,35,36,39,40,42,45,50}

goalの正確な値は119.517900301760392247020223113...で、doubleの計算結果は小数点以下14桁までしか一致しません。2つのグループの合計の一致は、(厳密に計算しても)小数点以下12桁までなので、けっこうぎりぎりのところで計算していることがわかります。

GCCでlong doubleで計算するとこんな感じです(最良解は1つではありません)。

119.517900301760392242633734838: goal
119.517900301760320737332055074: {1,4,5,7,8,9,12,13,15,16,20,25,27,30,31,33,37,38,41,43,44,46,47,48,49}
119.517900301760463740996520698: {2,3,6,10,11,14,17,18,19,21,22,23,24,26,28,29,32,34,35,36,39,40,42,45,50}

コードは後ほど。