13个数以上全排列请教 为什么运行时提示 内存溢出？

lanyf

我也觉得这样有问题
可是想不出什么好办法
要解决的问题见附件
大家看看
采取怎么样的方法才能实现呢~~

[ 本帖最后由 lanyf 于 2010-4-16 08:58 编辑 ]

灰袍法师

正如我在上面所言，这种平衡配置的问题，用随机算法是非常有效的

附件的算法是：
1 把所有扇叶随机排序，求出当前配重结果
2 如果当前结果更好，则保留，否则放弃
3 不断重复1,2步（100次），最后把最好结果写回工作簿

增加随机排序＋计算的循环次数，会更大几率得到更好的解，但是附件用读写工作簿，循环次数多的时候速度会很慢，用VBA代替函数公式会加快求解速度几百倍以上，留给楼主自己做了

虽然简单用随机算法不能保证得到非常好的解（请楼主定义非常好的意思），但是通常也不会太坏

如果在每次随机排序以后，程序聪明一点，尝试互换两个扇叶的位置使结果更好，这样的局部调整＋随机算法可以在极短时间内得到极好的结果，还是留给楼主自己做。

本附件删除，改良的附件在24楼，速度快几百倍了(当然，改为全VBA估计会再快几十倍)

[ 本帖最后由 灰袍法师 于 2010-4-15 03:31 编辑 ]

lb_bn

学习，谢谢老师提供算法。

xihabang

呵呵
学习中 ..

灰袍法师

嗯，光把Excel工作簿的屏幕刷新关掉，就已经加速几百倍了

附件随机算1万次，结果比100次随机好得多啦，合成力＝0.156，在我的笔记本耗时也就25秒。

同理，算个100万次，也就一小时不到，大可以看一下能够好到什么程度。

不过。。。。。。我估计100万次跟1万次的结果相差应该不会有数量级的改善，所以还是把这一小时省下来，考虑一下辅助的调整算法吧

设计一个根据历史统计信息，不断自我进化的算法：

比方说，设定一个标准代表配重结果是好的（合成力<=10），

那么当随机配重的结果是好结果的时候，就记录下每个位置的叶片出现次数

假设得到了 100个好结果，而又发现第2号叶片出现在第7位置40次

这样随后的随机算法就可以优先把 第2号叶片分配到第7位置，这样应该能导致最终结果更好。

当然，如果单纯随机法已经得到足够好的结果，也就不必再麻烦了。

[ 本帖最后由 灰袍法师 于 2010-4-15 04:14 编辑 ]

灰袍法师

由于附件的排序是用录制宏，所以可能在一些机器上会不能运行

自己重新录制一个排序宏，把叶片按随机数辅助列排序

然后把录制宏的代码替换我附件的代码，其中 with 到 end with 这一段即可

附带一个简单的证明，随机算法是有效的

假设所有可能的排列方案按从优到差排序，而我们要求得到的结果是落在 最好的0.01% 之内

很显然，每次随机方案只有 0.01%的几率 符合要求的标准

但10万次随机中间，将会有 1 - (1-0.01%)^10万 = 99.995% 的几率得到符合要求的结果!!!

所以对于精确度要求不是很高的情况，随机算法是非常高效的。

注意：简单地按顺序穷举10万次，跟随机10万次是不同的，一定要随机才能保证得到上述的高几率。
这也是为什么穷举法根本不予考虑的原因。

[ 本帖最后由 灰袍法师 于 2010-4-15 22:02 编辑 ]

lanyf

呵呵 谢谢老师讲解
我收获很大
本来一心想用穷举法来做的
昨天自己也搜索了一些随机函数及应用的例子
我自己也录制一个宏 嘿嘿
现在正在看看怎么在vb中将其代码编写出来呢
vb可编译为可执行文件
使用相对比较方便~~