平面内可相交直线序列的遍历算法研究

发布时间：2017-12-07 03:29

  本文关键词：平面内可相交直线序列的遍历算法研究

  更多相关文章： ESP问题 Rubber-band算法 直线序列 凸多边形

【摘要】：ESP问题是计算几何中的经典问题。本文针对遍历平面内可相交直线序列的ESP问题进行研究,研究目标是要寻找一条从起点出发到达终点,且遍历给定直线序列中每条直线至少一次的最短路径。该问题是很多实际应用问题的抽象模型,针对该问题的研究,不仅具有重要的理论意义,而且也具有很高的实际应用价值。本文首先阐述了与求解问题相关的基础知识与求解方法,如点与直线的位置关系、直线与直线的位置关系、对称点、凸包、贪婪算法、Rubber-band算法等。在此基础上,通过构造给定直线序列的凸多边形,将平面内直线序列的遍历问题转化为平面内可相交线段序列的遍历问题。为此,本文详细论述了凸包构造方法以及依据凸包构造凸多边形的详细过程,给出了遍历给定可相交直线序列的最优遍历路径一定包含在所构造的凸多边形内部的研究结论及其严格的理论证明。接着,通过对比分析两种求解可相交线段序列的改进Rubber-band算法,选择交换访问顺序的处理方式,提出了一个时间复杂度为O(n2)的求解平面内可相交直线序列的最短遍历路径的算法。针对提出的算法,设计了相应的数据结构,并用C++程序设计语言实现了该算法。随机构造了大量测试数据,对所提出的算法进行了测试,并可视化算法运行结果,验证了算法的正确性和有效性。
【学位授予单位】：大连海事大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O18

【参考文献】

中国硕士学位论文全文数据库 前1条

1 谭锦彪;遍历平面内Partial-Order线段集的ESP求解算法研究[D];大连海事大学;2013年

，

本文编号：1261005