CN111612257B - 基于空间归化的最短路径求解方法 - Google Patents

Abstract

本发明旨在提供基于空间归化的最短路径求解方法，包括以下步骤：将路网归化到矢量地理空间，获得起始地与目的地；以起始地与目的地连线中心为圆点，以起始地与目的地连线的长度为直径，构建包含起始地和目的地的第一圆；找出第一圆内所有的路径，并将这些路径进行拓扑构面；再次通过起始地与目的地连线与拓扑构面进行过滤，得到连接起始地与目的地的若干个多边形，并将这些多边形合并；合并后的多边形按照起始地、目的地将其切分为不同路径，选取路径较短者，即为获得的第一初始路径。本发明将弥补传统的A*算法估价函数选取困难问题，解决蚁群算法、遗传算法、神经网络算法等只能求解近似解无法得到数学最优解的难题。

Description

基于空间归化的最短路径求解方法

技术领域

本发明涉及计算机图形学、地理信息科学和逻辑学领域，具体涉及一种基于空间归化的最短路径求解方法。

背景技术

最短路径问题一直是计算机科学和地理信息科学中的经典问题，传统的类似问题解决多采用经典计算机算法如蚁群算法、A*算法、Dijkstra算法等，Dijkstra算法可以求解出数学最优解，但效率低；其他算法效率高，但却解算不出数学最优解，各种算法的解决思维不尽相同，因此很难兼顾优和准的问题，研究的方向也分为两个主流方向：Dijkstra算法的搜索效率优化和其他算法的精准度提升--至今没有学者能够统一两者，将其他算法的高效率与Dijkstra算法的数学严谨求解和二为一。

最短路径问题的解困扰计算机图形学、数学、逻辑学、地理信息科学等多个学科领域数十年，其研究解决的方向出现异化，需要效率难于顾及精准度，需要精准度难于顾及效率，因此该领域的研究走入死胡同至今无法解决这一矛盾。由简单数学分析可知，最短路径必然存在，其特点是路径上任意两点间的距离也是最短，是局部解和整体解得有机统一，因此研究自然分化为确保局部和确保整体两个方向。

由最短路劲的存在性和几何特点可知，问题最终就是长度比较，长度比较实质是线问题求解，而线是面的边界，因此可以通过将其他算法求解的问题归化到几何空间，通过几何手段完成样本空间的减缩优化，之后再利用Dijkstra算法求解最优解，最终实现所有最短路径算法在空间领域的统一，达到最短路径搜索“快”与“准”的统一。

发明内容

有鉴于现有技术的上述缺陷，为实现上述目的，本发明提供了一种基于空间归化的最短路径求解方法，以约束最短路径求解时解空间的发散问题，包括如下步骤：

S1、将路网归化到矢量地理空间，获得起始地与目的地；

S2、以起始地与目的地连线中心为圆点，以起始地与目的地连线的长度为直径，构建包含起始地和目的地的第一圆；

S3、找出第一圆内所有的路径，并将这些路径进行拓扑构面；

S4、再次通过起始地与目的地连线与步骤S3中得到的拓扑构面进行过滤，得到连接起始地与目的地的若干个多边形，并将这些多边形合并；

S5、将步骤S4中合并后的多边形按照起始地、目的地将其切分为不同路径，选取路径较短者，即为获得的第一初始路径。

作为可选的改进技术方案：步骤S3中还包括：只要路径在圆内或与圆有交叉，均筛选出来进行拓扑构面。

作为可选的改进技术方案：还包括步骤S6，以第一初始路径的长度为直径，将起始地和目的地的连线中心为圆点构建第二圆，将第二圆范围内过滤出来的路径进行拓扑构面，获取第二初始路径，将第二初始路径与第一初始路径进行比对，验算第一初始路径的准确性。

作为可选的改进技术方案：步骤S6还包括如下步骤：

S61、以第一初始路径的长度为直径，以起始地和目的地连线的中心为圆点，构建第二圆；

S62、找出第二圆圆内所有的路径，并将这些路径进行拓扑构面；

S63、再次通过起始地与目的地连线与步骤S62中得到的拓扑构面进行过滤，得到连接起始地与目的地的若干多边形，并将这些多边形合并；

S64、将步骤S63中合并后的多边形按照起始地、目的地将其切分为不同路径，选取路径较短者，即为获得的第二初始路径；

S65、将第二初始路径与第一初始路径进行比对，以验算第一初始路径的准确性。

作为可选的改进技术方案：步骤E2中还包括：只要路径在圆内或与第二圆有交叉，均筛选出来进行拓扑构面。

特别地，所述的步骤S2中圆的构建过程原因分析如下：

在步骤S2中通过构建以起始地与目的地连线长度为直径的第一圆，将问题从距离长度的一维空间拓展到二维空间，通过二维空间的范围概念约束可能解的空间，进而求出初始解，即第一初始路径。

步骤S3实现功能在于：

通过构面将问题的解空间拓展到二维面领域，合并多边形的目的为迅速找出可以包含起始地与目的地的面，进而找出可能的问题解，同时也为后续计算机的循环优化提供理论说明及初始值。

步骤S4与S5实现功能在于：

利用二维面是闭合线的概念，通过合并多边形将起始地、目的地、面、线结合在一起，通过闭合线找到初始解，进而为后期继续压缩解空间进而求解真值提供便利。

步骤S6实现功能在于：

通过步骤S5求的初始解是近似解，真值长度必然在两点连线和此近似解范围内。通过该近似解再次构建范围圆，由几何分析可知该范围圆内必然包含真值，进而再次约束和确保接真解求解的有效、快速、准确。

本发明将传统计算机图形学、逻辑学中对于最短路径求解统一归化到地理空间范畴，通过几何学、空间科学等相关技术，将参与解算的路径局限在小范围内。该范围与目标点连线线性相关，与全局样本数无关，因此也就解决了Dijkstra算法样本空间优化问题。借助升维降维思维，长度问题就是一维逻辑问题，而空间分析技术就是二维空间对象的逻辑判定技术，因此利用空间分析技术，将整体问题求解转化为局部问题求解进而求得最终解，也解决了其他算法如生物算法、智能算法只能求得局部最优解难于求解整体最优解的难题，是近年来将空间科学思维用于统一最短路径求解的新尝试。

最短路径是二维环境下的一维问题，因此其求解复杂度不低于样本数的二次方。对于二维环境下的一维问题，必然存在一维和二维的关联，这种关联就是隐含的二维环境下的对象拓扑关系。本发明构建范围圆，其实质就是将距离的解空间从一维拓展到约束的二维的过程，因此以升维降维思维为引导，借助拓扑关系这一维度之间的关联，有可能将二维问题一维化，进而快速求解出一维问题解。

本发明将弥补传统的A*算法估价函数选取困难问题，解决蚁群算法、遗传算法、神经网络算法等只能求解近似解无法完成数学最优解的难题。与专利ZL201510790636.5相比，本发明是该专利的前置，是将一维问题二维化过程中的全局二维化变革为局部二维化过程，优势在于不需要将全局样本进行二维拓扑构面，节约了大量的存储空间和计算资源，为实时最短路径分析的实现提供技术支持。

附图说明

图1为本发明的流程图。

图2为实施例中原始路线示意。

图3为实施例中以直接连线构建过滤范围圆的示意图。

图4为实施例中过滤得到的所有路径构面的示意图。

图5为实施例中通过连线过滤连接起始点多边形的示意图。

图6为实施例中找出构面后的多边形合并后导入空间坐标系后的矢量化图。

图7为实施例中第二圆压盖的道路区域示意图。

图8为实施例中第二圆的最优解示意图。

图9为实施例中的通过椭圆的外围圆来约束搜索范围的示意图。

图10至图12为通过椭圆来约束搜索范围的示意图。

图13为通过圆来约束搜索范围的示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述。

实施例一

参见图1，本实施例的基于空间规划的最短路径求解方法，其运行平台为PC上的Windows 7操作系统，地理信息系统平台为北京超图地理信息平台软件5.3.3版本，包括以下步骤：

S1、将路网归化到矢量地理空间，获得起始地与目的地，如图2。

S2、以起始地与目的地连线的中心为圆点，以起始地与目的地连线的长度为直径，构建包含起始地和目的地的第一圆；如图3。

S3、找出第一圆圆内所有的路径，并将这些路径进行拓扑构面，如图4；只要路径在圆内或与第一圆有交叉，均筛选出来进行拓扑构面。

S4、再次通过起始地与目的地连线与步骤S3中得到的拓扑构面进行过滤，得到连接起始地与目的地的若干个多边形，并将这些多边形合并，如图5；

S5、将步骤S4中合并后的多边形按照起始地、目的地将其切分为不同路径，选取路径较短者，即为获得的第一初始路径，如图6。由于多边形为闭合线，因此任意多边形上两点都可以有两条路连接，短的即为初始值。

上述选择最短路径可以采用现有技术完成最终最短路径的获取。

通过本实施例的方案，可以较快求解得到较佳的路径，整个过程包括先将地理空间矢量化，利用圆的易构建的特点，以及利用圆的二维平面的优势，筛选出一维的路径，再将一维的路径进行拓扑构面、升维形成二维封闭的路径块，再利用一维的起始地与目的地的连线与二维封闭的路径块进行重合、过滤，选出最短的路径，实现初始路径的求解；这样的求解过程不依赖于地图的更新与变化，只需要筛选出路径即可；而且筛选路径的过程也较为的方便，提升了求解的效率。

实施例二

本实施例为实施例一的优选方案；实施例一提供的求解方案是一个必要的技术方案，本实施例作为优选则是在该必要的技术方案的基础上，提供一个充分的技术方案。

S61、在实施例一中，已经求解得到了第一初始路径的长度，以此长度为直径，以起始地和目的地连线的中心为圆点，构建第二圆，如图7。

S62、找出第二圆圆内所有的路径，并将这些路径进行拓扑构面，如图7；只要路径在圆内或与第二圆有交叉，均筛选出来进行拓扑构面。

S63、再次通过起始地与目的地连线与步骤S62中得到的拓扑构面进行过滤，得到连接起始地与目的地的若干多边形，并将这些多边形合并；

S64、将步骤S63中合并后的多边形按照起始地、目的地将其切分为不同路径，选取路径较短者，即为获得的第二初始路径。由于多边形为闭合线，因此任意多边形上两点都可以有两条路连接，短的即为初始值，如图8。

S65、将第二初始路径与第一初始路径进行比对，以验算第一初始路径的准确性。

实施例一中得到的结果，可通过本实施例的再次计算验证，可以确认实施例一的计算结果确认无误，因此本实施例是一个充分的验证过程。

本实施例在进行计算时，是利用实施例一计算得到的第一初始路径的长度进行的计算，因此形成的第二圆可能大于第一圆，也可能等于第一圆，无论是何种情况，都是对于实施例一的一次充分验证。

同时第二圆与第一圆会存在一定的重合路径，因此第一圆的计算结果可以进行存储，在第二圆进行计算时调取使用。

在实施例一和实施例二中最短路径的计算，可以采用现有技术完成最终最短路径获取，如图8，图8中虚线为起始地和目的地之间的直线路径，而粗实线为计算出来的最短路径。采用的现有技术可以为专利号为ZL201510790636.5，当然不限于这套技术方案，只要能够完成最短路径获取的技术就行。

参见图9至图13，直接根据第一初始路径长度，可以通过椭圆来约束搜索范围，也可以通过椭圆的外围圆来约束，其中圆包括椭圆范围。本发明采用圆来约束，主要原因如下：

1、模型简单：只需要将初始路径长度和起目的地相关即可，而该圆的中心就是起目的地连线中心，而半径为初始路径长度一半，满足了用距离和起始点约束的目标；

2、便于数学求解：椭圆不仅需要求解长短轴和焦点，而且在坐标系统之间转换时，特别是旋转计算时，其求解较为复杂，而圆仅需要知道圆心即可，不存在图形旋转影响。

3、搜索精准：原始最简单的图形，在任意平台都能够无损转换，而对于椭圆，在不同平台之间转换时必然出现精度损失，如图11和图12所示。。

对空间搜索的精度影响较大，容易出现检索遗漏的可能，如下图11-图12所示，在新平台搜索时左侧的线将遗漏。建立椭圆找出最短路径的方法可以参考申请号为CN201910314226.1的中国发明专利申请。

参见图13，AOB是直径，O为圆心，直径长度多维初始路径：

AB<CA+CB

CA<AO+CO

CB<BO+CO

AO+CO<DO+CO＝L1

BO+CO<EO+CO＝L1

所以CA+CB<2*L1

根据圆的属性可知，CA+CB＝CA+AF>L1；

也就是说，该圆上面任意一点到起目的地的距离不超过初始距离的两倍2*L1且不小于L1，即该圆任一点到起目的地距离范围为[L1，2*L1)，解空间的下限为L1，也就是说圆外的距离必然超过该值，则意味着最优解必然在该圆范围内。通过初始解和该圆这样就把原来解空间从[L0，+∞)进行了降维约束到[L0，2*L1)，包括区间[L0，L1]即两点间连线和初始值之间,后期只需在该范围内进行路径求解必然包括最优解。

本发明未详述之处，均为本领域技术人员的公知技术。

以上详细描述了本发明的较佳具体实施例。应当理解，本领域的普通技术人员无需创造性劳动就可以根据本发明的构思作出诸多修改和变化。因此，凡本技术领域中技术人员依本发明的构思在现有技术的基础上通过逻辑分析、推理或者有限的实验可以得到的技术方案，皆应在由权利要求书所确定的保护范围内。

Claims (3)

1.基于空间归化的最短路径求解方法，其特征在于，包括以下步骤：

S1、将路网归化到矢量地理空间，获得起始地与目的地；

S2、以起始地与目的地连线中心为圆点，以起始地与目的地连线的长度为直径，构建包含起始地和目的地的第一圆；

S3、找出第一圆内所有的路径，并将这些路径进行拓扑构面；

S4、再次通过起始地与目的地连线与步骤S3中得到的拓扑构面进行过滤，得到连接起始地与目的地的若干个多边形，并将这些多边形合并；

S5、将步骤S4中合并后的多边形按照起始地、目的地将其切分为不同路径，选取路径较短者，即为获得的第一初始路径；

S6、以第一初始路径的长度为直径，以起始地与目的地连线中心为圆点构建第二圆，将第二圆范围内过滤出来的路径进行拓扑构面，获取第二初始路径，将第二初始路径与第一初始路径进行比对，验算第一初始路径的准确性；

步骤S6还包括如下步骤：

S61、以第一初始路径的长度为直径，以起始地与目的地连线的中心为圆点，构建第二圆；

S62、找出第二圆圆内所有的路径，并将这些路径进行拓扑构面；

S63、再次通过起始地与目的地连线与步骤S62中得到的拓扑构面进行过滤，得到连接起始地与目的地的若干多边形，并将这些多边形合并；

S64、将步骤S63中合并后的多边形按照起始地、目的地将其切分为不同路径，选取路径较短者，即为获得的第二初始路径；

S65、将第二初始路径与第一初始路径进行比对，以验算第一初始路径的准确性。

2.如权利要求1所述的最短路径求解方法，其特征在于，步骤S3中还包括：只要路径在圆内或与圆有交叉，均筛选出来进行拓扑构面。

3.如权利要求1所述的最短路径求解方法，其特征在于，步骤S62中还包括：只要路径在圆内或与第二圆有交叉，均筛选出来进行拓扑构面。

Images