【摘要】：考慮了在二維歐式平面內的多旅行商問題,通過Delaunay三角剖分的方法,將問題轉化為求解多個旅行商問題。樹分解算法的核心是Delaunay邊的空圓性質并且可以證明該算法的近似比為2。最后,通過數值模擬驗證了算法的有效性。

【相似文獻】

相關期刊論文 前10條

1 閔衛(wèi)東，，唐澤圣;二維Delaunay三角劃分的平均形態(tài)比最大性質[J];計算機學報;1994年S1期

2 毛建華,郭慶勝,閆浩文,梅志雄;限制性Delaunay三角網的剖分算法[J];蘭州鐵道學院學報;2002年03期

3 方錫武,崔漢國;有限元網格自動生成的Delaunay算法[J];海軍工程學院學報;1998年04期

4 陳學工,潘懋;空間散亂點集Delaunay四面體剖分切割算法[J];計算機輔助設計與圖形學學報;2002年01期

5 宋緒欽;Delaunay圖在公共設施場址選擇中的應用[J];測繪學院學報;2005年03期

6 汪嘉業(yè);楊承磊;張彩明;呂琳;;一致分布點集Delaunay三角化最佳期望時間算法[J];計算機輔助設計與圖形學學報;2011年12期

7 胡于進,趙虎躍,趙建軍;基于Delaunay準則的三維網格自動插點算法[J];華中理工大學學報;2000年05期

8 王德生,萬水;與波前法相結合的Delaunay四面體網格生成方法(英文)[J];Journal of Southeast University(English Edition);2002年02期

9 王兆清,馮偉;Delaunay多邊形單元的有理函數插值格式[J];力學季刊;2004年03期

10 劉金義;周培德三角剖分不是最小權三角剖分[J];計算機輔助設計與圖形學學報;2001年12期

相關會議論文 前1條

1 嚴金輝;劉劍飛;;一種新型的逐點插入Delaunay三角剖分算法插入序[A];北京力學會第17屆學術年會論文集[C];2011年

相關博士學位論文 前2條

1 馮笑;三維凸體表面的銳角三角剖分[D];河北師范大學;2015年

2 彭興璇;三角剖分上的多元有理樣條及其應用[D];大連理工大學;2006年

相關碩士學位論文 前10條

1 周曉;三維空間Delaunay網格剖分技術的研究[D];天津大學;2016年

2 李永耀;高維Voronoi算法研究[D];華南理工大學;2016年

3 李蒙;Delaunay網格劃分算法設計與實現[D];東北大學;2014年

4 梁虎;二維Delaunay網格生成算法研究[D];國防科學技術大學;2011年

5 崔凌國;約束Delaunay四面體剖分及其相關算法的研究[D];西北工業(yè)大學;2006年

6 李曉玲;直角梯形的全等三角剖分[D];河北師范大學;2015年

7 王曉琛;正多邊形與直角三角形的相似三角剖分[D];河北師范大學;2015年

8 李英;兩類多邊形相似三角剖分問題的研究[D];河北師范大學;2014年

9 孫明明;一類加密三角剖分下樣條函數空間的維數[D];廣西民族大學;2007年

10 張鼎林;空間曲面上點云的三角剖分[D];吉林大學;2007年

本文編號：2577237