基于Delaunay三角剖分处理二维欧式空间MTSP的近似算法

发布时间：2020-02-07 16:06

【摘要】：考虑了在二维欧式平面内的多旅行商问题,通过Delaunay三角剖分的方法,将问题转化为求解多个旅行商问题。树分解算法的核心是Delaunay边的空圆性质并且可以证明该算法的近似比为2。最后,通过数值模拟验证了算法的有效性。

【相似文献】

相关期刊论文 前10条

1 闵卫东，，唐泽圣;二维Delaunay三角划分的平均形态比最大性质[J];计算机学报;1994年S1期

2 毛建华,郭庆胜,闫浩文,梅志雄;限制性Delaunay三角网的剖分算法[J];兰州铁道学院学报;2002年03期

3 方锡武,崔汉国;有限元网格自动生成的Delaunay算法[J];海军工程学院学报;1998年04期

4 陈学工,潘懋;空间散乱点集Delaunay四面体剖分切割算法[J];计算机辅助设计与图形学学报;2002年01期

5 宋绪钦;Delaunay图在公共设施场址选择中的应用[J];测绘学院学报;2005年03期

6 汪嘉业;杨承磊;张彩明;吕琳;;一致分布点集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];西北工业大学;2006年

6 李晓玲;直角梯形的全等三角剖分[D];河北师范大学;2015年

7 王晓琛;正多边形与直角三角形的相似三角剖分[D];河北师范大学;2015年

8 李英;两类多边形相似三角剖分问题的研究[D];河北师范大学;2014年

9 孙明明;一类加密三角剖分下样条函数空间的维数[D];广西民族大学;2007年

10 张鼎林;空间曲面上点云的三角剖分[D];吉林大学;2007年

本文编号：2577237