论文部分内容阅读
NP难解问题是计算机算法和理论界长期研究的课题.在求解NP难解问题时,随机算法的性能往往很不稳定.在以往的实验中,人们发现基于重启的优化方法可以提高Las Vegas算法的性能和稳定性.尽管它的思想比较直观,但对它的性能进行理论分析却并不容易,这在很大程度上限制了其应用.该文使用连续概率分布对算法性能分布建模,针对Las Vegas算法提出了一种高效的重启策略构造方法.该文从平均性能和稳定性两个角度分析了该方法的效率,同时通过将其应用于求解大规模旅行商问题(TSP)显示了其应用价值.