基于凸链存储的不相交线段序列的最优遍历算法

摘要

本文针对平面上不相交线段序列的最优遍历问题进行研究，目标是要寻找一条从给定起点出发，依次遍历每一条线段，最终到达给定终点的最优遍历路径。该问题也是一个欧几里德最短路径(ESP)问题，是计算几何领域的一个理论问题，也是很多实际应用问题的抽象模型。研究高效的求解该问题的方法，不仅具有重要的理论意义，而且也具有很高的实际应用价值。
　　本文在综述本领域相关研究成果的基础上，指出了运用Rubber-band算法求解该问题时可能产生振荡现象，导致算法时间复杂度较高等问题。为解决这些问题，本文首先研究了与线段遍历问题相关的一些经典问题，以及问题求解过程中需要用到的基础知识与基本算法，如确定点与线段的位置关系、直线与直线的位置关系、反射点与完美反射等。在此基础上，提出了采用凸链存储技术，结合Rubber-band算法，给出不相交线段序列最优遍历问题的求解思路，即利用凸链存储局部最优路径，并利用二分检索树实现路径点的更新，防止振荡现象的产生，减少迭代次数，提升算法效率的整体解决方案。为此，本文详细论述了凸链存储技术以及基于二分检索树的路径点更新技术，以及通过组合优化技术优化算法的迭代过程等，最终提出了一个时间复杂度为O(n*logn*logn)的平面内不相交线段序列最短遍历问题的求解算法，解决了Rubber-band算法的振荡现象以及算法时间性能差方面的问题。最后，针对本文所提出的算法，构造相应的测试数据，设计相应的数据结构并编程加以实现，分析算法的可视化运行结果，验证了算法的正确性和有效性。

目录

声明

摘要

第1章 绪论

1．1 研究背景与研究意义

1．2 课题描述

1．3 国内外研究现状

1．4 主要研究内容

1．5 论文组织结构

第2章 基础知识与经典算法概述

2．1 相关基础知识

2．1．1 计算几何学及其研究领域

2．1．2 几个经典问题

2．1．3 基本概念

2．2 相关基础算法

2．2．1 向量

2．2．2 线段相交性判定算法

第3章 ESP问题的经典求解方法

3．1 贪婪算法

3．2 分治算法

3．3 Rubber-band算法

第4章 算法设计与具体实现

4．1 经典Rubber-band算法的局限性

4．2 实现算法用到的数据结构

4．3 算法实现

第5章 算法验证与实验结果分析

5．1 构造测试数据

5．2 实验结果验证

5．3 算法时间复杂度验证

第6章 总结与展望

6．1 论文工作总结

6．2 未来展望

参考文献

致谢

研究生履历