主题：版主那里有关于npc问题的电子图书

版主那里有关于npc问题的电子图书???

到超星去找找吧。

在学校的今年的第一题中,模拟退火算法,我怎么改变参数也无法达到很好的效果! 比如第二组数据我只能得到430只有的数据可是其精确解是408 第三组数据我只能得到540左右 是不是在较短的时间内就只能得到这种结果呢/ 因为模拟退火算法求最优解的复杂度不穷举都高!!!!! 望回复!!!

对了,一般遇到npc问题是不是就用组合优化的算法求近似解就可以了呢?,比如tsp问题jsp问题 但是这些在大规模的数据中还是收敛的很慢! 不过有些小规模的是可以求出最优解的!!!

龚劬老师要详细的给你们介绍模拟退火算法，复杂的npc问题通常只能求其近似解。

不知道你们队的计算时间和控制参数的具体设置，另有两个队采用模拟退火算法，3组数据的解分别是19，408和470，得到了最优解，效果很好，可以交流一下具体参数的设置。关键参数的设置对算法性能影响很大。SA的关键参数包括初始温度t0, 温度更新函数T(t)，Markov链长Lk和终止温度tf等，理论上设定的控制参数在实际应用中效果不一定理想，通常只能依据一定的启发式规则或大量试验来加以选取。 另外，可考虑给算法增加一个记忆器，使之能记住搜索过程中遇到过的最好结果，当结束时，将最终解与记忆器中的解比较，取较优者作为最后结果。还可考虑在有记忆的模拟退火算法后链接一个局部搜索算法。

不会吧！我看了一些关于模拟退火的算法的介绍，上面证明了用模拟退火算法的时间复杂度比穷举还高的多，我用了穷举还用了17分钟，1g的硬盘，而且还是c语言！

校内竞赛A题是一个NP难题，这类问题被认为不存在求最优解的有效算法。穷举法和分支定界算法等可用于求小型的组合优化问题的最优解，但大型问题（求最优解的算法的计算时间太长，比如，若干月，若干年，无法承受）只能用一些近似算法或启发式算法来求解。 模拟退火算法就是一种启发式算法，适合解大型问题，不一定能保证所得解的最优性。当然，校内竞赛A题给出的三个实例都是小型的，模拟退火算法的效果可能不及穷举法。解大型问题更能显示出模拟退火算法的优越性。 事实上，模拟退火算法的最终解质量和CPU时间呈反向关系，很难两全其美，解决办法只有：折中，即在合理的CPU时间里尽量提高最终解的质量。这涉及到冷却进度表所有参数的合理选取，可参考唐立山等著的《非数值并行算法——模拟退火算法》。 模拟退火算法的计算时间复杂度为O(k Lm t(n) ), 其中Lm是k个Markov链长的最大者，t(n)是问题规模n的多项式函数。

谢谢!!!

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