论文部分内容阅读
算法复杂性理论中的NP完全问题是悬解的著名难题之一。旅行商问题作为经典的组合优化问题，实际中的应用非常广泛．但它却是一个NP完全问题。历年来，对它的一项主要研究工作，就是寻找一种既有高质量的解，又能快速收敛的近似算法。围绕这项研究．本文的主要创新是：首先，设计了求解该问题的一种嵌入遗传算子的启发式算法，它在本质上是经典插入算法的改良．但同时渗透了遗传算法思想；其次，对于这种近似算法，文章阐明算法具有多项式时间界0（n^3），并且给出了评价其性能的不超过2的界估计及其严格的理论证明，因而它的算法理论基础是坚