一种基于升维降维思维的最短哈密顿路径求解方法

摘要

本发明涉及计算机图形学与地理信息科学领域，具体公开了一种基于升维降维思维的最短哈密顿路径求解方法，其特征在于，包括以下步骤：S1、获取节点样本的哈密顿路径初始解；S2、构建过滤因子，通过过滤因子对哈密顿路径初始解上的节点进行过滤；S3、重复步骤S2中的过滤步骤，直至过滤前后节点的位置不发生改变，所得的结果为最短哈密顿路径。本发明的一种基于升维降维思维的最短哈密顿路径求解方法，原理简单，能够有效降低处理的难度、成本和时间，提高哈密顿路径最优解的求解效率。

说明书

技术领域

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

背景技术

TSP问题是二十一世纪七大世纪难题的首位，已经被证明为完全NP问题，其求解过程的复杂主要原因如下：一是目标点的分布存在在二维空间，具有两个维度，而两点之间的最短路径也是二维分布，也就是说该问题是两个二维问题的纠缠，传统的算法可以解决两点间最短路径，但对于多维纠缠的TSP问题难于解决。由简单分析可知，两点间最短路径的计算复杂度无论如何优化，都不能低于二维，也就是节点数的二次方；而TSP问题是二维纠缠问题，其优化的最理想状态为二维的复合即节点数的四次方，这也是为什么人类难于解决TSP问题的直接原因。

TSP问题是哈密顿环的最优搜索，哈密顿环是首尾相连的哈密顿路径特例，也就是说最短哈密顿路径是TSP问题的通解。因此，急需提供一种求解方法，以降低最短哈密顿路径的求解难度，提高求解效率。

发明内容

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

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

S1、获取节点样本的哈密顿路径初始解；

S2、构建过滤因子，通过过滤因子对哈密顿路径初始解上的节点进行过滤，过滤因子的构建包括以下步骤：

S21、获取与过滤节点在哈密顿路径初始解上相邻接的两个节点作为基准节点，并通过连接过滤节点与两基准节点构建基准三角形；

S22、获取与过滤节点相邻的另外两个节点作为对比节点，两对比节点为哈密顿路径初始解上相邻接的两个节点，并通过连接过滤节点与两对比节点构建对比三角形；

S23、计算基准三角形中过滤节点的两邻边之和减去对边的长度，得到结果为L1，以及计算对比三角形中过滤节点的两邻边之和减去对边的长度，得到结果为L2；若L1＜L2，则保留基准三角形中的两邻边以及对比三角形中的对边，删除基准三角形中的对边以及对比三角形中的两邻边，若L1＞L2，则保留基准三角形中的对边以及对比三角形中的两邻边，删除基准三角形中的两邻边以及对比三角形中的对边；

S3、重复步骤S2中的过滤步骤，直至过滤前后节点的位置不发生改变，所得的结果为最短哈密顿路径。

优选的，所述步骤S2中，以哈密顿路径初始解的第二个节点作为起始点，依次过滤至哈密顿路径初始解的倒数第二个节点。

优选的，所述步骤S22中，以各节点为中心分别构建泰森多边形，根据泰森多边形临近原则，确定与过滤节点相邻的另外两个节点。

优选的，除与过滤节点在哈密顿路径初始解上相邻接的两个节点外，若存在另外两个以上的节点与过滤节点相邻，选择任意两个哈密顿路径初始解上相邻接的节点与过滤节点构造对比三角形。

优选的，若过滤节点能构造多个对比三角形，计算该过滤节点每一个对比三角形的L2，选取该过滤节点中L2的最小值与该过滤节点的L1进行对比。

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

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

附图说明

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

图1为本发明的一种基于升维降维思维的最短哈密顿路径求解方法的流程图；

图2为节点样本获取哈密顿路径初始解后的示意图

图3为图2中的过滤节点处的放大示意图；

图4为图3中的过滤节点构建基准三角形后的示意图；

图5为图4中的过滤节点构建对比三角形后的示意图；

图6为图5中的基准三角形删掉两邻边后的示意图；

图7为图6中的对比三角形删掉对边后的示意图；

图8为图1中的哈密顿路径初始解优化后的示意图。

具体实施方式

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

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

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

高维度问题的解算由数学原理可知，当问题解算空间拓展到更高维度，则解空间存在无限可能，如平面的线函数，在三维空间是一个面，而面包含无数个线，这就是TSP等高维问题求解难的根本所在。

由对数指数概念可知，对于多元高次空间，高维空间问题可以通过数学方法进行降维，进而才有解算问题的可能。基于此首先是对问题在高维空间环境下的特点，在将解决思路拓展到多维空间的同时，留意其更加普遍性的介于低维与高维之间的数学联系，以便在适当的时候对问题降维缩小解存在的维度空间，最终实现问题求解。

最短哈密顿路径的特点是经过指定节点且只经过一次，同时要求该路径的长度在所有可能路径中最小。基于此可以将问题分解为两个必要条件：必经问题和最短问题，结合升维降维思维，利用点范围分析模式，可以通过现有的方法实现一次性必经问题的求解；对于最短问题，由常识可知路径较短意味着至少有两条路径，而两条路径最少需要三个点，也就是说最优解中任意临近三点其连线都为最小。至此问题已经实现维度拆分，也就是说以上两个条件是该问题的充分必要条件，求解问题的关键就是保证解满足如上两个条件。

如图1至图8所示，本申请的一种基于升维降维思维的最短哈密顿路径求解方法，包括以下步骤：

S1、获取节点样本的哈密顿路径初始解；

S2、构建过滤因子，通过过滤因子对哈密顿路径初始解上的节点进行过滤，过滤因子的构建包括以下步骤：

S21、获取与过滤节点在哈密顿路径初始解上相邻接的两个节点作为基准节点，并通过连接过滤节点与两基准节点构建基准三角形；

S22、获取与过滤节点相邻的另外两个节点作为对比节点，两对比节点为哈密顿路径初始解上相邻接的两个节点，并通过连接过滤节点与两对比节点构建对比三角形；

S23、计算基准三角形中过滤节点的两邻边之和减去对边的长度，得到结果为L1，以及计算对比三角形中过滤节点的两邻边之和减去对边的长度，得到结果为L2；若L1＜L2，则保留基准三角形中的两邻边以及对比三角形中的对边，删除基准三角形中的对边以及对比三角形中的两邻边，若L1＞L2，则保留基准三角形中的对边以及对比三角形中的两邻边，删除基准三角形中的两邻边以及对比三角形中的对边；

S3、重复步骤S2中的过滤步骤，直至过滤前后节点的位置不发生改变，所得的结果为最短哈密顿路径。

具体的，如图2所示，本申请中节点样本的数量可以为1260个，其中，本申请获取哈密顿初始解的方法可以采用现有技术中公开的获取方法，优选采用公开号为CN110887502B中的搜索方法，其哈密顿路径初始解的获取步骤具体为：

S11.获取节点样本数据，并通过各节点构建泰森多边形；

S12.判断起点节点与终点节点是否为同一节点，若不是则直接进行S13处理；

S13.以起点节点所在的泰森多边形为起始，搜索与该泰森多边形相邻的泰森多边形，然后将相邻泰森多边形中依次相邻的泰森多边形合并成第一合并多边形，然后进行S14处理，若搜索的相邻的泰森多边形中有不相邻孤立的泰森多边形，则对应将不相邻孤立的泰森多边形进行S15处理；

S14.以第一合并多边形为基础，搜索与第一合并多边形相邻的未处理泰森多边形，然后将相邻的未处理泰森多边形中依次相邻的未处理泰森多边形合并成第二合并多边形，若相邻的未处理泰森多边形中有不相邻孤立的泰森多边形，则对应将不相邻孤立的未处理泰森多边形进行S15处理，直到处理完所有泰森多边形；

S15.若起点节点所在的泰森多边形的相邻的泰森多边形中或某个合并多边形的相邻未处理泰森多边形中有不相邻孤立的泰森多边形，则将该孤立的泰森多边形合并到相邻共边的某个合并多边形中，确保除起点节点所在的泰森多边形和终点节点所在的泰森多边形外的各合并多边形都有且仅有两个临近的合并多边形；

S16.通过各节点构建Denaulay三角形，将Denaulay三角形中两个顶点不在同一个合并多边形中的边删除；

S17.若合并多边形中剩余的边线不存在节点度大于等于三的情况，则进行S18处理，否则按照图形闭合两边原则选取较短边；

S18.将每个合并多边形中边线首尾相连，连线短者即为结果：

在获取节点样本的哈密顿路径初始解后，构建过滤因子，通过过滤因子对哈密顿路径初始解上的节点进行过滤，其中需要过滤的节点为过滤节点，具体的，如图3和图4所示，图中的1代表过滤节点，2、3、4、5分别代表与过滤节点相邻的四个节点，获取与过滤节点在哈密顿路径初始解上相邻接的两个节点2、3作为基准节点，并通过连接过滤节点与两基准节点构建基准三角形，并如图5所示，获取与过滤节点相邻的另外两个节点4、5作为对比节点，两对比节点为哈密顿路径初始解上相邻接的两个节点，并通过连接过滤节点与两对比节点构建对比三角形，在对节点进行过滤时，由于起点节点与终点节点未能获取在哈密顿路径初始解上相邻接的两个节点，因此无需对起点节点和终点节点进行过滤，以哈密顿路径初始解的第二个节点作为起始点，依次过滤至哈密顿路径初始解的倒数第二个节点，构建基准三角形和对比三角形后，计算基准三角形中过滤节点的两邻边之和减去对边的长度，得到结果为L1，以及计算对比三角形中过滤节点的两邻边之和减去对边的长度，得到结果为L2，其中，邻边为与过滤节点相连的连线，对边为与过滤节点不相连的连线，在确定邻近节点时，以各节点为中心分别构建泰森多边形，根据泰森多边形临近原则，确定与过滤节点相邻的另外两个节点，如图5所示，L1＝L12+L13-L23，L2＝L14+L15-L45，若L1＜L2，则保留基准三角形中的两邻边以及对比三角形中的对边，删除基准三角形中的对边以及对比三角形中的两邻边，若L1＞L2，则如图6，保留基准三角形中的对边，删除基准三角形的两邻边，以及如图7所示，保留对比三角形中的两邻边，删除对比三角形中的对边，若出现L1＝L2的情况，可以优选为保留基准三角形中的两邻边以及对比三角形中的对边，删除基准三角形中的对边以及对比三角形中的两邻边，重复上述的过滤步骤，直至过滤前后节点的位置不发生改变，如图8所示，所得的结果为最短哈密顿路径，在构建对比三角形时，若除与过滤节点在哈密顿路径初始解上相邻接的两个节点外，存在另外两个以上的节点与过滤节点相邻，选择任意两个哈密顿路径初始解上相邻接的节点与过滤节点构造对比三角形，优选的，若过滤节点能构造多个对比三角形，计算该过滤节点每一个对比三角形的L2，选取该过滤节点中L2的最小值与该过滤节点的L1进行对比，若除与过滤节点在哈密顿路径初始解上相邻接的两个节点外，不存在另外两个哈密顿路径初始解上相邻接的节点与过滤节点相邻，则无需多过滤节点进行过滤。

本申请通过构建过滤因子对节点进行过滤时，节点样本整体的连续性没有被破坏，从而使得最短哈密顿路径充要条件中的第一个约束条件没有被破坏，但哈密顿路径的整体长度减小。

优选的，本申请的求解方法可以用于平面求解。

在本申请方案中通过泰森多边形将点邻接的问题拓展到面领域，实现了问题求解中维度的升级。此外借助面邻接特性，将点之间的连接可能性从原来的N-1降低到临近泰森多边形的个数。按照原来的可能性分析，传统模式下两点之间的连接最多由N！种可能，则N个节点连接的可能性为N！*N！，也就是说通过拓扑邻接关系将原来的复杂度为O(N！*N！)的问题降低到N，使得问题的快速求解成为可能，通过将节点的连接问题拓展到面的临界领域，实现点点连接问题的拆维解决，本发明的求解方法是哈密顿路径问题在升维降维引导下的空间解，是将数学逻辑思维、通行性思维和空间科学思维相结合解决空间问题的新思路，具有重要的学术意义，在国民经济多个领域都具有巨大应用潜力。

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