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

《一个可以寻找更好路线的快速算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、一个可以寻找更好路线的快速算法1．摘要最短路径问题是可以适用于各种领域的其中最基本的问题之一，并且它和路线导航系统有着密切的关系。本文调查两端最短路径算法的问题,提出了双向A*算法基于一种新方法。该算法不仅适用于寻找最短的路线也适用于寻找出更好的路线。我们通过实验将它们应用于实际的道路网络以讨论这些算法的效率和性能。2.介绍提出减少必要的时间到目的地是一个路线导航系统所需的最基本的功能。从保持信息在起源地和目的地之间的一个适当路线上的困难度来说，以及利用如交通流这样的动态信息的可能性，这个问题必须有用户在其每次请求

2、的时候来解决。以这种方式，它以产生更有效的方法来搜索适当路径上的道路网络是重要的。该主题概括为上图的两端最短路径问题，这是问题找到从s的最短路径t上有向图G=（V，E）。这样，一个边的长度（U，V）中E为L（U，V），其中原点s和目的地t是已经给出。因为可以广泛应用，所以这种问题已经研究了在各种领域进行很长一段时间。例如使用Dijkstra方法是一种传统的算法针对此问题。此外，在A*算法和双向搜索算法是众所周知的基于AI（人工智能）搜索技术的算法。本文对这些算法不仅考虑从施加他们到的点的道路网络上的两个末端最短路径

3、问题，还提出在双向A*的基础上根据技术转换的一个新算法，即改进算法的Dijkstra方法。本算法不仅适用于发现最短的路线，而且适用于寻找更好的路由。即次优路由作为候选，含有不是最短，但较少的圈数的路径，例如替代路线。效率和这些算法的性能是通过使用实际的道路数据的实验讨论。2.1Dijkstra算法方法Dijkstra方法是一个基本的算法解决最短路径问题。虽然原算法通过迪杰斯特拉是为单原点到所有目的地的问题。它几乎适用于所有二端的问题。以下是使用Dijkstra方法的用于两终端问题的步骤。1.设S是空集，设Ps（S）

4、为到一个顶点U的点集合，除了原点S其他都是+∞。令Ps（S）是零。2.找到在V—S中有最小距离的顶点v0并添加到V—S。如果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当前的最短路径比保持了顶点的所有其他路径更短，这表

5、明这些顶点，从S到它们的实际最短路径已经被决定了。以这种方式进行Dijkstra方法查找，以便从S到顶点的路径长度最短路径从S到一个顶点。这表明如果G是均匀的，使用此算法的搜索区域就是与S的圆为中心。Dijkstra方法经常用于具有搜索在所有的方向无关的地方两终端最短路径问题的缺点。2.2A*算法在A*算法找到最短路径从S到T其实更有效，从各顶点的最短路径长度的试探估计t，而t是已知的，并且它必须小于实际最短路径的长度。令Hs（v）表示这个估计的顶点v。那么A*算法的步骤描述如下：1.设S是空集，设Ps（S）为到一

6、个顶点U的点集合，除了原点s其他都是+∞。令Ps（S）是零。2.找到在v—S中有最小距离的顶点v0并添加到V—S。如果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步。在该算法中，Ps（v）也表示从s到v临时最短路径的长度。因此，A*算法被认为是从s到t的最短路径的顶点搜索优先算法。这就意味着加以适当的估计即搜索的顶点向t分散。

7、如果估计量表示实际的最短路径长度为t，则该算法停止搜索从s到t的最短路径的顶点。假定的条件Hs（v）必须为小于从v到t的实际最短路径长度，这是最终获得的路径是最短从s到t所有路径中最短路径的保证条件。使用没有这个假设条件的估计的算法称为A算法。A*算法被定义为特殊型的算法。在A*的算法，从s的最短路径并不总是S中的顶点。也就是说，较短的路径可能在将来的搜索中找到。这就是为什么步骤3中当s中的顶点可能被更新的原因。这种诱导检索的增加的无效操作能够可以消除如果估计量是被定义为双重可行。定义1：所述用于向t的最短路径中估

8、计器，Hs是双重可行的。在E中的每个边（u，v），当且仅当如果Hs满足以下条件：L(u,v)+Hs(v)>=Hs(u)(1)如果该图是一个道路网络，一个顶点和t之间欧几里德距离会被用作从顶点到t的最短路径的双可行估计量。2.3双向Dijkstra算法方法前两种方法都是以搜索顶点与原点为中心的单向搜索算法。在这些算法中，目的地起着比原点稍微次要的一个角色。另一