| 摘要: |
| 将确定性退火技术及聚类方法应用于旅行商问题,给出了求解旅行商问题的一种启发式算法.该方法将旅行商问题的离散模型转化为连续模型去求解,通过求解一系列随温度变化的物理系统的自由能函数的局部极小来获得旅行商问题的解,并给出了一个简单的显式迭代公式.算例表明,该算法性能良好. |
| 关键词: 确定性退火技术,旅行商问题,聚类,极大熵原理. |
| DOI： |
| 分类号: |
| 基金项目:本文研究得到国防科技预研基金资助. |
|
| An Algorithm for Travelling Salesman Problem Using Deterministic Annealing |
|
YANG Guang-wen,ZHENG Wei-min,WANG Ding-xing,LI Xiao-ming
|
| Abstract: |
| In this paper, the deterministic annealing and clustering algorithms are applied to the travelling salesman problem, and a heuristic algorithm for the travelling salesman problem is put forward. The method transforms the discrete model of the travelling salesman problem into the continuous model, and the solution of the problem is obtained by solving local optimal solution of a series of problems to minimize the free energy of a physical system which varies with temperature. A simple explicit iterative formula is given. The computation results indicate that this algorithm has good performance. |
| Key words: Deterministic annealing, travelling salesman problem, clustering, the principle of maximum entropy. |
