数组内容随机排序问题请教

lanyf

原帖由 Zamyi 于 2011-4-6 17:38 发表
恩，SIN应该以弧度为单位吧？D2=C2*SIN(PI()/7.5*(ROW()-2))。上面是随机取数，不如直接历遍求最值好。

直接遍历对应15个，要遍历全部则有（15-1）！个，能全部遍历吗？以前的一算就死机

灰袍法师

楼主一年后还在研究这个问题吖，呵呵
http://club.excelhome.net/thread-559715-3-1.html

要高速用VBA去配重，应该 先把15个扇叶在15个位置的配重算出来，这样就不必在每一次随机排序里面都算一次

只需要随机排序序号，然后根据每个扇叶的序号直接读取对应的配重效果相加即可

随机排序一个数组可以用我的VBA排序贴
有史以来最快的希尔排序 - 比历史贴快10倍，比Excel排序更快 - 兼论堆排序和快速排序
http://club.excelhome.net/thread-661033-1-1.html

lanyf

呵呵 一年前的做好了
是在vb中利用spreadsheet里利用随机排序做的
不过随机的结果不理想
有时候计算99次的结果比计算9999次的还要好
最近看到旅行商问题，就又想起了这个事情
不过我看网上对这类问题讨论多半都是基于遗传算法
我现在讨论的可能仅是概率算法吧（不太清楚~~）
若是对15个结果遍历的话，计算量太大了 更何况还有16、17或更多的呢
所以想归结为看用哪种算法最好~~
由于仅仅是工作用到了 才东问一下西问一下 呵呵 一点基础没有~~~~~
不过我会努力多学习的~~
谢谢灰袍法师的提点~~

灰袍法师

原帖由 lanyf 于 2011-4-6 20:06 发表
呵呵 一年前的做好了
是在vb中利用spreadsheet里利用随机排序做的
不过随机的结果不理想
有时候计算99次的结果比计算9999次的还要好
最近看到旅行商问题，就又想起了这个事情
不过我看网上对这类问题讨论多半都 ...

你的想法是对的，单纯用随机算法，得到的结果很不稳定

而且也有相当大的概率得到一个不理想的结果

要避免这两个缺点，就要做很多次随机试验，如100万次甚至上亿次，这样的计算耗时就可能无法接受。

我自己对这种问题用的是 随机＋贪婪算法，对每一个随机结果，都尝试去调换两片扇叶，使结果更好，直到无法调整为止。

不过老实说，这样的NP难问题，用什么算法都无法保证最终结果一定是最好的。几种算法并用，然后选最佳值比较合适。

lanyf

原帖由 灰袍法师 于 2011-4-6 20:19 发表


你的想法是对的，单纯用随机算法，得到的结果很不稳定

而且也有相当大的概率得到一个不理想的结果

要避免这两个缺点，就要做很多次随机试验，如100万次甚至上亿次，这样的计算耗时就可能无法接受。

我自 ...

谢谢法师的指点
收益匪浅~~谢谢
贪婪算法~~呵呵 一窍不通

lpy6666

1、找出最小数

lanyf

原帖由 Zamyi 于 2011-4-6 17:07 发表
原来代码不对。试试下面：结果 0.001 And m < Ktime
  For i = 1 To 15
    t = Int((16 - i) * Rnd() + 1)
    te = b(t)
    b(t) = b(16 - i)
    b(16 - i) = te
    Next
  MinSin = 0
  MinCos = 0
  ...

谢谢帮助
我会仔细研究的 谢谢

lanyf

原帖由 dsmch 于 2011-4-6 16:50 发表
附件
901813

好用 谢谢了
我仔细看看代码
再结合下细节问题
有不懂的地方再请教~~

灰袍法师

原帖由 lanyf 发表
灰袍法师
正如您所说的采用希尔排序速度很快
可是我要排列的对象就15~30个, 只是排列的次数要多吧了, 这样速度优势还能显现嘛
正如1年前您帮我证明的，采取这种随机算法的话
即使落在最优解的地方的概率为0.01%，只要多次排列得到最优解的概率可以到达99.99%
可是若有20张叶片，只要可选方案就是19！，也就是是说落在最优解的概率只有1/19！
这样比如运行了9999得到的结果，到底算不算是最优结果呢~~

希尔排序即使只是每次排几十个数据，排一百万次，速度也是很快的，几分钟而已。

不过现在问题根本不是排序速度，而是要达到非常高的优化程度，那么随机试验的次数将是无法接受的。

如你举例19片扇叶，那么即使随机排出10万种方案，最好的一种也只不过是19!里面的10万种，占百分比几乎是0

但是，这么一丁点百分比的抽样，却可以以99.99%的概率保证这个解绝对是 落在0.01%范围的最优解

因为这种算法的优化精度只跟抽样大小有关，跟所有方案一共有多少个是无关的。

即使你排1000个扇叶(1000!)，抽10万个方案还是99.99%概率保证 落在最优的0.01%范围

而你对最优解的理解不正确

唯一的最优解是不可能得到的！

我说0.01%的意思是：保证找到的解比全部解当中的99.99%都好

也就是说，如果所有解一共有1万亿个，那么保证比其中的9999亿个要好，但不一定是最优解，因为可能还有1亿个解比它好

下面，我们把最优解的范围精度提高，从0.01%提高到0.001%

这时候，随机排10万个方案，只能以63％的概率保证求出的解是落在 0.001%的范围内！！！

要随机排90万次，才能保证99.99%的概率，求出的解落在0.001%的最优范围（一万亿个解的话，就是说求出了最好的1千万个解的其中一个）

所以，单纯用随机算法，是不可能求出最优解的，也不大可能非常接近最优解
（实际上不管用什么方法去解NP难的问题，也不可能保证求出的解就是最优解，甚至也不可能保证很接近最优解）

话说，以你的问题来看，也根本没必要求出很高的精度

本身风扇叶片的称重，求重心等等都是有误差的，而且静平衡求得再高，风扇一转起来就全变了。。。。。。

不是做这一行，不过我觉得提高叶片的加工精度才是王道吧？

实在不行，安装以后，然后给不平衡的叶片加一个平衡的配重行不？

[ 本帖最后由 灰袍法师 于 2011-4-6 23:37 编辑 ]

lanyf

原帖由 灰袍法师 于 2011-4-6 23:31 发表


希尔排序即使只是每次排几十个数据，排一百万次，速度也是很快的，几分钟而已。

不过现在问题根本不是排序速度，而是要达到非常高的优化程度，那么随机试验的次数将是无法接受的。

如你举例19片扇叶，那么 ...

法师果然是法师~~~解释相当到位
事实上也正是法师所讲的
叶片前期布置仅仅是为后期做准备
待到整体组装完成后，要对整体做静平衡
而且单张叶片重量精度一般.01kg，所以只有结果在。01就算是最优解（可接受解解）
呵呵~~求的精度再高 也是没必要的
现在又问相关的问题
主要是想看到了遗传算法了
想了解下我们的概率算法和遗传算法区别在哪~~
多谢法师指导~~~为我解开了大的难题~~