文档介绍：一、问题描述旅行商问题,即 TSP 问题( Travelli ng Salesman Problem ) 是数学领域中著名问题之一。假设有一个旅行商人要拜访 n 个城市,他必须选择所要走的路径, 路经的限制是每个城市只能拜访一次, 而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。图1 TSP 问题的示意图二、遍历算法一个最容易想到的方法是利用排列组合的方法把所有的路径都计算出来,并逐一比较, 选出最小的路径。虽然该方法在理论上是可行的, 但路径的个数与城市的个数成指数增长,当城市个数较大时,该方法的求解时间是难以忍受的,甚至是不可能完成的。以每秒 1 亿次的计算速度来估算, 如果 TSP 问题包含 20 个城市时,求解时间长达 350 年;如果要处理 30 个城市,则求解时间更长达 1+10e16 年。如此长的时间,在实际中完成是难以想象的。三、模拟退火算法模拟退火算法是解决 TSP 问题的有效方法之一, 其最初的思想由 Metropoli s 在 1953 年提出, Kirkpatrick 在 1983 年成功地将其应用在组合最优化问题中。模拟退火算法来源于固体退火原理, 将固体加温至充分高, 再让其徐徐冷却, 加温时, 固体内部粒子随温升变为无序状, 内能增大, 而徐徐冷却时粒子渐趋有序, 在每个温度都达到平衡态, 最后在常温时达到基态, 内能减为最小。用固体退火模拟组合优化问题, 将内能 E 模拟为目标函数值 f, 温度 T 演化成控制参数 t ,即得到解组合优化问题的模拟退火算法:由初始解 i 和控制参数初值 t 开始, 对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减 t 值, 算法终止时的当前解即为所得近似最优解, 这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。求解 TSP 的模拟退火算法模型可描述如下: 解空间:解空间 S 是遍访每个城市恰好一次的所有路经,解可以表示为{w1,w2 , ……, wn} , w1, ……, wn 是 1,2, ……,n 的一个排列,表明 w1 城市出发, 依次经过 w2, ……, wn 城市,再返回 w1 城市。初始解可选为(1, ……, n); 目标函数:目标函数为访问所有城市的路径总长度; 我们要求的最优路径为目标函数为最小值时对应的路径。新路径的产生:随机产生 1和n 之间的两相异数 k和m ,不妨假设 k<m , 则将原路径(w1,w2, …,wk,wk+1, …,wm,wm+1, …,wn) 变为新路径: (w1,w2, …,wm,wk+1, …,wk,wm+1, …,wn) 上述变换方法就是将k和m 对应的两个城市在路径序列中交换位置, 称为 2-opt 映射。根据上述描述, 模拟退火算法求解 TSP 问题的流程框图如下图2 模拟退火算法的流程框图四、主要代码对应于流程框图,实现流程的主体函数是 pution() ,代码如下: UINT pution(LPVOID pParam) { while(1) { double deltatotaldis = ; while(1) { SYRouter SelRouter( , NowTemperature, NowExternal