高德纳书中一道很普通的题目

wayne

用 改进的差分进化算法 算得一个比较好的分法： {1, 6, 7, 8, 9, 10, 13, 15, 16, 20, 21, 22, 23, 27, 28, 30, 35, 36, 37, 41, 43, 44, 47, 48, 50} {2, 3, 4, 5, 11, 12, 14, 17, 18, 19, 24, 25, 26, 29, 31, 32, 33, 34, 38, 39, 40, 42, 45, 46, 49} 两组元素的平方根之和的差值 2.01*10^-8

wayne

大致就是生物学上的自然选择，优胜劣汰过程

wayne

你可以下载一个1stopt 软件，代码是

1. Title "D. Knuth";
2. Constant n = 50;
3. Parameter x(1:n)[0,1,0];
4. Minimum = True;
5. Function abs(2*(sum(i=1:n)(sqrt(i)*x[i]))-sum(i=1:n)(sqrt(i)));

复制代码

KeyTo9_Fans

这种改进方法效率不高吧？ $21#$的结果wayne跑了多久？ 最佳结果大概是$239/2^50~=2e-13$。 还有一点差距。

wayne

这个算法本质是随机算法。 算法收敛值设的越小，跑的时间越长，另外，不同的参数设置，如种群数，变异率等，也能影响收敛的快慢， 上面的结果，我好像花了二十多分钟才得到的 =================================== 最佳结果应该不会到-13那个数量级的，大概跟我上面的结果很靠近，-9，-10这个数量级~~

sw2wolf

问题可简单为如何快速求n个数的组合？ 当n=50时， 就有2⁵⁰。 --Data.List.subsequences其实就是 combination :: [a] -> [[a]] combination [] = [[]] combination (x:xs) = concat [[(x:ys), ys] | ys <- combination xs] 在GHCI中测试 >:set +s > length \$ combination [1..10] 1024 (0.00 secs, 1053176 bytes) > length \$ combination [1..15] 32768 (0.04 secs, 5778956 bytes) *Money> length \$ combination [1..20] 1048576 (1.03 secs, 161482428 bytes) .。。。。。。 所以穷举法随着n的增大就不可行了！

wayne

这题只能用启发式的算法来做 如果能有确定性的高效算法，那你就顶天了

wayne

要不，降格以求 把这题换成擂台的形式 看谁给出的分组最优？

gxqcn

好啊，期限定为一个月，就截止到2010年4月30日，给最佳答案提供者奖励50枚金币。 现在我把该主题醒目处理。

wayne

改进的结果 {1, 3, 4, 5, 9, 10, 11, 12, 14, 15, 17, 18, 22, 24, 27, 29, 31, 32, 35, 39, 40, 41, 44, 46, 47, 50} {2, 6, 7, 8, 13, 16, 19, 20, 21, 23, 25, 26, 28, 30, 33, 34, 36, 37, 38, 42, 43, 45, 48, 49} 两组的差值 4.777E-9