最少分组方案算法

gxqcn

我有一个简单算法，可以非常高效地得到较优的解，
但无法保证（或证明）是最优解。

看两周内是否有更妙的算法，
否则我将把它公开，让大家来一起探讨。

无心人

贪心算法么？

gxqcn

原帖由 无心人 于 2008-8-14 08:43 发表
贪心算法么？

也许算是吧。
（刚查了手头一本书，有“贪婪算法”这个提法，
我对这些专业术语把握得不是太准）

无心人

就是每次都捡大数字组合在一起
直到不满足条件
再换下一组
叫贪心或者贪婪算法
名字不同而已
但应该效果不是最好

遗传算法
我想
是随机组合成两个解
再根据特定算法，（比如随机组合）
将两个解每组当作一个基因，进行基因的组合
如果有解基因数量不同。短的补1即可
得到新的两个解
如此不断分裂
中间可能会出现某个解的两个基因远小于给定数字
将之组合成一个基因，称为进化


瞎说的，大家也可优化下具体过程

gxqcn

楼上的前半部与我的算法原理基本吻合。

用该算法，可将 1024! （把它看作前 1024 个正整数序列）分解成 292 个可用 DWORD 表达的整数之积。
而 1024! 有 8770bits，故最少分组数极限值 = ceil(8770/32) = 275，
292 / 275 * 100% = 106.18%，效果还是很不错的。

无心人

还有一个挑选原则
是乘后尽量大

可以用对数加快测试速度
设已有的数字的二为底的对数和为x
找对数值最接近32-x的剩余数字

无心人

如果以对数做方程的系数
0或者1做方程的解
还可以列一个线性不等式组

但以LZ的例子
要172 X 172个项了

shshsh_0510

求这类复杂问题的近似最优解一般的通用的较高级方法有模拟退火，遗传算法，神经网络等等。
这个恐怕用遗传算法不会有什么益处。
用贪心是最直接的想法，可以快速得出一些结论。
我提一种贪心规则，不知效果如何：
1、S={前172个素数}
2、在集合S的所有4-tuple中,取其积不超过Bound的最大者，然后从S中去掉
3、if |S| > X then goto 2 else 穷举 S的分划，求最优解。
对上面算法的一点分析：
步骤1的复杂度小于 C(n,4)+C(n-4,4)+...,为O(n^5). n=172 时 <318015874 。计算机可解
需要选取适当的X，比如我们想进行10^9次计算，则有分划的近似公式
比如:p(X)=e^(2.56*X^0.5) /6.9X , p(X)=10^9 , X=115
当X=|S|时，即位实际的最优解，计算量在10^11的数量级，比较大，PC难于计算

gxqcn

我的算法相对比较简单，
得到上述 13# 结果的代码总共不超过30行（其中8行是大括号）。
（即：将前1024个正整数分组，使每组数之积可用 DWORD 型表达）

shshsh_0510

  , 问一下，你得到47组的用多长时间