An adaption of the A* Algorithm of Fastest Paths in Deterministic Discrete-Time

这是几年前研究生开题时需要提供论文翻译，现在整理和A*以及动态导航规划相关文档，把这个放出来，应该还有些其他翻译和论文总结的。

不过这里不支持word上传。。。。。。所以，可能不能示里面的公式。请勿转载，因为如果翻译不好，误人子弟。。。。

原文现在也可以下载了，以前是在IEEE里

http://www.its.uci.edu/~yangi/papers/Chabini.2002.IEEE.pdf

用于确定性离散动态网络最快路径计算的
A*算法的改进

Ismail Chabini ，Shan Lan

 

摘要：本文把A*算法扩展到动态网络中的最短路径问题之中，其弧旅行时间是时间相关的。我们提出一些有效的A*算法的改进，使之可以用于计算从一个起始节点到一个目标节点的最快路径（最少旅行时间），也可以用于计算在一些动态网络中满足先进先出原则的链接旅行时间，且其起始节点具有多出发时间的情况。我们总结了一些有用的动态网络工具，开发了改良的最少旅行时间的下界。开发这些下界是为了设计有效的A*改进算法，而算法是为了解决诸如一对一的动态最短路径的问题。这个开发出来的算法被执行，其计算性能是采用实验方法分析出来的。A*的改进算法的计算机实现性能相当于一个动态的狄杰斯特拉（Dijkstra）算法的改进。当目标节点被选择时，这个算法就停止了。比较计算结果可以证明本文所介绍的算法是有效的。使用一个包含3000个节点、10000条路链和100种时间间隔，此动态的A*改进算法可以降低在节点数目选择方面的比例，也可以降低在计算时间方面的比例。在这个算法的性能方面，网络规模的作用也是有计划的。这表明了在节点数目的选择和计算时间两方面，计算存储是随着网络拓扑规模的增长而增长的。

 

关键词：A*算法，计算机算法，动态网络，智能交通系统，网络优化，时间相关的最短路径。

 

第1章 介绍

动态网络中的最短路径计算是包含信息技术和网络设备在内的交通应用系统计算需求的核心。例如，在智能交通系统应用程序环境中，最短路径计算是路由导航系统和大规模动态网络流动模型解决算法的基础部分；这些模型在支持有效的智能交通系统决策制定方面非常有用。在这些应用程序中，需要在网络中寻找许多条最短路径，而其参数是时间相关的。此外，为了应付智能交通系统应用程序的实时操作需求，此解决算法必须足够有效，使得运行时计算最短路径比实时更快。

过去在动态最短路径问题方面的研究主要着眼于以下两个问题：在给定的出发时间下从一个起始节点到所有目标节点的最短路径问题和在所有可能的出发时间下从所有节点到一个目标节点的最短路径问题（参见参考文献[1]）。本文讨论的是从一个起始节点到一个目标节点的问题。这个问题在其它文献中很少被提及。这个问题需要着眼的是计算一个指定出发时间条件下的一对一的最短路径，或者是起始节点有许多可能的出发时间条件下的一对一的最短路径。

让我们考虑一个交通网络，司机们在寻求一个使他们旅行时间最少的路线。为了支持旅行者选择最优路线，网络可以以最短路径的形式提供给他们动态的信息。这些信息的传播方式有许多种，例如通过车载设备或者通过按装在特定网络节点处的可变信息信号，就像高速公路网络中的主要路口一样。这些最短路径应该由车载系统或者一个交通管理和信息中心计算出来；注意到前一种方法只适用于具有计算装置的车载设备。

在这一段和下一段，我们描述两种需要在动态网络中计算一对一的最短路径的路线导航情况。首先，考虑以下这个车载路线导航计算的情况。交通管理和信息中心预测交通状况及发送时间相关的路链旅行时间给车载导航处理单元。这些单元根据给定的车辆所在空间位置和时间（当前节点和当前时间）和司机的目的地节点计算最快路径。这个计算任务就是一个动态网络中的一对一最短路径问题。通常，车载计算受到车载存储器容量和数据传输能力的限制，而大量的动态数据（主要包括时间相关的路链旅行时间）需要发送给车辆和存储于车上。这需要快速的通信速度，车载存储空间能够压缩存储以一个选定算法生成的动态数据。在参考文献[2]中所描述动态网络数据的比特流方法就是这样的一个算法例子。

接下来我们描述需要计算在动态网络中一对一最短路径的另一种情况。当路线信息被发送给安装于某些节点的可变信息信号时，例如主要的高速公路路口，需要计算从这些节点到一个或多个主要目的节点的最短路径。有两种可能的方法来决定此应用的最短路径：寻找多条“一（起始节点）对一（目的节点）”的最短路径，或者为所有的出发时间寻找多条“所有对一（目的节点）”的最短路径。节点总数仅仅是网络总数的一个小小的零头，这些节点既不是目的节点也不是信息发送给的代表性节点。例如，在纽约Lower Hudson山谷地区高速公路和公园道路网络模型中，目的节点和路由候选节点的总数大约有100个，而节点总数则有数千个。需要解决许多一对一最短路径问题的最短路径计算，通常比能达到相同目标的、在所有可能出发时间下解决每个目标节点和“所有对一”的最短路径问题要更加有效。

在参考文献[3]中首次被提及的A*算法，是一个解决在静态网络中一对一最短路径问题的有效算法。A*算法用于解决静态最短路径问题通常胜过传统的静态最短路径算法，这在文献中是众所周知的。A*算法只适用于静态网络环境。参考文献[4]的注释中提出了A*算法能否被扩展到动态网络中解决一对一最短路径问题的疑问。据我们所知，这个问题在文献中并没有被解决。本文为大家展示第一次为人所知的在这方面取得的成果。

动态最短路径问题可以被看作是一个动态网络中的静态最短路径问题在时间空间中的表示（参见参考文献[1]）。这并不意味着它构造了一个时空网络和适用一个静态最短路径算法，而是意味着它采用了时空网络的特性（也是附加的特性）派生出动态网络的专用算法，但并没有明确地工作于时空网络中。本文的主要目的是通过使用一些动态网络数据的特性开发出一种有效的A*改进算法。因此，本文把A*算法扩展到动态网络中的最短路径问题。

定义一条路径的权值的标准有很多种。在本文中，路径的权值被定义为它的旅行时间。术语最短路径和最少旅行时间（或最快）路径被交替的使用，它们是等价的。

考虑在所有可能出发时间下计算起始节点和目标节点间最快路径的问题。本文的一个主要算法的发展是基于以下观点的：假定它解决这个问题与一系列的一对一最短路径问题一样，每个问题都相应地给出起始节点的出发时间。当计算一个出发时间为t的最短路径时，它可以将所获得的最短路径结果直接用于较早的离开时间（如t-1）。通过开发有效的从一个给定节点至一个给定目标节点的最短旅行时间的下界，我们采用这些过去的计算结果。正如在实验结果中所展示的一样，这将有意义地改进计算总效率。这个观点与采用从前一计算方法加快最佳路径的搜索相似，前者是在静态网络环境下解决一对一最短路径问题，参考文献[5]中有提及。本文的观点也与参考文献[6]中所描述算法的背后思想相似。这个算法计算在连续时间动态网络中从所有节点到一个目标节点的最短路径，其最短路径决定于以降序排列的起始节点出发时间。而由出发时间t计算出来的结果被获得使用与下一出发时间相应的结果，从而减少总的计算时间。

本文的主要贡献概述如下：我们通过提出有效的计算从起始节点到目标节点的最快路径（或最短旅行时间）的A*算法的改进，在弧旅行时间具有时间相关性的网络中，将A*算法扩展到了起始节点具有一个或多个出发时间的最短路径问题。此改进适用于路链旅行时间满足先进先出原则的动态网络。我们在此网络中标识动态数据的特性，并使用它们去开发基于最少旅行时间的改良的下界。这些下界是在设计有效的A*改良算法时被开发出来的。这些算法已经被实现，其计算性能已经通过实验分析出来。数值结果显示，本文所开发的A*改进算法比动态的狄杰斯特拉（Dijkstra）算法更有效率。当到达目标节点时，后者便会停止。后者被认为是文献中解决动态网络一对一最短路径问题的算法中最快的。计算结果表明，在网络包含3000个节点、10000条路链和100个时间间隔的情况下，A*改进算法比动态狄杰斯特拉改进算法（到达目标节点即停止）快五倍。此外，实验计算表明，这些计算出来的时间会随着网络规模的增长而增长。据我们所知，这是动态环境下的A*改进算法第一次出现在文献当中。

本文组织结构如下：第2章，简短地回顾文献中有关A*算法和动态最短路径问题的内容。第3章，提供一些定义和符号。第4章描述静态A*算法。第5章描述一些动态网络的特性。第6章，分析动态网络中最少旅行时间的下界；基于这些下界结果，运用A*改进算法有效地解决一些动态最短路径问题。第7章通过实验展示A*改进算法在计算机上运行的结果。第8章对本文作出总结。

 

第2章 文献回顾

A*算法最早在参考文献[3]中提及，在参考文献[7]、[8]和[9]中得到进一讨论和扩展。Hart等人（在参考文献[3]中）指出，A*算法是一个可接纳的最佳算法。Golden和Ball（在参考文献[10]中）根据经验发现，在一个具有斜向弧的无限点阵网络中，A*算法所搜索的区域比一个最优的Label-Setting(LS)算法所搜索的区域少8.3%。设n和m分别表示一个网络中的节点数目和弧数目。Sedgewick和Vitter （在参考文献[11]中）证明，A*算法在众多欧氏图中寻找一个最短路径的平均花费为O(n)，而运用堆栈实现的LS算法的平均花费为O((m+n)*log(n))。Bander和White（在参考文献[12]中）提出了IA*算法（interruptible A*）。这个算法利用了从专家处获得的节点集信息，这些信息可能包括最优的或者接近最优的从起始节点到目标节点的路径。Lark等人（在参考文献[13]中）提出了AG算法，运用一个启发式集合H引导搜索。这个集合能表示自然语言的语句和界限信息，例如欧式几何中的距离。Bander和White（在参考文献[5]）提出普适性的A*算法（AA*算法），扩展了AG算法和IA*算法。这个算法使用以往确定了的被认为是最优的路径，和专家们考虑过的值得提高搜索速度的路径。从过往计算中提取信息从而提高最优路径搜索速度的想法跟本文所提出的A*改进算法基本思想很相似。需要注意的是以上提及的所有关于A*算法的发展都仅仅只是着眼于静态网络。在本文中，我们将提出有效的在动态网络中的特定A*算法。

一个动态最短路径问题的第一个变化在参考文献[14]中被首次提及，文中也描述了在所有可能出发时间下从所有节点到一个目标节点的最短路径计算。在参考文献[14]中被提及的算法可以被看作是一个Bellman-Ford算法在时间相关网络中的扩展应用，其节点标签是一个标量标签的向量而不是一个在静态网络情形下的简单的标量标签。在参考文献[15]中，介绍了另一个算法用于解决参考文献[14]中的相同问题。这个算法可以被看作是在时间相关网络中更正最短路径算法的标签的一个扩展应用，其节点的标签是一个标量标签的向量而不是一个静态网络中情形中的简单的标量标签。参考文献[14]和[15]中的算法都是用于最少时间路径问题的。参考文献[1]表明，这些算法的运行时间复杂性在最坏情况下都是O((M+n)(m+n)M)，其中M是动态网络中离散时间间隔的数目。

以往的算法都是通过对节点进行迭代来构造最短路径标签向量。为了改变这种做法，Chabini在参考文献[16]和[17]中提出最优的最短路径花费向量可以以时间降序来构造。在每个时间阶段t，相应于每个出发时间t的所有节点的最优标签就被确定了。这就是我们所知的DOT算法的结果，算法的运行时间复杂度是θ(nM+mM+SSP(n,m))，其中SSP(n,m)是一个“所有对一”最短路径算法的运行时间。参考文献[16]和[17]表明，DOT算法用于解决在所有可能出发时间下“所有对一”动态最短路径问题时具有最佳的运行时间复杂度，似乎还没有其他算法在最坏情况下的运行时间复杂度比其更好。

另一个被讨论得较多的动态最短路径问题分量是在给定离开时间下从一个节点到所有节点的最短路径计算。此问题的一个著名结果是：满足先进先出原则（参见第3章关于先进先出原则的定义）的任何静态最短路径算法都可以解决在给定时间下的一对多动态最短路径问题，其时间复杂度与静态一对多最短路径问题的一样。Dreyfus（在参考文献[18]中）是第一位试探性地提出这种泛化的人。不久之后，Ahn和Shin（在参考文献[19]中），Kaufman和Smith（在参考文献[4]中）证明了这种泛化只有在先进先出原则得到贯彻时才有效。在参考文献[16]和[17]中给出了另一个对此结果的更简短的证明，本文将在稍候提及。

Chabini和Dean（在参考文献[1]中）扩展了在参考文献[16]和[17]中提及的结果。他们提出了一个完整的框架，用于分类、完整地叙述和解决离散时间动态网络中不同的最短路径问题分量。这个框架包括之前文献中作为特别案例所讨论过的所有问题分量。扩展的DOT算法在参考文献[16]和[17]中被描述过，Chabini和Dean（在参考文献[1]中）设计了实现了这个算法，使之具有最坏情况下理论上最优的运行时间复杂度。Chabini和Yadappanavar在参考文献[2]和[20]中提出了一种方法用于表示在压缩表中的动态数据，即我们所知的比特流，并改进了算法使之在此压缩表数据表示上运行得更加高效。

以上的文献回顾表明，多数动态最短路径领域的研究发展主要着眼于一对多或多对一最短路径问题，而在一对一动态最短路径问题上的贡献很少。Kaufman和Smith在参考文献[4]中建议使用静态最短路径算法（例如LS算法）去解决单出发时间的一对一最短路径问题。在Kaufman和Smith文章的注释中，Koutsopoulos提出了A*算法是否能够被扩展到解决动态网络中一对一最短路径问题的疑问。本文发布了在此方向上的第一次发展，展示了能有效解决动态网络中一对一最快路径问题的A*改进算法。

第3章 定义和符号

令G=(N,A,D)为一个有向网络，N={1,…,n}为节点集合，A={1,…,m}为有向路链集合。我们指定D={d_ij(t)|(i,j)∈A}为基于时间的路链旅行时间集合，其中函数d_ij(t)为整形值。函数d_ij(t)是一个有向且基于时间的函数，并假设其包含一个在时间间隔M的有限数字之后的静态值。因此，T={0,…,M-1}为路链旅行时间具有时间依赖性的出发时间间隔集合。B(i)表示具有一个到节点i的外向路链的节点集合，A(i)表示从节点i出发的一条路链的终止节点集合。令节点o∈N表示一个起始节点，节点q∈N表示一个目的节点。

本段落的符号假设了一个静态网络。下面是我们用于描述A*算法的符号（更多公用的符号可以在参考文献[7]中找到，这些符号给出了一个A*算法的普遍描述，这对于人工智能应用程序的其中一种是有效的）：

L_i      从起始节点o到节点i的最少旅行花费；

e_ij      从节点i到节点j的最少旅行花费；

F_i           在所有路径中从起始节点o到目标节点q，且经过节点i的最少旅行花费；

_i          从起始节点o到节点i的最少旅行花费的上界；

ê_ij           从节点i到目标节点j的最少旅行花费的下界；

_i         F_i的估计； _i= _i+ê_iq；

C            已经到达，且作为选择下一节点的候选的节点集合；

S                   已经被选择，且不在集合C中的节点集合；A节点也许是从集合S中删除的，并且如果其标签 _i减少则被加入到集合C中；这仅当在下一段中定义的一致性假设不成立时有效。

一致性假设：在最短路径算法领域中的一致性概念用来表示不同的概念。在本文中，对于一个给定的任意目标节点q，我们认为一致性假设当且仅当满足以下情况时成立：对于任意一对节点i和j，从这些节点到一个给定目标节点的最少旅行花费的下界满足不等式e_ij≧ê_iq-ê_jq。这就是说，任意一对节点i和j的下界的不同之处就是从i到j的最少旅行时间的一个下界。交通运输领域的一些研究员也使用条款一致性来评价先进先出原则，我们将会在本节后段进行定义。注意到如果使用以前的一致性假设的定义，那么我们有e_ij≧ê_iq-ê_jq。这意味着对于每条路链(i,j)∈A，其（减少了的）花费 是非负的，因为d_ij≧e_ij 。如果一致性假设是有效的话，一致性假设和路链减少的花费之间的关系将会被用作解释A*算法是一个经典的LS算法。本文稍候将会对此作出更详细的解释。

先进先出（FIFO）的定义：在一个交通系统中，在一个集合层次中，路链旅行时间通常是指旅行者以与他们从路链起点出发时相同的顺序到达此路链的终点，这就是所谓的先进先出原则。更正式地，我们说如果到达时间函数t+d_ij(t)是非递减的，那么路链旅行时间函数d_ij(t)满足先进先出原则。在离散时间动态网络中，一条路链(i,j)∈A是一条先进先出路链当且仅当

       。

如果一条路链(i,j)∈A的旅行时间函数满足先进先出原则，那么我们称路链(i,j)是一条先进先出路链。类似地，如果一条路径的旅行时间函数满足先进先出原则，那么我们称这条路径是先进先出路径。如果网络中的每条路链都是先进先出路链，那么称此网络为先进先出网络。在先进先出网络中解决最少时间动态最短路径问题，比在非先进先出网络中解决一般的包含最短时间路径问题的动态最短路径问题要更容易些。后者被定义为至少包含一条非先进先出弧的网络。

本文所考虑的问题是在先进先出动态网络中寻找包含一个或多个出发时间的从起始节点到目标节点的最快路径。为了解决这个问题，可以使用文献中所描述的不同的动态最短路径算法。例如，可以采用先进先出网络中的LS一对多最短路径算法（见参考文献[4]），当目标节点标签被选择成为进永久性集合时停止搜索。然后，这些最短路径算法是可以被改良的，因为某些节点并不需要被搜索到。本文所述的A*改进算法，将避免搜索那些不会出现在最短路径上的节点。能达到这一目标的机制是基于一下观察的：在一个先进先出网络中，当计算时间间隔为t的最短路径时，可以利用计算时间间隔为t-1时的最短路径的信息。这些信息被用来改进从某一节点i到目标节点q的最快旅行时间的下界。

第4章 A*算法

我们相信本文的典型读者是来自交通运输领域的，因此，他们可能对A*算法的细节并不熟悉。那么，在描述A*改进算法之前，我们首先提供一个相关的A*算法的简要介绍。我们首先举例说明A*算法的基本思想，然后进行描述，也摘录一些A*算法的特性。最后，我们说明如果一致性假设成立，那么A*算法可以被看作是狄杰斯特拉算法在一个等效网络中的应用。这个网络拥有与起始网络相同的拓扑，也拥有像路链花费一样的降低性花费。这个花费使用原始路链花费，和能验证一致性假设的下界。

A． A*算法的基本思想

为了解决一对一静态最短路径问题，可以使用任意传统的LS算法。此算法设计用于解决一对多最短路径问题，当到达目标节点时便停止。尽管如此，这些算法仍不是解决一对一最短路径问题的最有效率的算法。例如，考虑一个起始节点在市中心、目标节点在东面远方的城市网络。一个LS算法典型的可能是对起始节点的东面、南面、西面和北面的搜索都作相同的努力。因此，这些算法也许会搜索到最短路径可能不会经过的地区。

既然我们知道搜索的目标是到达目标节点，那么直观地，LS算法的效率是可以被改良的，可以利用这些信息去引导搜索。例如，最短路径搜索也许被约束在整个网络的某一个子区域中，结果搜索区域将会比一个传统的LS算法分析的区域要小得多。

 

图1 A*算法和LS算法的搜索区域

让我们考虑一个交通网络，其节点一律分布在一个给定的地理区域里，路链旅行距离为欧式几何距离。假设需要计算从一个起始节点o到一个目标节点q的最短路径（见图1）。如果使用狄杰斯特拉算法，在每一次新的循环中[（in Step 2）]，选择一个接近起始节点的节点，例如一个最小值为 的节点。狄杰斯特拉算法的搜索区域结果近似地为一个圆。A*算法根据标签 将节点在候选节点集合中排序，此式是对从起始节点到目标节点q、经过节点i的所有路径的最少旅行花费的估计。A*算法选择一个包含最少标签 的节点。在命题1和2的推论1中证明，A*算法只选择那些满足 的节点。如果A*算法中使用的下界是欧式几何距离，那么对应于后一不等式的搜索区域是一个椭圆（见参考文献[10]）。如图1所示，A*算法的搜索区域讲比传统LS算法的搜索区域小很多。

B． A*算法描述

接下来是A*算法的描述。节点对(起始节点,目标节点)表示为(o,q)。

步骤 1）初始化：

           设i=o， =0， =ê_ij； =∞， =∞， ；C={i}；S=Φ。

步骤 2）节点选择：

                    选择 , , 。

步骤 3）停止规则：

           如果i=q，那么停止。否则，继续。

步骤 4）更新 和距离标签 ：

对于每个 ：如果 ，那么 ； ；

如果 ， 。返回步骤 2）。

在算法的第4步，对于每个 ，标签 和 都被更新。如果一致性假设被下界所满足，那么不需要考虑那些属于已选择节点集(S)中的节点j（见命题1）。需要注意的是，在算法的实现中，对于节点j，可以仅保持标签 而不是 和 都保持，因为 可以仅从 的函数中得到( )。这使得在计算时间和存储空间上可以有所节省。式子 被称为下降花费（在本文中，旅行花费是指旅行时间）。

狄杰斯特拉最短路径算法的描述可以在经典网络算法书籍中被找到。这个算法可以被看作是A*算法的特别例子，其下界等于零。如果路链花费为非负的，那么零下界验证了一致性条件，而且因此，不需要考虑在步骤2中被选择的节点。我们省略了一对一狄杰斯特拉最短路径算法的描述，它可以很容易从A*算法的描述中衍生出来。

C． A*算法的一些特性

在本段，我们描述一些A*算法的特性。这些特性有助于理解A*算法，以及开发本文中的A*改进算法。既然这些特性出现于文献中，我们也就不对其进行证明了。

命题1[3，推论2]：假定一致性假设被满足，如果节点i由A*算法选出，那么 = 。

如果不满足一致性假设，那么由A*算法的前期步骤所选择的节点i的标签 将会在算法的后期步骤中降低。因此，如果节点i的 标记降低了，那么这个节点需要被放回候选集C。不管怎样，命题1意味着如果一致性假设被满足，那么一旦一个节点被A*算法所选择，从起始节点到此节点的最短路径就被标识出来了。因此，被选择的节点将不会重新加入候选集合中。A*算法的最后语句就不需要执行这些已经在被选择节点集合S中的节点。

命题2[3，推论3]：对于任何被A*算法选择的节点i， 。

命题3[3，定理1]：当A*算法终止时，通常就能找到一条从起始节点到目的节点的最短路径。

命题3显示出A*算法的正确性。

命题4[3，定理2]：考虑下界集合满足一致性假设。对于一个给定的下界，如果一个节点被A*算法选择了，那么这个节点将可以被A*算法用任何更下的下界选择。

在A*算法步骤2）中被选择的节点，是由将在步骤4）中被检索的弧所决定的。假设计算下界的工作是相似的，而且从节点出发的弧的数目是均匀地分布于节点间，那么总的计算工作是在A*算法步骤2）中所选择的节点的总数的递增函数。命题4意味着如果下界满足一致性假设，那么A*算法所选择的节点总数以及总的计算工作就是ê_id值的非递增函数。

下面的两个推论将展示出A*算法所选择的节点数目与e_iq的下界性质之间的关系。

推论1: 如果一贯性假定被满足，那么A*算法选择唯一的那些满足 的结点。

证明: 因为一贯性假定被满足，那么使用命题1，我们有 。使用命题2，如果结由A*算法选择，然后 。因而，我们有 。

推论2: 如果对每个节点i都有 ，那么A*算法在一个最短路径选择唯一那些节点。

证明:首先，我们证明，如果 为每个节点I,那么 满足一贯性假设。既然 是从i到q的最少旅行时间，对于所有的双节点i和j和我们有 。因此，我们有 。

因为一贯性假定被满足，那么，由推论1，A*算法选择唯一那些节点与 。因此 ，A*算法选择唯一核实不平等的那些节点 。因为我们知道任一个节点满足 ，如果 为所有节点，A*算法选择唯一核实平等的那些节点 。这意味着任一个选择的节点i是在一个从起始节点到目的节点的最短路径。因此，如果对于任意节点i有 ，那么A*算法就只选择这些节点生成最短路径。

总之，A*算法的效率取决于下界的质量。如果为每个节点i有 ，那么 。这意味着A*算法与狄杰斯特拉算法是相同的。如果 ，A*算法选择唯一那些在最短路径上的节点。如果 ，节点的数量由A*算法选择是一个 非负函数，如果一贯性假定是满足的。所以，为了让算法选择更少的节点，需要发现一个更紧密的 下界。

D． A*算法减少花费的表现

A*算法一般陈述依照被显示在部分IV-B 。我们现在表示，A*算法与狄杰斯特拉的最短的道路算法是相同的，如果原始的链接旅行费用由被减少的链接费用替换被获得使用最低界面满足一贯性假定。为所有 ，被减少的费用的表示是 。以下引理建立一个关系在A*算法之间和狄杰斯特拉的算法。它假设，狄杰斯特拉的算法被停止当目的节点被选择。

引理1: 如果一贯性假定是满意, 那么申请A*算法在一个网络以链接旅行时间 解决一个一对一最短的道路问题是同样算法("不同地" 陈述)作为运用狄杰斯特拉的算法在同样网络以链接费用 。

证明: 如果一贯性假定被满足，为所有 ，我们有 。所以 非负。因此，我们能运用狄杰斯特拉的算法在网络与路链旅行时间 为解决一对一最短路径问题。注意到狄杰斯特拉算法是当到达目标节点时停止的。

除了在他们的前步, A*算法和狄杰斯特拉的算法跟随同样步。因为被减少的费用非负，节点的标签被选择在这些算法早期不会被减少在最新阶段。声明在A 的最后步A*算法与最后步是然后相同的考虑唯一节点被到达了但未被选择的狄杰斯特拉的算法。

上述相等在算法的声明能并且服务为据为有效性A*算法的另外证明的如果一贯性假定是合法的。从替换 为 或替换 为 不影响最短的道路在任何对节点之间(参见[21])，一个最短的道路由狄杰斯特拉的算法发现在网络以链接旅行时间 并且是一个最短的道路被发现在原始的网络的，反之亦然。所以，申请A*算法在一个网络以链接旅行时间 解决一一对一最短路径问题是一个有效的算法，与狄杰斯特拉算法在相同拓扑网络是一样的，后者路链旅行时间是 而不是 。

在例子中当一贯性假定是合法的, 命题1并且暗示，一个不一定需要写分开的计算机编码为A*算法如果你已经有狄杰斯特拉的算法计算机编码。你可能狄杰斯特拉的算法在网络由替换 为 链接旅行时间负责操行。注意，然而，替换 为 所有链接将导致额外计算时间。实际上，解决一对一最短的道路问题，你不需要搜寻所有链接在网络。因而，它不是必要替换 为 所有链接在运用狄杰斯特拉的算法前。反而，你需要做如此只当你需要访问弧。这观察是特殊兴趣在动态网络上上下文为以下原因。照原样以后被显示在本文里，时间膨胀的网络包含弧mM，在多数弧m将由LS算法的动态适应搜寻。因为LS算法被停止当目的节点被选择，弧的一个更小的数字将被搜寻解决一对一最快速的道路问题在一个动态网络。因此，你应该计算 为唯一那些链接由算法实际上搜寻。这意味着如果计算效率被寻找，你需要改变狄杰斯特拉的算法计算机编码在这种情况下链接被减少的费用被计算只当链接被获取对更新节点不被选择。

A*算法可能被观看作为链接费用的算法, 由增加 来各弧 的费用。因而，如果 ，扰动增加弧 的费用, 当它增加弧 的费用如果 。如果节点最低界面是严紧措施对目的节点, 指向离目的地较近的弧有他们的费用减退, 当节点指向从目的地有他们的费用增量。这导致可能重新安排在节点的选择在步骤2) 。因此, 节点也许不被选择, 甚至不是在到达目标节点前被选择。

第5章 动态网络的一些特性

这个部分提出A*改进算法动态网络的一些根本节点果和物产本文算法根据。首先，我们表示，动态网络可能被观看作为静态网络由使用时间膨胀的网络表示法。然后时间膨胀的网络一些物产被突出。终于，我们提出将被使用开发最低界面在极小的旅行时间为A*改进算法动态的一些先进先出原则。

A． 时间延展网络

一个分离时间动态网络可能代表作为一个静态网络使用一个时间膨胀的网络表示法，是为形象化，公式化和解决分离时间动态最短的道路问题的一个有用的含蓄工具。这个网络由扩展原始的动态网络在时间维度，和做一个分开的拷贝所有节点形成为每个整数时间值 。每个节点在时间膨胀的网络代表时间节点对，包括时间 和节点 , 节点在最高的水平时间被采取代表不仅间隔时间M-1, 仅所有次大于或等于M-1。每个链接在一个时间膨胀的网络是一个被指挥的链接从节点时间对 对其它节点时间对 。

时间延展网络拥有以下特性：

1) 沿时间维度, 他们是非周期性的如果弧旅行时间是正的, 并且是多级的，如果弧旅行时间非负。

2) 每个道路在原始的动态网络对应于一个道路在时间膨胀的网络以同样旅行时间和旅行费用。参观一个结在原始的动态网络在时间对应于参观的结时间对 在对应的时间膨胀的网络。

3) 一个最短的道路问题在一个动态网络可能由运用解决一种静态最短的道路算法向它的等效表示法作为时间膨胀的网络。

上述特性2和3的说明，动态最短路径问题可能由(含蓄地) 运用解决静态最短的道路算法向一个动态网络的时间膨胀的表示法。这观察适用于A*算法。因为时间膨胀的网络包含节点nM和弧mM，一种静态最短路径算法的一种琐细和直接应用也许，然而，不是最高效率的算法可能。特性1被利用[1]公式化和高效率地解决各种各样的分离时间动态最短的道路问题在一个共同的框架。

对于每个离开时刻，A*改进算法被提出在本文查寻一个子集弧较少(实际较少) 比连接m在链接mM之中，和选择一个子集节点(实际) 比节点n在节点nM之中。我们演讲在本文剩下的人的主要任务是显示方式瞄准参观一定数量的弧，和节点，在解决一对一动态最短路径问题的A*算法的实际实现中是一样小的。

B． 先进先出原则

路链旅行时间也许拥有一些特性有用在学习和开发高效率的算法为动态网络，譬如，先进先出原则。下面，我们描述一些先进先出原则的有趣的后果，是非常有用的在开发高效率的A*改进算法。

引理2：如果每个路链在道路是先进先出路链，那么道路是先进先出道路。

证明：我们用归纳法证明这个命题。假设道路有k条路链，并且离开时间索引在第一节点在这个道路里是t。简化介绍，没有普通性损失，我们假设k条路链的索引是：1，2，…，k。

归纳假说是，到达时间作用在第l条路链的结尾， ，是一个t的非递减函数。首先让我们考虑基架。第一条路链在道路是先进先出道路，并且因此，归纳假说是合法的。现在，假设对第l条路链是真实的。我们需要证明，对第(l+1)条路链，到达时间函数 是一个非递减的函数。根据归纳假说，我们知道 是非递减的函数。因为每个路链在这个道路是先进先出路链，根据先进先出路链的定义， 是非递减的函数。令 。我们来证明，函数 是一个t的非递减的函数。因为 和 是两个非递减的函数，我们有： 并且 。令 和 ，那么 。因而， 。因此，我们有 。所以 是非递减的函数。由 ，道路的到达时间函数是一个t的非递减函数，并且道路是先进先出道路。

推论：在先进先出网络，任一个道路满足先进先出原则。

证明：在先进先出网络，每个路链满足先进先出原则。因而，任一个道路所有路链满足先进先出原则。使用命题2，任一个道路满足先进先出原则。

引理3：如果每个道路在起源结和目的节点之间满足先进先出原则，极小的旅行时间作用然后满足先进先出原则。

证明：假设 是一个最短的路径，在所有道路之中从起源节点o到目的节点q和离开节点o在时间t。道路 离去的旅行时间出发节点o在时间t表示 。从 是一个最短路径当离去节点o在时间t，我们有 。因为先进先出原则也适用在道路 ，我们有 。因此，我们有 。所以，如果每个道路在起始节点o和目的节点q之间满足先进先出原则，那么最少旅行时间函数满足先进先出原则。

命题3使用于第4章的B部分开发在最少旅行时间下的动态下界。

第6章 动态A*改进算法

在动态网络中，你也许需要解决一个一对一最短的道路问题对指定的离开时间t或许多或所有离开时间。在这个部分，我们首先学习一对所有动态最短路径问题的公式化在先进先出动态网络的计算。然后一个静态下界被开发解决一对一最短路径问题指定的离开时间t，使用A*改进算法。我们以后开发动态下界和被混合的静态动态下界，那探索特别特征动态网络解决一对一最短的道路问题所有离开时间。

A． 给定出发时间的一对一最短路径问题

一对一最短的道路问题的公式与一对所有最短路径问题的公式是相似的。唯一的区别是，为一对一最短路径问题，如果使用LS算法，当目的节点被选择时算法停止。我们首先提出一对所有动态最短路径问题的一种知名的公式。

1) 指定的离开时间的动态最短路径问题的公式：一对所有动态最短的道路问题的宗旨将发现最短路径从起始节点o，在时间间隔0时出发，到所有其它节点。最少旅行时间 由以下等式定义（[17]和[18]）：

 

引理4（从[18]借用）：如果先进先出原则被满足，那上述最短路径问题公式等价于下面的公式：

 

证明：由先进先出原则， 。因此，这两个公式是等价的。

这种公式与最优性条件下静态最短路径问题是相似的。它表示，静态最短路径算法可能被扩大解决一对所有最短的道路问题在先进先出动态网络。本文的动态A*改进算法从这种公式获得。改进不同只在于确定 的下界 ，最少旅行时间在（节点，时间）对 之间，对于目的节点q来说。公式是合法的如果离开时间 在起始节点不一定是等于零，因为它满足改变 的最小到达时间的定义而不是最少旅行时间。

以下为动态A*改进算法的描述，用于寻找一个在（起始，目的）节点对 之间，离开起始节点时间为 的最快速路径。

步骤1） 初始化：

     

步骤2） 节点选择：

 

步骤3） 停止规则：

      如果 则停止，否则继续。

步骤4） 更新 和距离标签

      对于每个 ：如果

      那么 ；

      如果 。返回步骤2）。

2）静态下界：在早先分部我们显示了A*算法的一个动态变形解决一对一动态最短路径问题在一个动态先进先出网络。按照在第4章B部分的说明，A*算法的效率取决于 下界的质量。所以，为了适应A*算法高效率，我们需要开发有效的 下界。因为我们以后将看见在本文里，它是可能发现更好的 下界在比那些常用在静态网络，譬如那些根据欧几里德的距离。

对所有 ，令 。我们构造一个虚拟静态网络，以 作为路链旅行时间。所有对一静态最短路径算法适用了于虚拟网络并且目的节点q导致最少旅行时间 表示从每个节点i到节点q。在我们之下证明 是一个 的下界对于每个节点时间对 。这个下界被认为是静态的，因为它不取决于起始节点的离开时间。注意，对于一个给定的目的地， 只需要在预处理步骤被计算一次。

引理5：对于每个节点i和出发时间t， 。此外， 满足一致性假设，例如，对于路链 ， 。

证明：首先我们证明对于每个节点i和出发时间t， 。假设p是一个在虚拟静态网络中从节点i到节点q的最短路径。我们有 。假设 是一个从i到q的最短路径，在时刻t离开节点i。既然 也是虚拟静态网络中的一个节点i和节点q之间的可行的路径，那我们有 。根据 的定义，对于任意时间间隔t的每个 ， 。因此， 。所以， 。

现在我们来证明 满足一致性假设。在虚拟静态网络中，由最优状况我们有 。由 的定义，我们有 。因此， 。

可作为 的一个下界。既然静态下界满足一致性假设，不管算法在什么时候选择一个节点，从目标节点到此节点的最短路径就被决定了。这样，在算法的最后一步，我们不需要考虑那些已经在被选择节点集合中的节点。我们只对不在被选择节点集合中的相邻节点更新标签 。

考虑路链的旅行时间是它欧几里德的距离由旅行速度的有些价值划分的二维栅格网络。下界根据欧几里德的距离由划分典型地获得欧几里德的距离在当前的结和目的节点之间，由极小速度的最低值在所有路链之中。这个"欧几里德的" 下界总是小于或等于，和无法因而胜过，静态下界被开发在这个分部。因而，我们进一步不比较这两个下界在实验性部分，因为我们知道由理论静态下界总是更加有效的。注意欧几里德的下界并且核实一贯性假定。

B． 对应所有出发时间的一对一最短路径问题

一对一最短路径问题所有离开时间包括在发现最短路径从起源节点对一个目的节点为每离开时刻在起源节点。虽然你可能仍然使用 作为下界，我们是对获得改善的下界感兴趣。假设，当计算最快速路径为离开时间，我们已经计算最快速路径为离开时间t-1。在先进先出网络，你可能利用节点果被获得在离开时间t-1减少计算努力为间隔时间t。这观察形成为一个动态最低界面的发展的依据，和一个混杂的最低界面。照原样被显示在实验性部分，这些最低界面正面地冲击计算效率。

1）动态下界：假设，当我们考虑离开时间t在起始节点，极小的旅行时间在时间t之前已经被确定。极小的到达时间在节点i是 ，离开时间t在起源节点。在算法期间，当前的极小的到达时间在节点i是 ，大于或等于 。我们是对获得一个下界 感兴趣，我们从静态下界将获得从一个概念性下界 和被描述在早先分部。引理6为节点i提供一个 的概念性下界，是在一个最短路径对应于离开时间t-1。我们提到这个更低的动态下界作为动态下界。

引理6：为每个离开时间节点t在起源节点和为每个节点i在一个最短路径对应于离开时刻t-1， 是一个 的下界。此外，这个下界表示 ，满足一贯性假定。

证明：我们首先证明 是一个 的下界。由引理3，我们知道先进先出原则也适用于在先进先出网络中的任何两个节点的最少旅行时间。对于从起始节点和节点i之间的最少旅行时间，我们有 。因为时刻 从节点i出发，到达节点q的时间不会早于时刻 从节点i出发，到达节点q的时间，所以我们有： 。这导致 。那么我们有 的下界表示 ： 。

我们现在将证明下界 满足一致性假设。我们要展示下面的不等式是成立的： 。因为 是时刻 从节点i出发到达节点q的最少旅行时间，所以我们有： 。不等式两边同时加上 ，那么： 。不等式的左边等于： 。不等式的右边等于： 。后面的项等于 。这样，我们就证明了不等式 是成立的。因此， 满足一致性假设。

引理6可能被推断获得一个 下界为节点i在一个最短路径对应于离开时刻t-k，k是一个正整数。我们不居住在这些下界因为数字节点果表示，最有效的实用下界被获得了值k=1。这些下界可能被使用为不是在一个最短路径对应于离开时间t-1，但是出现在一个最短路径对应于离开时刻t-k。这能是有用的如果它不是可能使用静态下界与动态下界一道正如下面所描述的。

2）混合下界：动态下界是合法的只为节点在引起的最短路径离去起源节点在时间t-1。为不是在早先最短路径的节点，我们使用 作为一个下界。这意味着，二类型下界将被使用，因为没有所有节点被保证是在一个早先最短路径。这也许导致一致性原则被破坏。

动态下界只是一个概念性节点果，因为不能知道 做着演算在节点i。实际上，你只知道 是一个 的上界。我们现在描述实际的下界是怎样从动态下界中派生出来的。我们知道 。它导致 。所以，我们能使用以下实际下界为节点在引起的最短路径对应于离开时间t-1： 。

后一个实际动态下界的值也许比 小。因此，对每个节点i在普遍的最短路径为离开起始在时间t-1，采取 的最大值和实际动态下界。虽然结果下界不满足一致性假设，但如我们稍候展示的一样，它最终将减少节点被选择的数量。

我们所采用的下界是由下式给出的：

这些下界被称为混合下界，表示为 。

 

图2 一个小型网络

引理7：混合下界不一定满足一贯性假定。

证明：我们提供表示的一个逆例子，一贯性假定由混杂的下界不满意为小网络被描述在图2 。这个网络包括三个节点、三个路链和三间隔时间。数字在路链旁边表示那个路链的旅行时间所有离开时间0，1，和2。例如，[ 8，7，6 ] 在路链(1，3) 意味旅行时间在路链(1，3) 是： 8在间隔时间0，7在间隔时间1，和6在间隔时间2。旅行时间被承担是恒定的在间隔时间2以后。注意每个路链旅行时间满足先进先出原则。

考虑发现最快速路链的问题从起源节点1对目的节点3所有离开时间。如果我们离去节点1在间隔时间0，极小的旅行时间到达节点3是8，并且一个最佳路径是1-3 (旅行时间为道路1-2-3 是) 。现在，让我们考虑时间间隔1在节点1。节点1在前一个最短路径上。这样，混合下界对于节点1就是 。

因为 ，和 ，我们有 。因为节点2不是在早先最短路径，我们使用 作为一个下界： 。这个小网络，如果一贯性假定是满足的我们有： 。但是，这不成立，因为 。因而，在这个网络，混合的下界不满足一贯性假定。所以，混合的下界总之不满足一贯性假定。

为一对一最短路径问题所有离开时间，我们需要确定一个最短路径从起源节点对一个目的节点为每离开时刻t。你也许使用静态下界或被混合的下界。如果你使用静态下界，你不需要反思那些节点在选择的节点设置，因为这些下界满足一贯性假定。混杂的下界，另一方面，不满足一贯性假定。

第7章 计算机实现和实验评价

动态A*改进算法被谈论在早先部分被实施了为计算测试的目的。在动态A*算法为一对一最短路链问题一离开倍，唯一静态最低界面是可应用的。我们提到这实施由DAA*_S 。为一对一最短路链问题所有离开时间，A 的二动态适应* 算法是可能的，使用静态最低界面或混杂的最低界面。我们提到实施根据混杂的最低界面作为DAA*_M 。Dijkstra 的算法并且被实施了为比较目的。注意所有这些算法被停止当目的节点被选择，那时一个最短路链从起源节点对目的节点被确定了。在A 的动态适应的各叠代* 算法和Dijkstra 的算法，你需要选择一个节点以极小的标签从候选节点集。这操作由使用实施堆数据结构。

在文学，A 的表现* 算法通常被描绘根据节点的数量只被选择。节点的数量被选择，然而，也许，单独，不反射这种算法综合效率。这是特别真实的在动态网络。这的原因是那发现一个更好的最低界面通常需要额外计算时间。你然后需要平衡额外计算时间花费获得一个更好的最低界面以这个最低界面也许导致的施行省时。所以，我们下面报告不仅节点的数量由动态A*改进算法选择，而且他们的计算时间。

所有算法被实施了使用C++ 编程语言和被测试了在任意地引起的网络。所有计算次由跑获得了代码在Sun SPARC 5 工作站。节点的数量由或A 的动态适应选择* 算法或Dijkstra 的算法也许变化用不同的起源目的地(OD) 对。节点的数量被选择和Dijkstra 的算法的计算时期非负极小的旅行时间的作用在OD 对之间。这观察有效性可能直觉地被解释如下。从旅行时间变化为不同的OD 对的极小值，查寻区域为OD 对以一个更久的旅行时间比查寻区域一般大的为OD 对以更短的极小的旅行时间。因而，比较二种算法由计算一个最短路链使用oneOD 对不能只导致决定性的结果。所以，当我们分析本文算法的表现，我们比较他们的表现根据一定数量的任意地选择的OD 对，和报告不仅数字结果被获得为各自的OD 对，而且平均这些数字结果。

我们意志第一compareDAA*_S 和DAA*_M 以Dijkstra 的算法使用网络包含3000 个节点、10 000 个链接，和100 间隔时间分析这些算法表现作为OD 对功能。然后我们测试算法在不同的大小网络分析各种算法表现作为测试网络功能的大小。如果适应A * 算法增量以大小的网络，这的储款然后会意味为大网络你也许有益于由使用A 的适应* 算法而不是使用一种算法譬如Dijkstra 的算法。我们进行计算测试使用网络有n节点和3*n 链接(公路网的典型的平均程度是在3) 附近。为所有测试网络，间隔时间的数量是100 。为了估计和分析A 的动态适应的整体表现* 算法与Dijkstra 的算法比较了，各自的网络参量的作用在算法的表现将由变化调查一个指定的参量，当保持其它参量恒定。

A．随机网络发生器

引起任意动态FIFO 网络的网络发电器被实施了使用C++ 编程语言。这台网络发电器的用户输入网络(节点的链接的数字，数字和数字的大小间隔时间) 并且链接旅行时间的范围。你可能并且引起非Fifo 网络，但为本文的目的，只有FIFO 网络将引起，因为动态A*改进算法是合法的为网络这组唯一。

一个任意网络的拓扑节点构引起在二步。我们首先修建保证连通性的子网络，并且我们然后增加任意链接直到链接的一个渴望的数字达到。链接旅行时间任意地被选择从范围由用户测量，使用一致的发行。链接旅行时间引起这样不能满足FIFO 物产。为了获得FIFO 链接旅行时间，以下变革向引起的链接旅行时间作用被申请： ，t是到达时间和是离开时间在节点i的地方。被变换的链接旅行时间 满足FIFO 物产。

B．包含一个出发时间的动态一对一最短路径问题的计算节点果

依照被表明及早在这个部分，为了分析算法的行为谈到不同的OD 对，我们首先DAA*_S 和DAA*_M 与Dijkstra 的算法比较在一个网络以3000 个节点、10 000 个链接，和100 间隔时间。

下面，我们显示计算节点果被获得使用动态A*改进算法和Dijkstra 的算法。因为我们考虑一个一对一最短路链问题的计算一离开倍，只有静态最低界面是可适用的。

 

图3 在一个拥有3 000个节点、10 000条路链和100个时间间隔的网络中，Dijkstra算法和DAA*_S所选择的节点数目的比较。Dijkstra算法所选择的节点平均数目是DAA*_S的5.4倍。

我们比较节点的数量由动态A*改进算法以静态最低界面(DAA*_S) 并且Dijkstra 的算法选择在任意地引起的动态网络。依照被表明以上，Dijkstra 的算法被实施这样，它停止每当目的节点被选择(意味一个最短路链从起源节点对目的节点被确定了) 。图3描述节点的数量由Dijkstra 的算法的基于堆的实施和DAA*_S 选择作为任意地选择的OD 对功能被排序增长的按他们极小的旅行时间的顺序。图表示，为每OD 对，节点的数量由DAA*_S 选择比节点的数量总是较少由Dijkstra 的算法选择。为任意网络以3000 个节点，10 000 个链接，和100 间隔时间，节点的平均数量由Dijkstra 的算法选择尽量是5.4 次节点的平均数量由DAA*_S 选择。图并且表示，节点的数量由Dijkstra 的算法选择，按照说明及早在这个部分，是极小的旅行时间的一个nondecreasing 的作用在OD 对之间。

我们现在比较DAA*_S 和Dijkstra 的算法的计算时代。如同图4 比Dijkstra 的算法的表明，为每OD 对，DAA*_S 的计算时期较少计算时期。为3000 个节点，10 000 个链接这个测试网络，和100 间隔时间，Dijkstra 的算法的平均计算时期是3.2 倍DAA*_S 的平均计算时期。

C．包含所有出发时间的动态一对一最短路径问题的计算节点果

下面，我们显示计算节点果被获得使用动态A*改进算法和Dijkstra 的算法。因为我们考虑一个一对一最短路链问题的计算所有离开次，静态最低界面和被混合的最低界面是可适用的。我们和一样在部分VII-B，那一个动态FIFO 网络以3000 个节点10 000 个链接，和100 间隔时间使用网络。计算时代报告了在这个分部是平均为一对一最短路链问题所有离开次。首先，我们比较节点的数量由动态A*改进算法选择根据混杂的最低界面(DAA*_M) 对节点的数量由适应选择根据静态最低界面(DAA*_S) 为任意地引起的动态网络。图5 表示，为每OD 对，节点的数量由DAA*_M 选择比节点的数量是较少由DAA*_S 选择。

我们现在比较DAA*_M 和DAA*_S 的计算时代在任意地引起的网络。图6 比DAA*_S 的计算时期表示，为大多数OD 配对，DAA*_M 的计算时期是较少。为一些节点，DAA*_M 的计算时期是大于DAA*_S 的计算时期。这是因为额外时间花费计算最低界面是更多比时间由使用保存这些最低界面。为这个测试网络以3000 个节点10 000 个链接，和100 间隔时间，DAA*_S 的平均计算时期是1.5 倍DAA*_M 的平均计算时期。

 

图4 在一个拥有3 000个节点、10 000条路链和100个时间间隔的网络中，Dijkstra算法和DAA*_S的计算时间的比较。Dijkstra算法的平均计算时间是DAA*_S的3.2倍。

 

图5 在一个拥有3 000个节点、10 000条路链和100个时间间隔的网络中，DAA*_S和DAA*_M所选择的节点数目的比较。DAA*_S所选择的节点平均数目是DAA*_M的2.1倍。

 

图6 在一个拥有3 000个节点、10 000条路链和100个时间间隔的网络中，DAA*_S和DAA*_M的计算时间的比较。DAA*_S的平均计算时间是DAA*_M的1.5倍。

 

图7 在一个拥有3 000个节点、10 000条路链和100个时间间隔的网络中，Dijkstra算法和DAA*_M的计算时间的比较。Dijkstra算法的平均计算时间是DAA*_M的4.8倍。

 

图8 在一个拥有3 000个节点、10 000条路链和100个时间间隔的网络中，Dijkstra算法和DAA*_M所选择的节点数目的比较。Dijkstra算法所选择的节点平均数目是DAA*_M的11.3倍。

从计算节点果被总节点以上，我们能并且比较A 的表现* 算法以混杂的最低界面(DAA*_M) 并且Dijkstra 的算法表现。我们首先比较节点的数量由DAA*_M 和Dijkstra 的算法选择在3000 个节点、10 000 个链接和100 间隔时间任意地引起的动态网络。图7 表示，为everyODpair，节点的数量由DAA*_M 选择比节点的数量是较少由Dijkstra 的算法选择。为这个网络，节点的平均数量由Dijkstra 的算法选择是大约节点的平均数量选择由DAA*_M 的11 倍。

图8 表示，为每OD 对，DAA*_M 的计算时期比Dijkstra 的算法的计算时期是较少。为测试网络被使用，Dijkstra 的算法的平均计算时期是4.7 倍DAA*_M 的平均计算时期。注意，相似与无花果。3和4，两棵无花果。7 和8 表示，节点的数量被选择, 和计算时间，Dijkstra 的算法nondecreasing 极小的旅行时间的作用在OD 对之间。

D．关于网络规模的函数和网络参数的性能研究

我们首先显示DAA*_S 、DAA*_M 和Dijkstra 的算法的实施的表现为不同的网络大小当保留链接的数量在测试网络相等与三倍节点的数量。采取弧的数量是三乘节点的数量的测试网络的原因，将看齐比率在链接的数量和节点之间的数量是典型地大约3 的交通网络。

 

图9 不同规模网络下，不同算法所选择的节点平均数目的比较。NxxMyy表示网络包含xx00个节点和yy00条路链。例如，N50M150表示网络规模为包含500个节点和15 000条路链。

 

图10 不同规模网络下，不同算法的计算时间的比较。NxxMyy表示网络包含xx00个节点和yy00条路链。例如，N50M150表示网络规模为包含500个节点和15 000条路链。

图9表示，节点的数量由Dijkstra 的、DAA*_S 和DAA*_M 算法选择增加以网络的大小，但以不同的率。注意- 轴不跟随一个线性标度在无花果。9 和10 。增长率节点的数量的由Dijkstra 的算法选择比增长率高级节点选择的byDAA*_S 的数量的。这后者率比增长率高级节点的数量的由DAA*_M 选择。图10 表示，计算时间储款为不同的实施相似地表现与节点的数量由算法选择。

节点果被陈列在无花果。9 和10 建议，为网络以更大的大小，动态A*改进算法导致更大的储款根据节点的数字被选择并且根据计算时间。

在剩余这个分部，我们分析DAA*_S 、DAA*_M 和Dijkstra 的算法的计算机实施的效率，作为不同的网络参量功能当保持其它参量恒定。首先，我们考虑链接的数量的作用当保留节点的数量和间隔时间的数量恒定。图11 表示，为网络以1000个节点和100 间隔时间，节点的数量由DAA*_S 选择，DAA*_M 或Dijkstra 的算法是几乎链接的数量的恒定的作用。这可能被解释如下。如果节点的数量在网络是恒定的，下跌在查寻区域对应于算法为指定的目的地节点的平均数量不会改变既使链接的数量改变。但是，因为你也许期望，节点的数量由Dijkstra 的算法选择大于节点的数量由或DAA*_S 或DAA*_M 算法选择。

图12表示，为网络以1000 个节点，Dijkstra 的、DAA*_S 和DAA*_M 算法的计算时期增加以链接的数量，但以不同的率。增长率Dijkstra 的算法的计算时期的比增长率高级对应于DAA*_S 和DAA*_M 算法。虽然节点的数量由不同的算法选择是几乎恒定的，更多链接将被扫描每当节点被选择如果链接的数量增加。因而，计算时间增加以链接的数量。

 

图11 在包含1000个节点、100个时间间隔，且路链数目变化的网络中，不同算法的所选择的节点平均数目的比较。

 

图12 在包含1000个节点、100个时间间隔，且路链数目变化的网络中，不同算法的平均计算时间的比较。

 

图13 在包含9000条路链、100个时间间隔，且节点数目变化的网络中，不同算法所选择的节点平均数目的比较。

 

图14 在包含9000条路链、100个时间间隔，且节点数目变化的网络中，不同算法所的平均计算时间的比较。

现在，我们审查节点的数量的作用在计算表现当保留链接的数量和间隔时间的数量恒定。图13 表示，为网络以9000 个链接和100 间隔时间、节点的数量由DAA*_S 选择，DAA*_M 或Dijkstra 的算法增量以节点的数字，但以不同的率。增长率节点的数量的由Dijkstra 的算法选择比增长率高级对应于DAA*_S 和DAA*_M 算法。

图14象被显示了在图9 表示，为测试网络以9000 个链接和100 间隔时间，不同的算法的计算时代相似地表现与节点的数量被选择，作为节点的数量的作用在网络，。数字节点果表示，计算挽救比率不变化作为间隔时间功能的数量。数字节点果支持这个节点论不包括在本文里，但是节点论是直觉地合法的。

第8章 总结

在本文里，我们提出了A 的高效率的适应* 算法为计算的最快速路链在一个起源节点和一个目的节点之间在动态网络，为一个或多离开时间在起源节点。A 的这些动态适应* 算法根据有效的最低界面在极小的旅行时间、那盘剥动态数据FIFO 物产和一个动态网络的时间膨胀的含蓄表示法的特别节点构。适应的算法被实施了并且他们的计算表现被评估了和实验性地被测试了。动态A*改进算法的计算机实施的表现与的Dijkstra 的算法动态适应比较被停止当目的节点被到达。节点果使用网络包含3000 个节点、10 000 个链接，和100 间隔时间显示了挽救比率11，根据节点的数字被选择，并且挽救比率5 根据计算时间。网络大小的作用在这些适应表现计算上也被学习了。它被显示，计算储款，根据两个节点被选择和计算时间的数字，增加以网络大小。这些令人鼓舞的节点果展示算法的效率被开发在本文里。

我们现在提出一些逻辑引伸对研究工作出席在本文里。首先，它会是有趣对连续时间动态网络扩大本文的节点果。静态最低界面依然是合法在这上下文，当动态最低界面也许需要适应为你知道唯一最快速路链计算的节点果在某一时间瞬时的更加早期的有限数字的案件。讨论在部分的末端VI-B-2 总节点一个这样的动态最低界面。其次，你也许并且考虑调查A 的引伸* 算法对非Fifo 网络。注意静态最低界面是合法的在这上下文。第三，本文提议可能性算法为设计和开发高效率的平行的实施为动态最短路链的计算。分解战略可能被开发在对领域起源目的地节点和网络拓扑节点构。一个高效率的战略应该平衡通信时间、计算时间和无所事事的时间。终于，想法被提出在本文里可能被扩大开发基于时间的算法，为离散时间并且连续时间动态网络，计算最短路链从一个起源节点对所有其它节点如果你改变离开时间在起源。在[ 22 ]，例子的这样引伸被开发计算起源唯一极小的旅行时间道路树所有可能的离开次在连续时间FIFO 动态网络。其它基于时间的算法设计为其它动态最短路链问题，是持续的研究主题。第一作者和其它合作者开发了算法根据优化的概念，可能被观看分享，某种程度上，一些根本相似性以派生在本文里。算法导致了鼓励计算结果[ 23]。我们将报告关于这些算法在即将到来的文件里。

参考文献

[1] I. Chabini and B. Dean, “Shortest path problems in discrete-time dynamic networks: Complexity, algorithms, and implementations,” Massachusetts Institute of Technology, Cambridge, MA, Tech. Rep., 1999.

[2] I. Chabini and V. Yadappanavar, “Advances in discrete-time dynamic data representation with applications to intelligent transportation systems,” Transport. Res. Rec., vol. 1771, pp. 201–208, 2001.

[3] E. P. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE Trans. Syst. Sci. Cybern., vol. SSC-4, no. 2, pp. 100–107, 1968.

[4] D. E. Kaufman and R. L. Smith, “Fastest paths in time-dependent networks for intelligent-vehicle-highway systems application,” IVHS J., vol. 1, pp. 1–11, 1993.

[5] J. L. Bander and C. C. White, III, “A heuristic search algorithm for path determination with learning,” IEEE Trans. Syst., Man, Cybern. A, vol. 28, pp. 131–134, 1998.

[6] I. Chabini, “Shortest paths in continuous-time traffic networks with time-dependent piece-wise linear link travel time and cost functions,” Transport. Res. Part B: Methodological, 2001, to be published.

[7] J. N. Nilsson, Problem-Solving Methods in Artificial Intelligence. New York: McGraw Hill, 1971.

[8] I. Pohl, “Heuristic search viewed as path finding in a graph,” Artif. Intell., vol. 1, pp. 193–204, 1970.

[9] J. Pearl, Heuristic Intelligent Search Strategies for Computer Problem Solving. Reading, MA: Addison-Wesley, 1984.

[10] L. B. Golden and M. Ball, “Shortest paths with Euclidean distance: An explanatory model,” Networks, vol. 8, pp. 297–314, 1978.

[11] R. Sedgewick and J. S. Vitter, “Shortest path in Euclidean graphs,” Algorithmica, vol. 1, pp. 31–48, 1986.

[12] J. L. Bander and C. C. White, III, “A new route optimization algorithm for rapid decision support,” in Proc. SAE/IEEE-VTS VNIS, Detroit, MI, 1991, pp. 709–728.

[13] J. W. Lark, C. C. White, III, and K. Syverson, “A best-first search algorithm guided by a set-valued heuristic,” IEEE Trans. Syst., Man, Cybern., vol. 25, pp. 1097–1101, 1995.

[14] A. Ziliaskopoulos and H. Mahmassani, “Time-dependent shortest path algorithms for real-time intelligent vehicle highway system applications,” Transport. Res. Rec., no. 1408, pp. 94–100, 1993.

[15] K. L. Cooke and E. Halsey, “The shortest route through a network with time-dependent internodal transit times,” J. Math. Anal. Appl., vol. 14, pp. 492–498, 1966.

[16] I. Chabini, “A new shortest paths algorithm for discrete dynamic networks,” in Proc. 8th IFAC Symp. Transport Systems, 1997, pp. 551–556.

[17] , “Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time,” Transport. Res. Rec., pp. 170–175, 1998.

[18] S. E. Dreyfus, “An appraisal of some shortest path algorithms,” Oper. Res., vol. 17, pp. 395–412, 1969.

[19] B. H. Ahn and J. Y. Shin, “Vehicle routing with time windows and timevarying congestion,” J. Opl. Res. Soc., vol. 42, pp. 393–400, 1991.

[20] I. Chabini and V. Yadappanavar , “A bitwise algorithm for fastest paths in time-dependent networks,” Transport. Res. Rec., vol. 1771, pp. 209–218, 2001.

[21] R. Ahuja, T. Magnanti, and J. Orlin, Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs, NJ: Prentice-Hall, 1993.

[22] I. Chabini and V.Yadappanavar, “Algorithms for single-origin minimum time path problems in networks with piecewise linear time-dependent link travel time functions,” Transport. Res. Rec., 2002, to be published.

[23] N. Grier and I. Chabini, “A new algorithm for determining minimum time path trees in FIFO time dependent networks,” presented at the Transportation Research Board Annu. Meeting, Washington, DC, Jan. 2002.