以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 算法理论与分析 』  (http://bbs.xml.org.cn/list.asp?boardid=60)
----  压气机叶片排序  (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=29736)


--  作者:vororo
--  发布时间:4/1/2006 10:09:00 AM

--  压气机叶片排序
压气机叶片排序

由于加工出的压气机叶片的重量和频率不同,安装时需要按工艺要求重新排序。

1. 压气机24片叶片均匀分布在一圆盘边上,分成六个象限,每象限4片叶片的总重量与相邻象限4片叶片的总重量之差不允许超过一定值(如8g)。

2. 叶片排序不仅要保证重量差,还要满足频率要求,两相邻叶片频率差尽量大,使相邻叶片频率差不小于一定值(如6Hz)。

3. 当叶片确实不满足上述要求时,允许更换少量叶片。

请按上述要求给出:

1. 按重量排序算法;

2. 按重量和频率排序算法;

3. 叶片不满足要求时,指出所更换叶片及新叶片的重量和频率值范围;

4. 当叶片保证了重量差和频率差时,按排列顺序输出。

这个算法怎么做呢?


--  作者:vororo
--  发布时间:4/4/2006 10:16:00 AM

--  
我用穷举法,一点也没技术含量

--  作者:nansanzi
--  发布时间:8/16/2006 7:24:00 PM

--  
兄台,这是一个NP难问题。如果用穷举搜索算法,其时间复杂性函数为:
24!,该函数需要的基本操作数是:10的23次方,用运算能力为1Mflops(每秒一百万次浮点运
算)的计算机进行求解需要至少3000年才能找到最优解。穷举是无效的

--  作者:nansanzi
--  发布时间:8/16/2006 7:24:00 PM

--  
兄台,这是一个NP难问题。如果用穷举搜索算法,其时间复杂性函数为:
24!,该函数需要的基本操作数是:10的23次方,用运算能力为1Mflops(每秒一百万次浮点运
算)的计算机进行求解需要至少3000年才能找到最优解。穷举是无效的

--  作者:nansanzi
--  发布时间:8/16/2006 7:34:00 PM

--  
可以考虑遗传算法、模拟退火算法等智能优化算法
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
39.063ms