计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2013年
3期
657-665
,共9页
旅行商问题%近似算法%多项式时间近似方案%凸壳%旋转卡壳%射影
旅行商問題%近似算法%多項式時間近似方案%凸殼%鏇轉卡殼%射影
여행상문제%근사산법%다항식시간근사방안%철각%선전잡각%사영
欧氏旅行商问题(TSP)的多项式时间近似方案(PTAS)结合了递归剖分、动态规划两种方法.相似的技术已成功用于构造多个欧氏组合优化问题的PTAS.为进一步拓展该方法的适用范围,研究曲面上的TSP.观察到球面不像平面那样可以递归正则剖分,对于可被开半球完全覆盖的小尺度球面TSP,采用的策略为将其逆球心射影到一个球内接正方形上,扰动其顶点并构造剖分网格,接着将该网格射影到球面,然后如同平面TSP的PTAS一样进行动态规划等操作.该策略被拓展到非小尺度球面TSP及更一般的一类曲面TSP.需注意的是由于球面、平面之间射影变形的不规则性,无法将球面TSP直接PTAS归约为平面TSP.
歐氏旅行商問題(TSP)的多項式時間近似方案(PTAS)結閤瞭遞歸剖分、動態規劃兩種方法.相似的技術已成功用于構造多箇歐氏組閤優化問題的PTAS.為進一步拓展該方法的適用範圍,研究麯麵上的TSP.觀察到毬麵不像平麵那樣可以遞歸正則剖分,對于可被開半毬完全覆蓋的小呎度毬麵TSP,採用的策略為將其逆毬心射影到一箇毬內接正方形上,擾動其頂點併構造剖分網格,接著將該網格射影到毬麵,然後如同平麵TSP的PTAS一樣進行動態規劃等操作.該策略被拓展到非小呎度毬麵TSP及更一般的一類麯麵TSP.需註意的是由于毬麵、平麵之間射影變形的不規則性,無法將毬麵TSP直接PTAS歸約為平麵TSP.
구씨여행상문제(TSP)적다항식시간근사방안(PTAS)결합료체귀부분、동태규화량충방법.상사적기술이성공용우구조다개구씨조합우화문제적PTAS.위진일보탁전해방법적괄용범위,연구곡면상적TSP.관찰도구면불상평면나양가이체귀정칙부분,대우가피개반구완전복개적소척도구면TSP,채용적책략위장기역구심사영도일개구내접정방형상,우동기정점병구조부분망격,접착장해망격사영도구면,연후여동평면TSP적PTAS일양진행동태규화등조작.해책략피탁전도비소척도구면TSP급경일반적일류곡면TSP.수주의적시유우구면、평면지간사영변형적불규칙성,무법장구면TSP직접PTAS귀약위평면TSP.
