摘要
多项式复杂程度的非确定性(NP)问题是一种组合优化问题,模拟退火算法(SA)是其中的一种搜索方法,同其它通用的有效近似算法相比,SA应用的范围较广,运行的效率也较高,还具有描述较简单、能够实现灵活使用的优点。本文首先分析了SA的基本原理,针对TSP问题,我们将SA应用到TSP上,并建立了TSP的数学模型,阐述了利用模拟退火算法解TSP的方法。最后通过实验实现了求解TSP的模拟退火算法。
The problem of non-deterministic polynomial complexity （NP） is a combinatorial optimization problem. The simulated annealing algorithm （SA） is one of these search methods. Compared with other common approximation algorithm, SA is used in a wide range of applications. Its operating efficiency is high, its description is simple, and the use is flexible. This paper first analyzes the basic principles of the SA. For the TSP problem, SA is applied in the TSP and the TSP mathematical model is built. We describe the method of SA methods in the TSP. Finally, the simulated annealing algorithm is realized to solve the TSP by experiment.
出处
《电脑与电信》
2012年第4期36-38,47,共4页
Computer & Telecommunication
关键词
模拟退火
TSP
组合优化
simulated annealing
TSP
combination optimization
