摘要
旅行商问题是经典的组合优化NP难题之一,学术界一直致力于建立在合理的计算时间内精确或近似求解问题的算法.近似算法常求得的高质量近似优化解与全局最优解之间边交集不为空,建立了两者之间及与全局最优解之间的特定关系,通过数学分析建立量化关系模型,利用实验确立模型中相关参数的先验概率.据此建立的随机TSP裁减过程大幅度裁减问题的求解规模;在求解过程中亦能高概率确定属于全局最优解的边,以提高问题求解效率和质量.
Traveling Salesman Problem is one of the typical NP-hard problems in the field of combinatorial optimization. Academe commits himself to finding new algorithms for solving exactly or approximately TSP in reasonable computing time for a long time. The fact,which the intersection between high-quality optimal solutions found by approximate algorithm and global optimal solutions ,establishes two kind of special relationships ,the one is between them, and the other one is among high-quality optimal solutions. The quantizing relationship model can be set up through mathematic analysis, and the prior probability of correlative parameters in the model is computed in virtue of experiment. By utilizing it, the stochastic TSP cutting procedure cuts sharply down problem solving scale. The edges can be identified in high probability whether or not they belong to the edge set of global optimal solutions so that the solving efficiency and quality is improved effectively.
出处
《小型微型计算机系统》
CSCD
北大核心
2008年第5期879-884,共6页
Journal of Chinese Computer Systems
基金
国家自然科学基金-广东中生代典型侵入岩隆升过程研究项目(40473029)资助
关键词
旅行商问题
全局最优解
局部最优解
裁减
求解质量
traveling salesman problem
global optimal solution
local optimal solution
cutting
solution quality
