旅行商问题优化解之间关系的分析  

Relationship Analysis Between Optimal Solutions of TSPs

作　　者：王东[1] 吴湘滨[1] 毛先成[1] 刘文剑[1] 

机构地区：[1]中南大学地学与环境工程学院

出　　处：《小型微型计算机系统》2008年第5期879-884,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金-广东中生代典型侵入岩隆升过程研究项目(40473029)资助

摘　　要：旅行商问题是经典的组合优化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.

关 键 词：旅行商问题 全局最优解 局部最优解 裁减 求解质量 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]