一种基于等高线思维的哈密顿路径求解方法

摘要

本发明涉及计算机图形学与地理信息科学领域，具体公开了一种基于等高线思维的哈密顿路径求解方法，包括以下步骤：S1、获取节点样本数据；S2、构建节点样本的外包图形；S3、分别以每一节点为中心构建泰森多边形，形成泰森多边形网；S4、以边界线为基准，搜索与边界线邻接的泰森多边形；S5、搜索与泰森多边形环邻接的泰森多边形；S6、重复S5中的搜索步骤，直至搜索结果覆盖所有的泰森多边形；S7、以其中一泰森多边形环中的任一节点为起始点，依次连接该泰森多边形环内的所有节点；S8、重复S7中的连接步骤，结果即为哈密顿路径的解。本发明的一种基于等高线思维的哈密顿路径求解方法，原理简单，能够有效降低处理的难度、成本和时间，提高求解效率。

说明书

技术领域

本发明涉及计算机图形学与地理信息科学领域，尤其涉及一种基于等高线思维的哈密顿路径求解方法。

背景技术

哈密顿路径问题求解方法是数学与计算机图形学的研究热点，在物流、旅游、军事等领域具有巨大应用潜力。但传统的哈密顿路径问题的解决方法多从图形学及数学角度进行，效率和适用范围受到很大限制，在哈密顿路径问题求解时样本数据达到一定量后，计算机和传统算法将无能为力。

哈密顿路径问题求解方法属于必经结点的路径搜索问题，鉴于问题求解的特殊性，如必经结点的先后优化组合、空间相对位置等未作考虑，因此鲜有学者将传统的空间路径搜索方法用于哈密顿路径求解领域以降低处理的难度、成本和时间。

发明内容

本发明旨在至少解决上述所提及的技术问题之一，提供一种基于等高线思维的哈密顿路径求解方法，原理简单，能够有效降低处理的难度、成本和时间，提高求解效率。

为了实现上述目的，本发明采用的技术方案为：一种基于等高线思维的哈密顿路径求解方法，包括以下步骤：

S1、获取节点样本数据；

S2、构建节点样本的外包图形，以将所有节点覆盖在外包图形中；

S3、分别以每一节点为中心构建泰森多边形，形成泰森多边形网，并将外包图形的边线作为泰森多边形网的边界线；

S4、以边界线为基准，搜索与边界线邻接的泰森多边形，并将搜索结果合并得到泰森多边形环；

S5、搜索与泰森多边形环邻接的泰森多边形，并将搜索结果合并得到新的泰森多边形环；

S6、重复S5中的搜索步骤，直至搜索结果覆盖所有的泰森多边形，以得到若干泰森多边形环；

S7、以其中一泰森多边形环中任一节点为起始点，依次连接该泰森多边形环内的所有节点，并将最后一个连接的节点与相邻的另一泰森多边形环内的节点相连；

S8、重复S7中的连接步骤，直至将所有泰森多边形环内的节点依次连接，以及相邻的泰森多边形环连接，结果即为哈密顿路径的解。

优选的，所述外包图形为矩形或者圆形。

优选的，所述外包图形大于最小外包图形，以使得所有的节点样本未落在外包图形的边线上。

优选的，所述步骤S7中，以最外围的泰森多边形环中的任一节点作为起始点。

优选的，所述步骤S7中，同一泰森多边形环中的节点在连接时，依次连接相邻的节点。

优选的，所述步骤S7中，若其中一节点与多个节点相邻，将所述其中一节点与任一相邻的节点进行连接。

优选的，所述步骤S7中，其中一泰森多边形环的最后一个连接的节点与相邻的另一多边形环中相邻的任一节点连接。

优选的，上述任一的求解方法用于平面求解。

有益效果是：与现有技术相比，本发明的一种基于等高线思维的哈密顿路径求解方法通过将节点的连接问题拓展到面的临界领域，实现点点连接问题的拆维解决，本发明的求解方法是哈密顿环问题在升维降维引导下的空间解，是将数学逻辑思维、通行性思维和空间科学思维相结合解决空间问题的新思路，原理简单，能够有效降低处理的难度、成本和时间，提高求解效率，具有重要的学术意义，在国民经济多个领域都具有巨大应用潜力。

附图说明

以下结合附图对本发明的具体实施方式作进一步的详细说明，其中：

图1为获取节点样本构建外包图形后的示意图；

图2为图1中的节点样本构建泰森多边形网后的示意图；

图3为搜索泰森多边形环的示意图；

图4为泰森多边形环搜索完成的示意图；

图5为泰森多边形环中的节点依次连接得到哈密顿路径解的示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明的一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

需要说明的是，当组件被称为“固定于”另一个组件，它可以直接在另一个组件上或者也可以存在居中的组件。当一个组件被认为是“连接”另一个组件，它可以是直接连接到另一个组件或者可能同时存在居中组件。当一个组件被认为是“设置于”另一个组件，它可以是直接设置在另一个组件上或者可能同时存在居中组件，当部件被称为“设置在中部”，不仅仅是设置在正中间位置，只要不是设置在两端部都属于中部所限定的范围内。本文所使用的术语“垂直的”、“水平的”、“左”、“右”以及类似的表述只是为了说明的目的。

除非另有定义，本文所使用的所有的技术和科学术语与属于本发明的技术领域的技术人员通常理解的含义相同。本文中在本发明的说明书中所使用的术语只是为了描述具体的实施例的目的，不是旨在于限制本发明。本文所使用的术语“及/或”包括一个或多个相关的所列项目的任意的和所有的组合。

升维代表无限可能，降维代表问题简化求解，点点连接问题的难点就在于解的发散同时没有有效约束解的空间，而空间问题不是传统逻辑思维的拓展，因此不借助升维降维思维很难求解多维问题。

由基本常识可知，点的连线属于一维问题，线分布方向在二维，因此该问题是一维问题在二维空间的约束求解，具有一定的数学难度。几何原理告诉我们，环其实就是闭合线，因此二维空间的点线面具有一定的隐性空间关系。

哈密顿路径的特性是点点相连只经过一次，这与二维环境下多边形的依次邻接概念一致，因此可以通过多边形邻接关系约束连接次数。点是零维元素，直接拓展到二维就是点的势力范围概念：泰森多边形。基于此本发明引入泰森多边形构建，解决点势力范围构建及多边形邻接关系的隐形构建。而对于约束后的点点相连，则由线闭合是面来完成。通过外围先构建首级闭合环，之后再由外至内依次构建内环，直到将所有的泰森多边形都搜索完毕。其利用的思维类似于等高线的闭合代表地面势力范围，之后将每个环内的节点相连，达到环环相连点点相连的目的，进而实现最终问题求解。

上述方法利用两个基本原则：面的邻接和闭合的基本概念，通过将问题剖析分解，引入等高线代表地面势力范围的思维，将点点连接问题拓展到面的邻接，实现了哈密顿路径问题求解

具体的，为了实现上述目的，本发明采用的技术方案为：一种基于等高线思维的哈密顿路径求解方法，包括以下步骤：

S1、获取节点样本数据；

S2、构建节点样本的外包图形，以将所有节点覆盖在外包图形中；

S3、分别以每一节点为中心构建泰森多边形，形成泰森多边形网，并将外包图形的边线作为泰森多边形网的边界线；

S4、以边界线为基准，搜索与边界线邻接的泰森多边形，并将搜索结果合并得到泰森多边形环；

S5、搜索与泰森多边形环邻接的泰森多边形，并将搜索结果合并得到新的泰森多边形环；

S6、重复S5中的搜索步骤，直至搜索结果覆盖所有的泰森多边形，以得到若干泰森多边形环；

S7、以其中一泰森多边形环中任一节点为起始点，依次连接该泰森多边形环内的所有节点，并将最后一个连接的节点与相邻的另一泰森多边形环内的节点相连；

S8、重复S7中的连接步骤，直至将所有泰森多边形环内的节点依次连接，以及相邻的泰森多边形环连接，结果即为哈密顿路径的解。

更为具体的，求解方法为：如图1所示，获取节点样本的数据，并构建节点样本的外包图形，其中，外包图形可以为矩形或者圆形，优选的，本实施方式中采用矩形作为外包图形，以将所有的节点样本被覆盖在外包矩形中，且矩形的面积大于最小外包矩形的面积，以使得节点样本在矩形的内部，且没有任何节点落在矩形的边界线上，如图2所示，分别以每一节点为中心构建泰森多边形，形成泰森多边形网，并将矩形的边线作为泰森多边形网的边界线，如图3所示，以边界线为基准，搜索与边界线邻接的泰森多边形，即与边界线直接相连的泰森多边形，并将搜索结果合并，得到由若干泰森多边形构造的泰森多边形环，然后搜索与泰森多边形环邻接的泰森多边形，并将搜索结果合并，得到新的泰森多边形环，以最内层的泰森多边形环为基准，重复上述的搜索步骤，直至搜索结构覆盖所有的泰森多边形，如图4所示，以得到多个泰森多边形环，其中在一些实施方式中，搜索至最后，会在泰森多边形网络的中部存在一个或多个泰森多边形不能构成环状的情况，则将这些泰森多边形作为最内层的泰森多边形离散单元，如图5所示，以其中一泰森多边形环中任一节点为起始点，依次连接该泰森多边形环内的所有节点，并将最后一个连接的节点与相邻的另一泰森多边形环内的节点相连，相邻的另一泰森多边形环中，以与其中一泰森多边形相连的节点作为起始点，依次连接另一泰森多边形环中的所有节点，重复上述的节点连接步骤，直至将所有泰森多边形环内的节点依次连接，以及相邻的泰森多边形环连接，结果即为哈密顿路径的解，其中，在存在有泰森多边形离散单元的情况时，将所有的泰森多边形环中最后连接的节点依次连接泰森多边形离散单元中剩余的泰森多边形的节点，从而得到哈密顿路径的解，且在与泰森多边形离散单元中的节点连接时，按照距离最近原则依次连接，优选的，在进行节点的连接时，以最外层的泰森多边形环中的任一节点作为起始点，由外至内依次将多层泰森多边形环进行连接，在同一泰森多边形环中的节点进行连接时，依次连接相邻的节点，其中节点的相邻原则以泰森多边形的临近原则为基准，若存在一个节点与多个节点相邻的情况，将该节点与任一节点进行连接，其中一泰森多边形环内最后连接的节点与相邻另一泰森多边形环的节点进行连接时，选择另一泰森多边形环中与之相邻的一节点进行连接，若存在与多个节点相邻的情况，则选择任一相邻的节点进行连接。

优选的，上述求解方法可以用于平面求解。

本发明的通过将节点的连接问题拓展到面的临界领域，实现点点连接问题的拆维解决，本发明的求解方法是哈密顿环问题在升维降维引导下的空间解，是将数学逻辑思维、通行性思维和空间科学思维相结合解决空间问题的新思路，具有重要的学术意义，在国民经济多个领域都具有巨大应用潜力。

以上实施例仅用以说明本发明的技术方案而并非对其进行限制，凡未脱离本发明精神和范围的任何修改或者等同替换，其均应涵盖在本发明技术方案的范围内。