毕业论文移动版

1.3.4蚁群算法（ACA）

该算法也是一种启发式算法，是利用群集智能来解决组合优化问题。20世纪90年代Dorigo首先提出了该算法，并且将其应用于旅行商问题取得了很好的效果，后来许多人对该算法进行了改进，文献[24]提出了基于ACA求解TSP问题的分段算法；文献[25]提出了智能蚂蚁算法；文献[26]则创造性的提出了带聚类处理的并行蚂蚁系统，极大的提高了收敛速度。

1.3.5其他算法

除了上述的算法外，还有很多新算法来解决TSP问题，以达到提高求解的效果，文献[27]采用了多项式时间的进化算法来求解TSP；文献[28]采用了混沌神经动力学与2-opt算法相结合来求解TSP。

1.4本文的主要安排

本文主要对TSP问题进行了研究，对各种算法进行了详细的介绍和比较，选取Hopfield神经网络方法进行了编程实现，并对该方法进行了了非常详细的介绍以及算法的改进，从而得到比较满意的求解结果。具体安排如下： 

第一章， 介绍TSP问题的由来、应用价值以及研究现状等问题。

第二章， 对TSP问题进行详细的分析，介绍其作为NPC问题的求解难点。

第三章， 选择了遗传算法、人工免疫算法，混合优化算法和蚁群算法进行了介绍并且对介绍其各自的优缺点。

第四章， 对Hopfield神经网络算法进行详细的介绍并进行了编程实现和算法改进。

第五章， 总结。

2介绍TSP问题及其作为NPC的求解难点

    旅行商问题在图论中是很有代表性的组合优化问题，为了说明TSP求解的重要性，这里首先介绍计算复杂性问题。

2.1计算复杂性。[ ]源.自/优尔·论\文'网·www.youerw.com/

    人们通过长期的探索研究得知，并不是所有的问题都可以通过计算解决。根据算法存在与否，可以讲待解决的问题分为两类：如该问题存在有解题的算法，称该问题是可解决的（Decidable）;反之，用任何算法都无法解决的问题，称为不可解决的（Undecidable）。这里所谓的可解决和不可解决的概念，是建立在数理逻辑基础上的，也就是用回答真和假的方式来进行处理。

    1936年图灵指出，有一类问题可难到任何算法都无法解决。例如，无法找到一个计算程序，实际上也是不能通过任何计算工具来加以解决。为此，有必要了解计算复杂性这个既重要又较难理解的概念。

    计算复杂性涉及计算问题求解的定量分析，用定量分析加以确定解决某一类问题算法所需要的计算资源的限额。