神经网络解决 TSP问题题目：基于 Hopfield网络算法的TSP问题的分析与实现学号： 2220150496 姓名：陈帅1 一、预备知识1、TSP问题旅行商问题，简称TSP，即给定 n 个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。其图论描述为：给定图G=（V，A），其中 V 为顶点集， A 为各顶点相互连接组成的边集，设D=（dij）是由顶点 i 和顶点 j 之间的距离所组成的距离矩阵，要求确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短距离。旅行商问题可分为如下两类：（1）对称旅行商问题（ dij=dji，Π i，j=1，2，3，?，n）；（2）非对称旅行商问题（ dij≠dji，?i，j=1，2，3，?，n）。非对称旅行商问题较难求解，我们一般是探讨对称旅行商问题的求解。若对于城市 V={v1，v2，v3，?，vn}的一个访问顺序为T={t1，t2，t3，?，ti，?，tn}，其中 ti∈V（i=1，2，3，?，n），且记 tn+1=t1，则旅行商问题的数学模型为：minL=。。TSP是一个典型的组合优化问题，并且是一个NP 完全难题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发式的搜索、 优化算法的间接比较标准。因此，快速、有效地解决TSP有着重要的理论价值和极高的实际应用价值。2、Hopfield 网络Hopfield网络是一种互连型网络的一种，它引入类似于 Lyapunov函数的能量函数概念，把神经网络的拓扑结构 (用连接权矩阵表示 )与所求问题 (用目标函数描述 )相对应，并将其转换为神经网动力学系统的演化问题。其演变过程是一个非线性动力学系统，可以用一组非线性差分议程描述(离散型 )或微分方程 (连续型 )来描述。系统的稳定性可用所谓的“能量函数 ”进行分析。在满足条件的情况下，某种2 “能量函数 ”的能量在网络运行过程中不断地减少，最后趋于稳定的平衡状态。因为人工神经网络的变换函数是一个有界函数，故系统的状态不会发生发散现象。目前，人工神经网络经常利用渐进稳定点来解决某些问题。如果把系统的稳定点视为一个记忆的话， 那么从初态朝这个稳定点的演变过程就是一个寻找记忆的过程。 如果把系统的稳定点视为一个能量函数的极小点，而把能量函数视为一个优化问题的目标函数， 那么从初态朝这个稳定点的演变过程就是一个求解该优化问题的过程。因此，Hopfield神经网络的演变过程是一个计算联想记忆或求解优化问题的过程。 实际上， 它的解决并不需要真的去计算，而是通过构成反...
