基于delaunay三角剖分的tsp问题求解-.研究

《基于delaunay三角剖分的tsp问题求解-.研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于Delaunay三角剖分的TSP问题求解研究对相应算法的特性和求解步骤等做较为详细的分析，并比较目前流行的几种求解TSP的算法优缺点。在此基础上，对基本蚁群算法的描述、算法特性，用蚁群算法求解TSP问题的优势与不足，以及改进算法不足的相关技术环节做较为详细的论述。第4章基于候选集策略的改进蚁群算法。作为本文的研究重点，本章首先着重论述基于Delaunay三角剖分的候选集策略，并通过与基于最近邻居的候选集选择策略比较，分析该策略在求解TSP问题中的优势与作用。接着，着重论述最大最小蚁群算法的特性。在此基础上，结合局部搜索法，探索对求解TSP问题的蚁群算法的

2、改进，并对参数选择和算法时间复杂度等，做较为详细的论述。第5章算法验证及其实验结果分析。本章首先对改进算法的运行结果进行分析，通过与现有经典算法运行结果的比较，指出改进算法的优势，并结合一个TSP问题实例，验证本文所提出的改进算法的有效性。第6章总结与展望。对本文所做的工作进行总结，并对今后需要进一步研究的工作提出展望。5第2章Delaunay三角剖分及其生成算法第2章DeIaunay三角剖分及其生成算法本章重点论述平面点集的Delaunay三角剖分的特性、准则以及Delaunay三角网的生成算法，为运用Delaunay三角剖分的相关技术特性求解TSP问题奠

3、定理论基础。2．1Delaunay三角剖分的基础知识Delaunay三角剖分是求解TSP问题的基础理论之一，针对Delaunay三角剖分研究，首先必须掌握如下几个概念：(1)Delaunay三角剖分的研究对象及其基本概念Delaunay三角剖分以欧几罩德平面上的点集为研究对象，包括点、给定两点的线段、3个给定点确定的平面，以及由有序点序列组成的多边形等概念。用E2表示2维欧几里德平面，下面给出Delaunay三角剖分研究中所涉及到的一些基本概念的定义。1)线段：给定E2中两个不同的点pl和p2，连接点pl和p2间的直线被称为这两点间的线段，一般可记为而。2)

4、凸集：设D是E2中的域，且PJ和p2是D中的任意两点，如果线段pip2完全包含在D中，则称域D是凸的，也称D为凸集。3)凸包：E2中点的集合S的凸包是指E2中包含S的最小凸域的边界，凸包有时也被称为凸壳。4)多边形：多边形定义为平面内线段的有限集合，该集合中每条线段的端点恰好为两条边所共有。其中，线段被称为多边形的边，线段的端点被称为多边形的顶点，且顶点数和边数相等。若多边形的任意两个不相邻边互不相交，则称该多边形为简单多边形。简单多边形把平面划分为两个不相交的区域：内部区域(有界的)和外部区域(无界的)。一般情况下，将多边形理解为边界和内部区域的并。若简单

5、多边形P的内部区域是凸集，则称P是凸的。如果P内存在点q，使得对于P的所有顶点P而言，线段印完全位于P内，则此简单多边形是星形多边形。5)三角剖分；若平面剖分的所有有界区域是三角形，则此平面剖分称为三角6基于Delaunay三角剖分的TSP问题求解研究剖分。有限点集S的三角剖分是S上具有最大边数的平面图。或者说，由不相交的直线段来连接S的点得到S的三角剖分，且每个三角形区域都在点集S凸壳的内部。6)平面图；若平面中含有的图G=(V，E)互不交叉，则G是平面图。把直线嵌入到一个平面中所形成的划分，称为平面划分。设平面图的顶点数、边数、面数分别为v，e和f，则有

6、公式：v-e+f=2(2．1)公式(2．1)被称为欧拉公式。(2)三角剖分三角剖分是计算几何领域中的重要几何结构之一，它具有广泛的应用价值。三角形与其他类型的多边形相比，具有许多特性和优点，在许多领域有着广泛的应用，如有限元网格自动生成、计算机图形处理及模式识别、三维实体几何造型系统中的曲面描述及隐藏面消除等。Delaunay三角剖分是一种特殊的三角剖分，具有每个三角形的外接圆内不含有其他生成对象、Delaunay三角网是唯一的、改变一个生成对象的位置只影响其局部结构发生的变化、Delaunay三角形的边一般小于随机选择的两节点间的连接边等特点。这些特点保证

7、了网格的整体质量是最优的，以及有限元迭代算法是稳定可靠的，因而引起了众多学者对之展开研究。可以说，Delaunay三角剖分思想是计算机图形学中的一个非常重要的理论基础。2．2平面点集的三角剖分在计算几何领域中，点集的三角剖分问题研究是科学计算与分析中的一种重要的方法，即使在其它的应用领域，点集的三角剖分问题也是广为人知的。二维或者更高维点集的三角剖分，对组合优化问题以及图形学来说，都是极其重要的。针对平面点集三角剖分的研究，其理论和算法尤为成熟。针对平面上的一个点集P={pl，p2，⋯，pn)，所谓平面点集三角剖分是指用互不相交的直线段连接Pi与pj(1

8、，j9，i≠j)，并使凸壳内的每一个区域都是一个三角