计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2006年
33期
71-73
,共3页
旅行商问题%NPC%closest-point%最近点前后插入法%近似算法
旅行商問題%NPC%closest-point%最近點前後插入法%近似算法
여행상문제%NPC%closest-point%최근점전후삽입법%근사산법
旅行商问题(TSP)是典型的具有NPC复杂性的组合优化问题.在现有求解TSP问题的2-近似算法closest-point算法基础上,通过对插入点的插入位置进行改进,提出了一种有效的近似算法最近点前后插入法(CPBOA),并采用TSPLIB中的一些典型实例对该算法进行了测试,同时与典型的常数近似比算法MST-PRIM算法和closest-point算法进行了比较.实验结果表明,该算法在求解质量上与closest-point和MST-PRIM算法相比都有很大的改进,而且速度也很快.
旅行商問題(TSP)是典型的具有NPC複雜性的組閤優化問題.在現有求解TSP問題的2-近似算法closest-point算法基礎上,通過對插入點的插入位置進行改進,提齣瞭一種有效的近似算法最近點前後插入法(CPBOA),併採用TSPLIB中的一些典型實例對該算法進行瞭測試,同時與典型的常數近似比算法MST-PRIM算法和closest-point算法進行瞭比較.實驗結果錶明,該算法在求解質量上與closest-point和MST-PRIM算法相比都有很大的改進,而且速度也很快.
여행상문제(TSP)시전형적구유NPC복잡성적조합우화문제.재현유구해TSP문제적2-근사산법closest-point산법기출상,통과대삽입점적삽입위치진행개진,제출료일충유효적근사산법최근점전후삽입법(CPBOA),병채용TSPLIB중적일사전형실례대해산법진행료측시,동시여전형적상수근사비산법MST-PRIM산법화closest-point산법진행료비교.실험결과표명,해산법재구해질량상여closest-point화MST-PRIM산법상비도유흔대적개진,이차속도야흔쾌.
