最少分组方案算法

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组的用多长时间