基于凸链存储的可相交线段序列遍历算法研究

摘要

本文针对平面内可相交线段序列的最优遍历问题进行研究，目标是寻找一条从给定起点出发，依次遍历给定的可相交线段序列，最后到达终点的最短遍历路径。研究该问题的高效求解方法，不仅是一个理论问题，而且有助于机器人运动规划、无人机控制等一些实际应用问题的求解，因而具有较大的理论意义和实际应用价值。
　　本文详细分析了Rubber-band算法在求解可相交线段序列遍历问题时所出现的退化现象，以及局部最优路径迭代计算过程中存在的重复计算等问题，同时指出为处理线段相交点而提出的Rubber-band改进算法（抠点法）中存在着计算结果不精确的问题。为解决这些问题，本文在分析点与线段的位置关系的基础上，详细论述了穿越、完美反射，以及在线段端点处发生折射等局部最优路径收缩技术，提出了基于跨线段处理相交点与局部最优路径凸链存储结构的分段优化并加以组合的求解方法，设计出了一个时间复杂度为O(n*log2n)的求解可相交线段序列遍历问题的算法。该算法不仅有效地解决了退化问题，而且有效地减少了局部最优遍历路径收缩计算中的迭代次数。为验证所设计算法的有效性，本文设计出了相应的数据结构，用Java语言编程实现了所设计出的算法，随机构造了大量测试数据，并给出了算法运行的可视化结果。实验结果表明，本文所提出的算法，不仅有效地解决了Rubber-band算法的退化现象等问题，而且所计算出的最短遍历路径比采用抠点法的结果更为精确，是迄今为止解决可相交线段序列遍历问题的最优算法。

目录

声明

摘要

第1章 绪论

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

1．2 国内外研究现状

1．3 主要研究内容

1．4 论文组织结构

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

2．1 计算几何学的相关基础

2．1．1 计算几何学概述

2．1．2 基本定义

2．1．3 基础算法

2．2 经典算法

2．2．1 贪婪算法

2．2．2 分治算法

2．3 本章小结

第3章 遍历可相交线段序列的求解方法

3．1 问题描述

3．2 Rubber-band算法

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

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

3．3．2 抠点算法

3．3．3 跨线段处理法

3．3．4 可相交线段序列遍历问题的改进方法

3．4 本章小结

第4章 基于凸链存储的求解算法设计与实现

4．1 算法设计中的相关技术

4．1．1 初始化最短遍历路径

4．1．2 局部最优路径求解技术

4．1．3 凸链存储及其组合优化方法

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

4．3 算法设计中关键步骤的程序实现

4．4 本章小结

第5章 运行结果及分析

5．1 测试数据构造

5．2 实验结果及其分析

5．3 时间复杂度分析

5．4 本章小结

第6章 总结与展望

6．1 论文工作总结

6．2 进一步研究工作

参考文献

致谢