安徽科技学院学报
安徽科技學院學報
안휘과기학원학보
JOURNAL OF ANHUI SCIENCE AND TECHNOLOGY UNIVERSITY
2014年
2期
43-48
,共6页
凸包%工作集%工作集划分%TSP%二维
凸包%工作集%工作集劃分%TSP%二維
철포%공작집%공작집화분%TSP%이유
TSP问题是一个NP完全问题,在现实生活中许多领域得到充分应用.通过对“S计算几何”中凸包算法分析,提出了一种最大凸包工作集规划TSP路径算法,能快速解决二维TSP问题.首先运用凸包算法构造城市的最大凸包工作集,将剩余城市节点根据隶属度大小加入到相应的凸包子工作集中.再应用最大凸包算法逐个划分凸包子工作集,直至子工作集中的尺度为2.最后依次访问每个子工作集头,得到TSP最短路径.实验结果表明,该算法能更快速地得到问题的近似最优解.
TSP問題是一箇NP完全問題,在現實生活中許多領域得到充分應用.通過對“S計算幾何”中凸包算法分析,提齣瞭一種最大凸包工作集規劃TSP路徑算法,能快速解決二維TSP問題.首先運用凸包算法構造城市的最大凸包工作集,將剩餘城市節點根據隸屬度大小加入到相應的凸包子工作集中.再應用最大凸包算法逐箇劃分凸包子工作集,直至子工作集中的呎度為2.最後依次訪問每箇子工作集頭,得到TSP最短路徑.實驗結果錶明,該算法能更快速地得到問題的近似最優解.
TSP문제시일개NP완전문제,재현실생활중허다영역득도충분응용.통과대“S계산궤하”중철포산법분석,제출료일충최대철포공작집규화TSP로경산법,능쾌속해결이유TSP문제.수선운용철포산법구조성시적최대철포공작집,장잉여성시절점근거대속도대소가입도상응적철포자공작집중.재응용최대철포산법축개화분철포자공작집,직지자공작집중적척도위2.최후의차방문매개자공작집두,득도TSP최단로경.실험결과표명,해산법능경쾌속지득도문제적근사최우해.
