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

摘要：

旅行商问题是经典的组合优化NP难题之一,学术界一直致力于建立在合理的计算时间内精确或近似求解问题的算法.近似算法常求得的高质量近似优化解与全局最优解之间边交集不为空,建立了两者之间及与全局最优解之间的特定关系,通过数学分析建立量化关系模型,利用实验确立模型中相关参数的先验概率.据此建立的随机TSP裁减过程大幅度裁减问题的求解规模;在求解过程中亦能高概率确定属于全局最优解的边,以提高问题求解效率和质量.

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

所属期刊栏目：29

分类号：TP301(计算技术、计算机技术)

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

在线出版日期：2008-07-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：879-884