基于关键图的带插图的最短路径算法-第2部分：Floyd-Warshall和A-Star算法
在本系列文章的第1部分中，我提供了图数据结构的快速入门，并承认有几种基于图的算法，其中最著名的是最短的路径/距离算法，最后说明了Dijkstra和Bellman-Ford算法。继续最短的路径/距离算法，我在本文的第2部分中说明了Floyd-Warshall和A *（A星）算法。如第1部分所述，虽然在线上的许多教科书和参考性资源中都充分介绍了这些算法的内部原理，但我觉得没有多少人提供直观的示例来说明处理步骤的足够细致程度，从而使他们易于理解其工作原理。细节。此外，
Floyd-Warshall算法
Floyd-Warshall算法是一种基于动态编程的算法，用于计算允许负权重的加权图中每对顶点之间的最短距离。动态编程是一种解决问题的方法，在该方法中，基本上以迭代方式递增地解决复杂的问题，其方式是使用先前迭代中计算出的值来计算当前迭代中的值。这样，为了有资格进行动态编程，应将问题分解为具有相同问题上下文的子问题。Floyd-Warshall采用动态编程方法，将两个顶点之间的路径划分为两个子路径，这两个子路径通过第三中间顶点连接。例如，可以将顶点A和D之间的路径视为通过第三中间顶点C的路径，以使距离d（A，D）可以计算为距离d（A，C）与d（C，D）的总和，即d（A，D）= d（A，C）+ d（C，D），然后是两者之间的路径顶点A和C可以进一步视为通过另一个中间顶点B的路径，因此d（A，C）= d（A，B）+ d（B，C）。这样，计算顶点之间的距离的主要问题被分为计算中间距离的子问题，其中，主要问题和子问题都处理寻找两个顶点之间的距离的相同上下文。在动态规划方法的每个步骤中，Floyd-Warshall算法都会确定两个顶点之间的最短暂定距离。注意，两个顶点之间的距离被认为是暂时的，直到算法确认它是最短的距离。该算法的核心是，顶点A和C之间的最短距离对于A和C之间到目前为止的暂定最短距离或A到B以及B到C的暂定最短距离之和而言是最小的，其中B是中间顶点。该算法迭代图的顶点，并在每次迭代时，将当前迭代顶点视为中间对象，同时评估其他顶点对之间的暂定距离。在测试图形中的每个可能对以及一对之间的每个可能中间顶点之后，该算法完成。该算法迭代图的顶点，并在每次迭代时，将当前迭代顶点视为中间对象，同时评估其他顶点对之间的暂定距离。在测试图形中的每个可能对以及一对之间的每个中间顶点之后，该算法完成。该算法迭代图的顶点，并在每次迭代时，将当前迭代顶点视为中间对象，同时评估其他顶点对之间的暂定距离。在测试图形中的每个可能对以及一对之间的每个中间顶点之后，该算法完成。
图3：Floyd-Warshall算法的图示
图3说明了执行Floyd-Warshall算法的逻辑步骤。本质上，该算法维护一个邻接矩阵，该矩阵包括在每个迭代中将更新的每对顶点之间的估计距离。该示例图包含4个顶点，因此算法将维持大小为4 x 4 = 16个值的相邻矩阵。作为一个例子，中值为3 次行和2 次列代表顶点3和顶点2之间的估计距离。在步骤0，算法启动矩阵值。该算法将顶点到自身的距离设置为0，如矩阵的对角线值所示。该算法将任意两个顶点之间的已知直接边缘权重设置为矩阵中的初始距离。对于所有其他没有直接边的顶点对，该算法将距离设置为矩阵中的无穷大。
然后，该算法开始步骤1。在步骤1，该算法采用动态编程方法，通过将顶点1视为中间顶点来评估一对顶点之间的最小暂定距离。因此，该算法将顶点i和j之间的暂定距离A1（i，j）评估为A0（i，j）或A0（i，1）+ A0（1，j）的最小值。 i和j，其中i不等于j且i和j都不等于1。在这种情况下，A1是在步骤1中更新的邻接矩阵的副本，而A0是在启动步骤0处创建的邻接矩阵。 A1（i，j）= Min（A0（i，j），A0（i，1）+ A0（1，j））?i≠j?i≠1 given j≠1。因为在执行过程中必须满足公式约束，该算法将固定第1行的第1行，第1列和对角线值，如图3所示。这意味着在此步骤中无法更新固定值。这样，在步骤1中可以评估的唯一距离是A1（2、3），A1（2、4），A1（3、2），A1（3、4），A1（4、2）和A1 （4、3）。该算法将使用公式A1（2，3）= Min（A0（2，3），A0（2，1）+ A0（1，3））来评估值A1（2，3）。类似地，算法将使用公式A1（4，3）= Min（A0（4，3），A0（4，1）+ A0（1，3））来评估值A1（4，3）。如图3步骤1所示，该算法将相应地评估和更新A1矩阵的值以完成步骤1。这样，在步骤1中可以评估的唯一距离是A1（2、3），A1（2、4），A1（3、2），A1（3、4），A1（4、2）和A1 （4、3）。该算法将使用公式A1（2，3）= Min（A0（2，3），A0（2，1）+ A0（1，3））来评估值A1（2，3）。类似地，算法将使用公式A1（4，3）= Min（A0（4，3），A0（4，1）+ A0（1，3））来评估值A1（4，3）。如图3步骤1所示，算法将相应地评估和更新A1矩阵的值以完成步骤1。因此，在步骤1中可以评估的唯一距离是A1（2、3），A1（2、4），A1（3、2），A1（3、4），A1（4、2）和A1 （4、3）。该算法将使用公式A1（2，3）= Min（A0（2，3），A0（2，1）+ A0（1，3））评估值A1（2，3）。类似地，算法将使用公式A1（4，3）= Min（A0（4，3），A0（4，1）+ A0（1，3））评估值A1（4，3）。如图3步骤1所示，该算法将相应地评估和更新A1矩阵的值以完成步骤1。3）使用公式A1（4，3）= Min（A0（4，3），A0（4，1）+ A0（1，3））。如图3步骤1所示，该算法将相应地评估和更新A1矩阵的值以完成步骤1。3）使用公式A1（4，3）= Min（A0（4，3），A0（4，1）+ A0（1，3））。如图3步骤1所示，该算法将相应地评估和更新A1矩阵的值以完成步骤1。
然后，该算法开始步骤2。在此步骤中，该算法采用动态编程方法，通过将顶点2视为中间顶点来评估一对顶点之间的最小暂定距离。本质上，在步骤2中评估距离的动态编程公式由A2（i，j）= Min（A1（i，j），A1（i，2）+ A1（2，j））i≠j?i给出≠2?j≠2。在这种情况下，A2是在步骤2中更新的邻接矩阵的副本，而A1是在步骤1中更新的邻接矩阵的副本。在此步骤中，算法固定第2行，第2列和对角线值，因此可以在步骤2中评估的距离为A2（1、3），A2（1、4），A2（3、1），A2（3、4），A2（4、1）和A2 （4、3）。该算法将使用公式A2（1，3）= Min（A1（1，3），A1（1，2）+ A1（2，3）来评估值A2（1，3）3））。类似地，该算法将使用公式A2（4，3）= Min（A1（4，3），A1（4，2）+ A1（2，3））来评估值A2（4，3）。使用如图3步骤2所示的方法，该算法将评估和更新A2矩阵的值并完成步骤2。以类似的方式，该算法执行步骤3和步骤4。请注意，在步骤3，该算法将评估通过使用动态编程公式A3（i，j）= Min（A2（i，j），A2（i，3）+ A2（3，j）将顶点3作为中间顶点来处理一对顶点之间的最小暂定距离））?i≠j?i≠3?j≠3，其中A3是在步骤3中更新的邻接矩阵的副本，而A2是在步骤2中更新的邻接矩阵的副本。
从图中可以推断出，该算法执行了N个步骤，其中N是图形中的顶点数。在每个步骤中，该算法计算最（N 2 -暂定距离值的3N + 2）号。因此，通过该算法评价的距离的总数量为N给定x（N 2 - 3N + 2）。因此，Floyd-Warshall算法的时间复杂度约为N 3。此时间复杂度与执行Dijkstra算法（时间复杂度为N 2）N次迭代相同，其中在每次迭代中，图中的一个顶点被视为源顶点，以评估其与其余顶点的距离。
A *（A星）算法
A *算法是一种基于启发式的，贪婪的，最佳优先搜索算法，用于查找加权图中从源顶点到目标顶点的最佳路径。如第1部分所述，如果算法在执行的每个步骤中都利用局部最优解，并且期望这种局部最优解最终会导致全局最优解，那么该算法就是贪婪的。A *算法基于贪婪的期望，即评估成本最低的顶点是路径上的最佳顶点，这将导致从起始顶点到目标顶点的最佳路径。基于两个成本组成部分评估成本的增量估算。如果V是路径上的下一个顶点，则成本估算值由f（V）= h（V）+ g（V）给出，
图4：Dijkstra的算法示例
图5：纯贪婪最佳优先算法示例
如第1部分中所示，如图4所示，Dijkstra的算法保证了从源顶点A到目标顶点F的最短路径，但是以计算从源顶点A到所有其他顶点的最短路径为代价。Dijkstra的算法贪婪地选择了路径上的下一个顶点完全基于顶点与源顶点之间的距离。Dijkstra的算法未考虑任何指示下一个顶点与目标顶点有多接近的启发式算法。在示例中，由Dijkstra算法计算出的最短路径为{A，B，D，F}。另一方面，如图5所示，纯启发式驱动的，贪婪的，最佳的第一算法用于纯粹基于顶点与目标启发式值所指示的目标顶点的接近度来挑选下一个顶点。它没有考虑下一个顶点与源顶点之间的距离。如图5所示，从源顶点A开始，该算法首先选择顶点E作为下一个顶点，因为与顶点B和C相比，该算法具有较低的启发式。然后从顶点E开始，该算法选择顶点G作为下一个顶点，因为与顶点D相比，它具有较低的启发式，最后从顶点G开始，该算法选择了启发式为0的目标顶点F。因此，在此示例中，由纯贪婪最佳第一算法计算出的最优路径为{A，E， G，F}。
可以将A *视为试图结合两全其美的算法-迪克斯特拉（Dijkstra）和纯贪婪的最佳优先算法。本质上，A *算法不仅考虑下一个顶点与h（n）指示的目标顶点之间的距离，而且考虑下一个顶点与g（n）指示的源顶点之间的距离，以找到最佳路径。从源顶点开始，该算法将评估所有邻居的f（n）= h（n）+ g（n）值，并将选择f（n）值最低的邻居V作为路径上的下一个顶点。该算法将重复计算顶点V的邻居的f（n）值，并选择具有最低f（n）值的下一个顶点。该算法重复此过程，直到评估达到目标顶点为止。
图6：A *算法的图示
图6说明了执行A *算法的逻辑步骤。有意简化了步骤，以确保重点放在理解直觉上。图中算法的目标是找到源顶点A和目标顶点F之间的最佳路径。加权图中的每个顶点都分配有相对于目标顶点的启发式值。该算法维护一个表示路径顶点的有序集合，该集合最初包含源顶点A。如图6所示，在步骤1中，该算法从源顶点A开始，并计算f（n）= h（n）+ g（n）对于其每个邻居B，C和E。该算法选择顶点E作为次佳顶点，因为其f（n）值10是最低的，而B的值为13，C的值为11。 E到设置的路径顶点。在步骤2 该算法移至顶点E并计算顶点E的每个邻居的f（n）值-在示例中，顶点C的值为23，顶点D的值为11，顶点G的值为13。由于顶点D的f（n）值最低，因此算法选择顶点D为次佳顶点，并将其添加到路径顶点集。然后，算法在步骤3移至顶点D并计算其邻居的f（n）值-顶点C的值为28，顶点F的值为11，顶点G的值为20。由于顶点f最低，因此选择了顶点F。 （n）值，将顶点F添加到设置的路径顶点并移至顶点F。该算法确定其已到达目标顶点F并停止执行。生成的路径顶点集包含最佳路径{A，E，D，F}。
采用A *算法的主要挑战之一是确定顶点启发式值。提出了一些计算精确值或近似值的方法，这些方法的细节可能是另一个讨论主题。无论采用哪种方法，通常都建议分配给顶点的启发式值是不同的，这样就不会有两个顶点获得相同的启发式值。这是为了避免在多个顶点最终获得相同的f（n）值时打破潜在的平局。启发式计算方法的选择也会影响A *算法的时间复杂度。在最坏的情况下，时间复杂度可能与需要评估f（n）值的顶点数量成指数关系。
更多算法
在本文的后续部分中，我将用具体的插图介绍其他基于图的最短路径算法，并希望这些插图将有助于理解此类算法背后的直觉。

关注 CDA人工智能学院 ，回复“录播”获取更多人工智能精选直播视频！