| 以文本方式查看主题 - SCI论坛 (http://artsoncqu.eicp.top/scibbs/index.asp) -- 数学建模 (http://artsoncqu.eicp.top/scibbs/list.asp?boardid=38) ---- 版主那里有关于npc问题的电子图书 (http://artsoncqu.eicp.top/scibbs/dispbbs.asp?boardid=38&id=1271) |
| -- 作者：wenkejiujiu -- 发布时间：2003/7/5 14:46:57 -- 版主那里有关于npc问题的电子图书 版主那里有关于npc问题的电子图书??? |
| -- 作者：cquhrb -- 发布时间：2003/7/5 16:54:26 -- 到超星去找找吧。 |
| -- 作者：wenkejiujiu -- 发布时间：2003/7/6 15:22:52 -- 在学校的今年的第一题中,模拟退火算法,我怎么改变参数也无法达到很好的效果! 比如第二组数据我只能得到430只有的数据可是其精确解是408 第三组数据我只能得到540左右 是不是在较短的时间内就只能得到这种结果呢/ 因为模拟退火算法求最优解的复杂度不穷举都高!!!!! 望回复!!! |
| -- 作者：wenkejiujiu -- 发布时间：2003/7/6 15:31:13 -- 对了,一般遇到npc问题是不是就用组合优化的算法求近似解就可以了呢?,比如tsp问题jsp问题 但是这些在大规模的数据中还是收敛的很慢! 不过有些小规模的是可以求出最优解的!!! |
| -- 作者：cquhrb -- 发布时间：2003/7/7 9:19:24 -- 龚劬老师要详细的给你们介绍模拟退火算法，复杂的npc问题通常只能求其近似解。 |
| -- 作者：gong -- 发布时间：2003/7/11 9:27:00 -- 以下是引用wenkejiujiu在2003-7-6 15:22:52的发言：
在学校的今年的第一题中,模拟退火算法,我怎么改变参数也无法达到很好的效果!
比如第二组数据我只能得到430只有的数据可是其精确解是408
第三组数据我只能得到540左右
是不是在较短的时间内就只能得到这种结果呢/
因为模拟退火算法求最优解的复杂度不穷举都高!!!!!
望回复!!!
不知道你们队的计算时间和控制参数的具体设置，另有两个队采用模拟退火算法，3组数据的解分别是19，408和470，得到了最优解，效果很好，可以交流一下具体参数的设置。关键参数的设置对算法性能影响很大。SA的关键参数包括初始温度t0, 温度更新函数T(t)，Markov链长Lk和终止温度tf等，理论上设定的控制参数在实际应用中效果不一定理想，通常只能依据一定的启发式规则或大量试验来加以选取。
另外，可考虑给算法增加一个记忆器，使之能记住搜索过程中遇到过的最好结果，当结束时，将最终解与记忆器中的解比较，取较优者作为最后结果。还可考虑在有记忆的模拟退火算法后链接一个局部搜索算法。
|
| -- 作者：wenkejiujiu -- 发布时间：2003/7/13 0:20:33 -- 不会吧！我看了一些关于模拟退火的算法的介绍，上面证明了用模拟退火算法的时间复杂度比穷举还高的多，我用了穷举还用了17分钟，1g的硬盘，而且还是c语言！ |
| -- 作者：gong -- 发布时间：2003/7/13 10:07:00 -- 模拟退火算法的最终解质量和CPU时间 校内竞赛A题是一个NP难题，这类问题被认为不存在求最优解的有效算法。穷举法和分支定界算法等可用于求小型的组合优化问题的最优解，但大型问题（求最优解的算法的计算时间太长，比如，若干月，若干年，无法承受）只能用一些近似算法或启发式算法来求解。 模拟退火算法就是一种启发式算法，适合解大型问题，不一定能保证所得解的最优性。当然，校内竞赛A题给出的三个实例都是小型的，模拟退火算法的效果可能不及穷举法。解大型问题更能显示出模拟退火算法的优越性。 事实上，模拟退火算法的最终解质量和CPU时间呈反向关系，很难两全其美，解决办法只有：折中，即在合理的CPU时间里尽量提高最终解的质量。这涉及到冷却进度表所有参数的合理选取，可参考唐立山等著的《非数值并行算法——模拟退火算法》。 模拟退火算法的计算时间复杂度为O(k Lm t(n) ), 其中Lm是k个Markov链长的最大者，t(n)是问题规模n的多项式函数。 |
| -- 作者：wenkejiujiu -- 发布时间：2003/7/14 12:24:12 -- 谢谢!!! |
| -- 作者：gator -- 发布时间：2004/6/25 23:47:38 -- Some related links: http://www.busygin.dp.ua/npc.html it also includes some other useful links. http://www.nada.kth.se/~viggo/problemlist/compendium.html |