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