计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2002年
7期
701-707
,共7页
对称TSP问题%局部搜索算法%填充函数变换%近似最优解
對稱TSP問題%跼部搜索算法%填充函數變換%近似最優解
대칭TSP문제%국부수색산법%전충함수변환%근사최우해
该文提出了求对称TSP问题近优解的填充函数算法. 首先, 在用局部搜索算法求得对称TSP问题的一个局部极小解后, 对该问题作填充函数变换得到一新的组合优化问题, 新问题的局部极小解和最优解分别是原问题的局部极小解和最优解, 而且在对称TSP问题的目标函数值大于或等于其目标函数当前极小值的区域中, 新问题只有一个已知的局部极小解. 随后用局部搜索算法求新问题的一个局部极小解, 它或者是已知的局部极小解, 或者是对称TSP问题的更好的局部极小解. 对多个标准实例的计算试验表明,该文所构造的算法优于直接求解对称TSP问题的局部搜索算法.
該文提齣瞭求對稱TSP問題近優解的填充函數算法. 首先, 在用跼部搜索算法求得對稱TSP問題的一箇跼部極小解後, 對該問題作填充函數變換得到一新的組閤優化問題, 新問題的跼部極小解和最優解分彆是原問題的跼部極小解和最優解, 而且在對稱TSP問題的目標函數值大于或等于其目標函數噹前極小值的區域中, 新問題隻有一箇已知的跼部極小解. 隨後用跼部搜索算法求新問題的一箇跼部極小解, 它或者是已知的跼部極小解, 或者是對稱TSP問題的更好的跼部極小解. 對多箇標準實例的計算試驗錶明,該文所構造的算法優于直接求解對稱TSP問題的跼部搜索算法.
해문제출료구대칭TSP문제근우해적전충함수산법. 수선, 재용국부수색산법구득대칭TSP문제적일개국부겁소해후, 대해문제작전충함수변환득도일신적조합우화문제, 신문제적국부겁소해화최우해분별시원문제적국부겁소해화최우해, 이차재대칭TSP문제적목표함수치대우혹등우기목표함수당전겁소치적구역중, 신문제지유일개이지적국부겁소해. 수후용국부수색산법구신문제적일개국부겁소해, 타혹자시이지적국부겁소해, 혹자시대칭TSP문제적경호적국부겁소해. 대다개표준실례적계산시험표명,해문소구조적산법우우직접구해대칭TSP문제적국부수색산법.
