wayne 发表于 2010-3-25 16:11:44

用 改进的差分进化算法
算得一个比较好的分法：
{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 发表于 2010-3-25 21:52:36

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

wayne 发表于 2010-3-25 22:01:37

你可以下载一个1stopt 软件，代码是Title "D. Knuth";
Constant n = 50;
Parameter x(1:n);
Minimum = True;
Function abs(2*(sum(i=1:n)(sqrt(i)*x))-sum(i=1:n)(sqrt(i)));

KeyTo9_Fans 发表于 2010-3-25 23:25:15

这种改进方法效率不高吧？

$21#$的结果wayne跑了多久？

最佳结果大概是$239/2^50~=2e-13$。

还有一点差距。

wayne 发表于 2010-3-26 09:13:28

这个算法本质是随机算法。
算法收敛值设的越小，跑的时间越长，另外，不同的参数设置，如种群数，变异率等，也能影响收敛的快慢，
上面的结果，我好像花了二十多分钟才得到的

===================================
最佳结果应该不会到-13那个数量级的，大概跟我上面的结果很靠近，-9，-10这个数量级~~

sw2wolf 发表于 2010-3-26 09:15:03

问题可简单为如何快速求n个数的组合？ 当n=50时， 就有250。

--Data.List.subsequences其实就是
combination :: -> []
combination [] =[[]]
combination (x:xs) = concat [[(x:ys), ys] | ys <- combination xs]
在GHCI中测试
>:set +s
> length \$ combination
1024
(0.00 secs, 1053176 bytes)
> length \$ combination
32768
(0.04 secs, 5778956 bytes)
*Money> length \$ combination
1048576
(1.03 secs, 161482428 bytes)
.。。。。。。

所以穷举法随着n的增大就不可行了！

wayne 发表于 2010-3-26 09:20:53

这题只能用启发式的算法来做

如果能有确定性的高效算法，那你就顶天了

wayne 发表于 2010-3-26 10:53:21

要不，降格以求
把这题换成擂台的形式

看谁给出的分组最优？

gxqcn 发表于 2010-3-26 11:15:05

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

wayne 发表于 2010-3-26 12:13:16

改进的结果
{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
页: 1 2 [3] 4 5 6 7
查看完整版本: 高德纳书中一道很普通的题目