平面上几何物体序列遍历算法的优化研究

摘要

平面上几何物体序列遍历问题是计算几何学研究领域的核心问题，它不仅涉及可视性识别、最短路径计算、算法设计与优化等基础理论问题，而且也是机器人运动规划、无人机控制等一类实际应用问题的抽象模型，研究这些问题的简单、高效、实用的求解方法，不仅具有理论意义，而且也有很大的实际应用价值。
　　针对几何物体序列遍历问题的研究，虽然已经取得了一些成果，但这些成果一般还存在着数据结构复杂、迭代计算次数多，以及相交点处理时的算法退化等问题，围绕这些问题，本文展开求解算法的优化研究。
　　首先针对不相交线段序列遍历问题的算法优化进行了研究。针对Rubber-band算法在求解该遍历问题时所存在的重复迭代计算等缺陷，采用凸链分解与组合优化技术以及二分检索树存储结构，提出了O（nlog2n）时间复杂度的优化算法，降低了现有求解算法的时间复杂度，并构造测试数据对改进前后的求解算法做了运行时间性能对比分析。其次，针对可相交线段序列遍历问题，提出了跨线段处理技术，有效地解决了Rubber-band算法不能处理线段相交点的问题，并通过交换相邻线段访问顺序获得了更为精确的最短遍历路径，设计出了On2)时间复杂度的优化算法。在此基础上，针对直线序列遍历问题，采用构造扩大凸多边形的方法，将直线序列遍历问题转化为在凸多边形中求解可相交线段的最短路径遍历问题，设计出了O（n2）时间复杂度的最优遍历算法，并证明其为求解直线遍历问题的算法时间复杂度下界。最后，针对不相交凸多边形序列遍历问题，分析了凸多边形序列的几何特征，提出了正向划分多边形与逆向定位访问边的组合技术以及最短路径图结构，设计出了O（kn）时间复杂度的最优求解算法。
　　本文深入地研究了平面上几何物体序列的遍历问题，有效地解决了该领域研究中存在的一些问题，所提出的求解算法是到目前为止的最优解决方案，这些方法将有助于巡视员最短路径问题、机器人运动规划等实际应用问题的求解。同时，本文也提出了该研究领域有待进一步研究的问题。

目录

声明

摘要

第1章 绪论

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

1．2 国内外研究现状概述

1．2．1 巡视员路径问题

1．2．2 线段遍历问题

1．2．3 直线遍历问题

1．2．4 多边形遍历问题

1．2．5 存在问题与对策

1．3 主要研究内容

1．4 论文的章节结构

第2章 基于凸链分解与组合优化相结合的DS-DM算法

2．1 不相交线段序列遍历问题的描述

2．2 Rubber-band算法概述

2．2．1 Rubber-band算法的基本过程

2．2．2 Rubber-band算法的性能分析

2．3 DS-DM算法中的相关技术

2．3．1 局部收缩技术

2．3．2 局部路径优化技术

2．3．3 凸链分解与归并处理技术

2．3．4 局部最短路径归并过程示例

2．4 DS-DM算法设计与实现

2．4．1 DS-DM算法设计

2．4．2 DS-DM算法性能分析

2．4．3 算法实现与结果验证

2．5 运行结果对比分析

2．6 本章小结

第3章 基于跨线段处理技术的CS-CCH算法

3．1 可相交线段序列遍历问题的描述

3．2 Rubber-band算法的局限性

3．3 CS-CCH算法设计中的关键技术及其处理流程

3．3．1 跨线段处理技术

3．3．2 跨线段处理算法流程

3．4 CS-CCH算法及其性能分析

3．4．1 CS-CCH算法设计

3．4．2 CS-CCH算法性能分析

3．5 本章小结

第4章 直线序列遍历问题的最优遍历算法

4．1 直线序列遍历问题的描述

4．2 直线序列遍历问题的特征分析

4．3 直线序列遍历问题的求解方法

4．3．1 直线相交点集的凸包构造

4．3．2 凸包CL的扩大处理方法

4．4 L-CS算法的设计及其性能分析

4．4．1 L-CS算法设计

4．4．2 L-CS算法性能分析

4．5 本章小结

第5章 基于正向划分与逆向定位组合技术的DP-SPM算法

5．1 不相交凸多边形序列遍历问题的描述

5．2 最短遍历路径的几何特征分析

5．2．1 局部最优路径的特征分析

5．2．2 最优遍历路径的唯一性证明

5．3 最短遍历路径的构造技术

5．3．1 凸多边形的区域划分

5．3．2 最短路径图的构造

5．3．3 逆向求取各多边形的访问边

5．4 DP-SPM算法的设计及性能分析

5．4．1 DP-SPM算法处理流程

5．4．2 DP-SPM算法设计

5．4．3 DP-SPM算法性能分析

5．4．4 DP-SPM算法验证

5．5 本章小结

第6章 结论

6．1 论文工作总结

6．2 进一步研究工作

参考文献

攻读学位期间公开发表的论文

致谢

作者简介