模拟退火算法求解TSP问题.doc

摘 要 旅行商问题，即TSP问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一TSP问题是一个典型的NP 完全问题,模拟退火算法是求解此问题的一种比较理想的方法。 模拟退火算法是迭代求解策略的一种随机寻优算法TSP问题旅行商问题是一个组合优化问题该问题被证明具有NPC计算复杂性受到高度的关注算法在函数优化上的应用TSP问题以及模拟退火算法实际enterlast problem, the problem, in the field of mathematics. TSP problem famous one problem is a typical NP, impersonate all annealing algorithm is the solution of the problem of a rather ideal method. Simulation of annealing the algorithm is not an iterative the solution of a random TSP problem, this algorithm for the travel company is a combination of optimization problem. The question was shown to the complexity of the NPC. Thus, research on degradation is the basic principle of the TSP problem and solution of the application by a high degree of concern. This article focuses on the principle of simulated annealing algorithm and some of the knowledge structure what associated with the first point. By studying the principle of their algorithm, simulated annealing algorithm to optimize the application function, and optimization of research to understand the problem and the simulated annealing algorithm for TSP The practical application and research. Help to understand the basic principles of simulated annealing algorithm and its application in solving TSP problems. KEY WORDS SAA；TSP；NPC；Combinatorial Optimization 目 录 摘 要 I ABSTRACT II 第一章 引言 2 1.1 TSP问题的基本概念 2 1.2 模拟退火算法的背景 2 1.3 发展前景 3 第二章 2.1模拟退火算法的原理 4 2.1.1 模拟退火的基本思想 4 2.1.2 算法对应动态演示步骤 4 2.2 TSP问题简述 5 第三章 问题描述与算法分析研究 6 3.1应用研究整体规划 6 3.2应用开发环境 6 3.2.1开发语言 6 3.2.2开发平台 6 3.3 TSP问题的描述和分析 7 3.4模拟退火算法的分析 7 3.4.1模拟退火算法模型 7 3.4.2模拟退火算法与优化问题分析 8 3.5应用研究方案分析 8 第四章 算法具体设计与编码实现 9 4.1基于模拟退火算法求解TSP问题详细设计 9 4.1.1求解TSP问题的模拟退火算法及流程图 9 4.1.2主要代码 11 第五章 算法运行分析 13 5.1 运行界面图示 13 5.2 运行结果 15 第六章 结束语 16 致 谢 17 参考文献 18  引言 旅行商问题（Traveling Salesman Problem，TSP）可描述为：已知N个城市之间的相互距离，现有一推销员必须遍访这N个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，使其旅行路线