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

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