现代计算机：下半月版
現代計算機：下半月版
현대계산궤：하반월판
Modem Computer
2012年
2期
3-5,18
,共4页
旅行商问题%近似算法%模拟退火算法
旅行商問題%近似算法%模擬退火算法
여행상문제%근사산법%모의퇴화산법
Travelling Salesman Problem%Approximate Algorithm%Simulated Annealing Algorithm
旅行商问题TSP是一类典型的NP完全问题．围绕着这个问题有各种不同的求解方法，已有的算法例如动态规划法、分支限界法、回溯法等，这些精确式方法都是指数级的，根本无法解决目前的实际问题．贪心法是近似方法．无法达到比较满意的近似比。常用的遗传算法也是求解这类问题的常用方法之一。由于该问题的解是一种特殊的序列．所以遗传算法在求解该问题时的性能也并不理想。模拟退火算法具有描述简单、使用灵活、运用广泛、运行效率高和较少受到初始条件约束等优点．是解决旅行商问题的一种很好的算法。
旅行商問題TSP是一類典型的NP完全問題．圍繞著這箇問題有各種不同的求解方法，已有的算法例如動態規劃法、分支限界法、迴溯法等，這些精確式方法都是指數級的，根本無法解決目前的實際問題．貪心法是近似方法．無法達到比較滿意的近似比。常用的遺傳算法也是求解這類問題的常用方法之一。由于該問題的解是一種特殊的序列．所以遺傳算法在求解該問題時的性能也併不理想。模擬退火算法具有描述簡單、使用靈活、運用廣汎、運行效率高和較少受到初始條件約束等優點．是解決旅行商問題的一種很好的算法。
여행상문제TSP시일류전형적NP완전문제．위요착저개문제유각충불동적구해방법，이유적산법례여동태규화법、분지한계법、회소법등，저사정학식방법도시지수급적，근본무법해결목전적실제문제．탐심법시근사방법．무법체도비교만의적근사비。상용적유전산법야시구해저류문제적상용방법지일。유우해문제적해시일충특수적서렬．소이유전산법재구해해문제시적성능야병불이상。모의퇴화산법구유묘술간단、사용령활、운용엄범、운행효솔고화교소수도초시조건약속등우점．시해결여행상문제적일충흔호적산법。
Travelling salesman problem is a kind of a typical NP-complete problems, around this problem there are different ways of solving.The existing algorithms such as dynamic programming method, Branch and bound method, Backtracking, etc. These precision-type methods are expo- nential, simply will not solve the practical problems. Greedy method is approximate method can not achieve satisfactory approximation ratio. Genetic algorithm for solving such problems is also one of the commonly used. Since the solution of the problem is a special sequence, therefore, the genetic algorithm in salving the problem of performance is not satisfactory. Describes simulated annealing algorithm in a simple, flexible, use a wide range, run efficient and less constrained by the initial conditions, is a good algorithm to solve the travelling salesman problem.
