简单多边形中限于给定点集的最短路径求解研究

摘要

本文针对简单多边形中限于给定点集的最短路径问题进行研究，以期设计出一个求解算法，使得对于简单多边形中给定的点集以及起点s和终点t，能够找到一条从点s出发，中间经过给定点集中的某些点（也可能不经过），到达点t的最短路径。若这样的路径存在，则输出该路径;否则，报告出最短路径不存在的结论。该问题是TSP问题的变形问题，也是很多实际应用问题（如物流配送问题等)的抽象模型，因此研究该问题，不仅具有理论意义，而且具有很大的实际应用价值。
　　本文首先分析了简单多边形中点的可视性与最短路径计算的关联关系，然后通过分析简单多边形的顶点凸凹特性，将给定的简单多边形分割成若干个边链，求出边链对应的可视集，使得分布于每个可视集中的给定点之间相互可视。在此基础上，计算出关于给定点集的所有可视点对，最后运用Dijkstra算法计算出从点s到点t的最短路径。由于给定点集具有任意性，所以满足要求的最短路径未必存在，本文详细地分析了最短路径存在性，设计出了相应的判别算法以及最短路径的求解算法并加以分析。为了验证所设计算法的有效性，本文实现了所设计的算法并对算法运行结果做了较为详细的分析。实现结果表明，本文所设计的算法是高效的，在时间性能上优于已有的输出敏感度等算法。

目录

声明

摘要

第1章 绪论

1．1 研究背景与意义

1．2 国内外研究现状

1．3 研究内容

1．4 论文的组织结构

1．5 文章小结

第2章 相关基础知识

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

2．1．1 计算几何学

2．1．2 简单多边形

2．2 基本定义

2．3 最短路径的经典求解算法

2．4 本章小结

第3章 简单多边形中给定点集的可视点对计算方法

3．1 可视点对的判别方法

3．1．1 简单多边形顶点的凹凸性分析

3．1．2 不同可视集之间可视点对的计算

3．1．3 可视集内所有点的kd-树算法

3．2 给定点集中所有可视点对的计算

3．3 本章小结

第4章 限于给定点集的最短路径求解算法

4．1 算法概述

4．2 求解可视点对的算法流程

4．2．1 顶点位置的判断方法

4．2．2 可视点对的算法描述

4．3 最短路径的存在性分析

4．4 最短路径的算法流程

4．4．1 最短路径的存在性判断

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

4．4．3 最短路径求解算法的流程描述

4．5 算法时间性能的分析

4．6 本章小结

第5章 实验结果分析

5．1 测试数据

5．2 测试结果分析

5．3 本章小结

第6章 结论

6．1 研究工作总结

6．2 研究工作展望

参考文献

致谢

研究生履历