一个可以寻找更好路线的快速算法

一个可以寻找更好路线的快速算法1摘要最短路径问题是可以适用于各种领域的其中最基本的问题之一，并且它和路线导航系统有着密切的关系。本文调查两端最短路径算法的问题,提出了双向A *算法基于一种新方法。该算法不仅适用于寻找最短的路线也适用于寻找出更好的路线。我们通过实验将它们应用于实际的道路网络以讨论这些算法的效率和性能。2.介绍提出减少必要的时间到目的地是一个路线导航系统所需的最基本的功能。从保持信息在起源地和目的地之间的一个适当路线上的困难度来说，以及利用如交通流这样的动态信息的可能性，这个问题必须有用户在其每次请求的时候来解决。以这种方式，它以产生更有效的方法来搜索适当路径上的道路网络是重要的。该主题概括为上图的两端最短路径问题，这是问题找到从s的最短路径t上有向图G =（V，E）。这样，一个边的长度（U，V）中E为L（U，V），其中原点s和目的地t是已经给出。因为可以广泛应用，所以这种问题已经研究了在各种领域进行很长一段时间。例如使用Dijkstra方法是一种传统的算法针对此问题。此外，在A*算法和双向搜索算法是众所周知的基于AI（人工智能）搜索技术的算法。本文对这些算法不仅考虑从施加他们到的点的道路网络上的两个末端最短路径问题，还提出在双向A*的基础上根据技术转换的一个新算法，即改进算法的Dijkstra方法。本算法不仅适用于发现最短的路线，而且适用于寻找更好的路由。即次优路由作为候选，含有不是最短，但较少的圈数的路径，例如替代路线。效率和这些算法的性能是通过使用实际的道路数据的实验讨论。2.1 Dijkstra算法方法Dijkstra方法是一个基本的算法解决最短路径问题。虽然原算法通过迪杰斯特拉是为单原点到所有目的地的问题。它几乎适用于所有二端的问题。以下是使用Dijkstra方法的用于两终端问题的步骤。1.设S是空集，设Ps（S）为到一个顶点U的点集合，除了原点S其他都是+。令Ps（S）是零。2.找到在VS中有最小距离的顶点v0并添加到VS。如果V0等于T，就暂停寻找。3.对于所有的顶点V，使得（v0，v）在E上，如果Ps（v0）+L（v0，v）小于Ps（v），就用从s的路径替换到v从s的路径V0和边缘（v0，v）中，并让Ps（v0）为Ps（v0）+ L（v0，v）。4.进入第2步。在此算法中，每个顶点保证都可以从S的最短路径中被搜索，并且其值表示该路径的长度。当顶点被添加至S，如果从S当前的最短路径比保持了顶点的所有其他路径更短，这表明这些顶点，从S到它们的实际最短路径已经被决定了。以这种方式进行Dijkstra方法查找，以便从S到顶点的路径长度最短路径从S到一个顶点。这表明如果G是均匀的，使用此算法的搜索区域就是与S的圆为中心。Dijkstra方法经常用于具有搜索在所有的方向无关的地方两终端最短路径问题的缺点。2.2 A *算法在A*算法找到最短路径从S到T其实更有效，从各顶点的最短路径长度的试探估计t，而t是已知的，并且它必须小于实际最短路径的长度。令Hs（v）表示这个估计的顶点v。那么A *算法的步骤描述如下：1.设S是空集，设Ps（S）为到一个顶点U的点集合，除了原点s其他都是+。令Ps（S）是零。2.找到在vS中有最小距离的顶点v0并添加到VS。如果v0等于T，就暂停寻找。3.对于所有的顶点V，使得（v0，v）在E上，如果Ps（v0）+L（v0，v）小于Ps（v），就用从s的路径替换到v从s的路径v0和边缘（v0，v）中，并让Ps（v0）为Ps（v0）+L（v 0，v）。4.进入第2步。在该算法中，Ps（v）也表示从s到v临时最短路径的长度。因此，A*算法被认为是从s到t的最短路径的顶点搜索优先算法。这就意味着加以适当的估计即搜索的顶点向t分散。如果估计量表示实际的最短路径长度为t，则该算法停止搜索从s到t的最短路径的顶点。假定的条件Hs（v）必须为小于从v到t的实际最短路径长度，这是最终获得的路径是最短从s到t所有路径中最短路径的保证条件。使用没有这个假设条件的估计的算法称为A算法。 A *算法被定义为特殊型的算法。在A*的算法，从s的最短路径并不总是S中的顶点。也就是说，较短的路径可能在将来的搜索中找到。这就是为什么步骤3中当s中的顶点可能被更新的原因。这种诱导检索的增加的无效操作能够可以消除如果估计量是被定义为双重可行。定义1：所述用于向t的最短路径中估计器，Hs是双重可行的。在E中的每个边（u，v），当且仅当如果Hs满足以下条件：L (u, v) + Hs (v) = Hs (u) (1) 如果该图是一个道路网络，一个顶点和t之间欧几里德距离会被用作从顶点到t的最短路径的双可行估计量。2.3 双向Dijkstra算法方法前两种方法都是以搜索顶点与原点为中心的单向搜索算法。在这些算法中，目的地起着比原点稍微次要的一个角色。另一方面，双向搜索算法利用两个原点且均匀地在目标由从原点侧和从目的地侧搜索备选。在下文中，正向搜索表示从原点那边开始的搜索，而为了方便起见，后向搜索表示从目的地那一边开始的搜索。双向Dijkstra算法方法使用的Dijkstra方法既为向前和向后搜索。双向Dijkstra方法的概要说明如下。1.设S和T是空集，以及一个顶点v的值，Pt（v）以及Ps（v）是+。令Ps（S）和Pt（t）为零。2.找到在vS中有最小距离的顶点v0并添加到VS。.如果v0是T，然后转到步骤7。3.对于所有的顶点V，使得（v0，v）为在E，如果Ps（v0）+ 1（v0，v）为小于Ps（v）中，用从s的路径替换到v从s的路径VO和边缘（v0，v）中，并且令Ps（v）的是Ps（v0）+L（v0，v）。4.找到有最小值的顶点v0并增加至T。如果v0是S，则转到步骤7。5如果L（v，v0）+ Pt（v0）小于Pt（v），对于所有的顶点v，E中的（v，v0），则代替从v到t的路径，改为边缘从v0到t的路径，让Pt（v）等于L（v，v0）+ Pt（v0）。6.转到第2步7.找到Pt（u）的+ L（u，v）+ Pt（v）有最小值的边缘值（u，v）。如果Ps（v）+ L（u，v）+ Pt（v）小于Ps（v0）+ Pt（v0）,从S到t的最短路径是从s到u的路径和所述边（u，v）以及从V到t的路径，否则它是由从s到v0的路径。后向前和向后搜索到达同一顶点，从S到T是由简单的后向处理得到，如步骤7的最短路径。这是因为，它决定从s的最短路径顶点，以便使用Dijkstra方法的属性从s到顶点的路径长度。如果G是均匀的，搜索到顶点的数目是因为在这种情况下搜索顶点单向迪杰斯特拉法大约一半分布在两个圆与两个终端的中心。3新的简单方法双向A *算法人们很自然地使用A *算法向前搜索和向后搜索，以减少搜索区域。假设对于每个顶点v一个起始值，估计从V到t的最短路径为Hs（v），从s到V的最短路径为Ht（V）。利用H作为估计器，用于前向搜索和h作为估计器，用于后向搜索的算法已被提出。虽然这种方法是自然的，所述算法是复杂的，所以它不能指定从s时被搜索的双方的区域相互重叠的最短路径吨。这意味着从s到t的最短路径并不总是通过重叠点，该算法不能阻止从另一个侧面后进行搜索的已经到达顶点被搜索过的点。这是由于，该算法利用独立估值器2进制的A *算法，并且除非两个估计器是双可行否则就不会改变。为了避免这样的缺点，我们提出了基于根据以下技术平移A *算法和Dijkstra算法，每个估计器是双重可行的情况下的另一种方法的新的双向A *算法。定理1：使用边缘长度L的迪杰斯特拉法作如下变化是等同于A*使用原始边缘长度L与双可行估计Hs算法:L(u，v)=l(u, v )+Hs(v) - Hs(u) (2)证明：既然L（u，v）不是h的偶可行性负，则可以使用L（u，v）对于边缘的长度（u，v）中的迪杰斯特拉法。令P是从s的临时路径为顶点v。则满足下式为V的迪杰斯特拉方法的值：注意Hs（s）是一个常数，并且 表示迪杰斯特拉算法里v的值。这表明使用改善性边缘长度Dijkstra方法等效于A*的算法。这个定理表明了A*算法可以通过使用Hs给予特殊的边长来转化为Dijkstra算法（2）。这意味着双向A*算法是通过使用改性的边缘长度通过将双向迪杰斯特拉方法来实现（2）。但是，这种方法有一个问题，即向后搜索未改变A*算法，因为用于从s的最短路径时估计器不包含Hs（2）。要应用A *算法利用Ht进行后向搜索，一个边的长度（U，V）必须如下修改：L(u，v)=L(u, v )+Ht(v) - Ht(u) (3)因此，很自然地采取L作为新的边长去在A *算法中转换向前和向后搜索：L(u，v)=L(u, v )+（1/2）（Hs(v) - Hs(u)）+ Ht(u) - Hs(v) (4)L一定不是负数因为Hs和Ht的偶可行性。边长的改进相当于利用（1/2）（Hs(v)-Ht(u)）作为从V到t的估计最短路径，利用（1/2）(（Ht(v) - Hs(v)）作为从s到v的估计最短路径。当每个顶点u的Ht和Hs皆有意义的值，即不为负的值，这些新的估计量需要满足下述不等式：Hs(t)=（1/2）（Hs(v)-Ht(v)） (5)Ht(v)=（1/2）（Ht(v)-Hs(v)） (6)每个不等式保证了相应的新的估计量不超过对于其估计的实际最短路径长度。以这种方式，以下定理才成立。定理2使用边长L定义为（4）的双向迪杰斯特拉算法等效于利用原始边缘长度L利用（1/2）Hs(v)-Ht(v)作为从V到t的估计最短路径和双向A *算法利用（1/2）Ht(v)-Hs(v)作为从s到v的估计最短路径。考虑到每种算法估计的结果，不等式（5）、（6）表明新的估计是不足于原有的。然而，这种方法具有实现简单的双向A *算法的优势，当搜索区域从两侧彼此重叠它可以指定以较少的运算获得最短路径。本算法适用于寻找次优的路由。次优的路线被认为是最理想的候选替代路线。假设次优的路径被定义为，其长度比最短路径长度长了近，但长度只是