多边形中给定点集的无交叉Hamilton回路求解研究

摘要

多边形中给定点集的无交叉Hamilton回路求解问题，是经典的Hamilton回路的一个变形问题，其研究涉及到计算几何，图论等领域，具有较高的理论价值。从应用角度看，在机器人学、游戏产业、海上搜救、军事作战、物流规划、交通规划、行车导航、社交网络、物联网与实物搜索、无人机控制等领域，针对该问题的研究也具有很大的价值。
　　本文针对平面上简单多边形中给定点集的无交叉Hamilton回路的求解问题进行研究。首先论述了与该问题求解相关的基础知识，如Hamilton路径、Hamilton回路、测地线凸包、简单路径等概念，以及它们在多边形搜索研究中的拓展含义。然后，本文对现有的相关研究进行了概括与分析，如对特定类型的图中Hamilton路径及回路的求解、测地线凸包的构造、多边形内简单路径的求解等。由于针对多边形内给定点集的无交叉Hamilton回路的求解问题，迄今为止没有相对成功的可行算法，且该问题又有别于图的Hamilton回路问题，因此本文的研究致力于寻找需要被遍历的给定点集的潜在顺序，并在包含所有点的多边形中预先计算出一个具有部分点的初始回路，利用初始回路确定部分点的潜在顺序，然后设法将剩余点逐个插入到初始回路上，以便最终找到该问题的多项式时间求解算法。本文给出了求解该问题的一个有效算法，并对其性能进行了详细的分析。
　　最后，本文编码实现了所提出求解算法，并以点的个数小于100的情形，给出了相应的运行结果。实践表明，本文所设计的算法是可行且高效的。

目录

声明

摘要

第1章 绪论

1．1 研究背景与意义

1．2 国内外研究现状

1．3 研究内容

1．4 论文的组织结构

第2章 相关基础知识

2．1 概述

2．2 基本定义

2．3 相关经典问题及算法

2．3．1 凸包及测地线凸包的求解算法

2．3．2 多边形中给定点集的简单路径求解方法

2．3．3 多边形的凸划分

2．4 本章小结

第3章 无交叉Hamilton回路求解算法的设计

3．1 问题描述

3．2 初始回路

3．2．1 初始回路的求解方法

3．2．2 初始回路求解方法的性能分析

3．3 剩余点的插入方法

3．4 算法设计及其复杂性分析

3．5 本章小结

第4章 算法实现及其结果分析

4．1 算法实现与测试

4．2 实验结果及分析

第5章 总结与展望

5．1 论文工作总结

5．2 进一步研究工作

参考文献

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

致谢