クヌースのヒューリスティクスの概要

Floydの問題を解くためにクヌースが考案したヒューリスティクスの概要をまとめる。

Floydの問題：

１〜５０までの整数がある。これをA、Bの２つの組にわけ、それぞれ組においてルートをとって和をとる。この和がもっとも近くなるようにA、Bを決めよ。

すなわち、
U = \{1, 2, 3, , , 50\}
A \subset U
B = U - A
Sa = \sum _{a \in A} \sqrt{a}
Sb = \sum _{b \in B} \sqrt{b}
としたとき、
Sa - Sbが最小となるような集合Aを求めよ。

注）本当は１０秒という制限がある。

クヌースのヒューリスティクス

まず、小数点以下を合わせ、その後に整数部分を考える。

1. I = {1, 4, 9, 16, 25, 36, 49}とし、これらはルートをとっても整数になるので後で考える。
2. X = {2, 8, 18, 32, 50}、Y = {3, 12, 27, 48}、Z = {5, 6, 7, 10, 11, 13, 14, 15}とする。集合Xについてはルートをとるとすべてルート２の倍数になるので、和の場合の数は実は2^5 = 32ではなく、16通りとなる(ルート２の係数が０〜１５）。同様に、Yについては2^4 = 16ではなく11通り。Zは減らせず、2^8 = 256通り。
3. P = X ∪ Y ∪ Zとし、Pの（だいたい）すべての和の場合の数16 * 11 * 256 = 45056通り (16bit以内）について、数の組み合わせと平方根和を、これらの和の小数点以下１６bitをキーとしてハッシュに入れる。
4. Q = U - I - Pとする。この要素の数は50 - 7 - (5 + 4 + 8) = 26である。Qについてすべての組み合わせ2^26通りを考えて、それぞれ119.517900301760 . . .(=(Sa + Sb)/2)との差をとり、その差分の小数点以下をキーとしてハッシュでヒットした集合を加えてAとし、評価する。すなわち2^26の全探索を行い、もっとも小数点以下がSaとSbで近くなるようにする。
5. 最後に整数部分が近くなるようにIの要素をAとBに振り分ける。この部分はIの全探索なのでたかだか2^7 = 127通り。

クヌースのヒューリスティクスの評価回数は45056 + 2^26 + 2^8 ≒ 2^26≒6.7 * 10^7である。

＜原典＞
Are Toy Problems Useful?
Knuth
(in Selected Papers on Computer Science)
(Originally published in Popular Computing, Volume 5, Number 1 (January1977) and Volume 5, Number 2 (Feburary 1977).)

結果の比較

最適解の精度は10＾-12。桁数は整数を含めて15桁。全探索で評価回数は2^49 = 5.6 * 10^14回。

最適解の一つは（もちろんこの精度を実現する組み合わせは複数ある）
A = {7, 8, 12, 13, 15, 16, 25, 27, 30, 31, 33, 36, 37, 38, 41, 43, 44, 45,46, 47, 48, 49}
Sa = 119.517900301760320754230296092
Sb = 119.517900301760463739810150134
(By T.Y)

実時間についてはPentium4 ３GHｚ WindoowsXP ハイパースレッディング(およそ１GHｚ） Cygwinコンパイラでの時間。N君のアルゴリズムについてはこちらを参照。GAの詳細についてはここを参照。

参考

N君のアルゴリズムとは集合Aの要素数N(A)を固定した探索手法。基本的に全探索するが、探索の打ち切りをうまく使うため、N(A)が小さいときは評価回数を減らすことができる。これ以上深く探索しても絶対に良い解が得られないと分かっているときのみ、探索を打ち切りを行う。探索の打ち切りはプログラムの実行時にしか決まらず、どれくらい評価回数を減らすことができるかも事前には分からない。本来、N(A)＝24、N(A)＝25でも探索を行うべきであるが、計算時間がかかりすぎるため実行することができなかった。

N(A)	実際の評価回数	全探索をした場合の評価回数(50CN(A))	実際に評価した割合
19	4.5 * 10^3	3.0 * 10^13	1.4 * 10^-10
20	2.7 * 10^7	4.7 * 10^13	5.7 * 10^-7
21	3.2 * 10^9	6.7 * 10^13	4.7 * 10^-5
22	7.1 * 10^10	8.8 * 10^13	8.0 * 10^-4
23	5.2 * 10^11	1.0 * 10^14	4.8 * 10^-3