1.概述

在本教程中,我们将讨论在访问所有节点的图表中找到最短路径。

首先,我们将定义问题并提供解释它的示例。然后,我们将讨论两种不同的方法来解决这个问题。

2.定义问题

假设我们有一个图表,G,它包含V.节点编号0.V - 1。另外,我们有E.连接这些节点的边。这些边缘中的每一个都具有与之相关的权重,表示使用该边缘的成本。

我们的任务是找到通过给定图中的所有节点的最短路径。

回想一下,两个节点之间的最短路径\ textbf{一}\ textbf {b}是在所有可能的路径之间具有最低成本的路径\ textbf{一}\ textbf {b}

在此任务中,我们查找涵盖所有可能的启动和结束节点的所有路径。此外,我们可以多次访问相同的节点。让我们来看看一个更好的理解的例子。

假设我们有以下图:

正如我们所看到的,那里有许多路径通过给定图中的所有节点,但它们中的最短路径\ textbf {0 \ lightarrow 1 \ lightarrow 4 \ lightarrow 1 \ lightarrow 2 \ lightarrow 3},它的成本等于6.;T.因此,给定图中访问所有节点的最短路径具有等于的成本\ textbf {6}

3.蛮力方法

3.1。大意

这里的主要想法是生成所有可能的路径,并获得具有最低成本的路径。

首先,我们将生成节点的所有可能的排列。每个排列将代表图表中访问节点的顺序。路径的成本将等于每两个连续节点之间的所有最短路径的成本。

其次,我们将使用Floyd-Warshall算法计算每两个连续节点之间的最短路径。回忆,弗洛伊德战争算法计算一个图中所有节点对之间的最短路径。

最后,访问图中所有节点的最短路径将具有所有可能的路径中的最小成本。

3.2。执行

让我们来看看这样的实现:

呈现由QuickLaTeX.com

最初,我们声明一个叫做阵列距离,使用Floyd-Warshall算法存储给定图中每对节点之间的最短路径。

接下来,我们生成所有可能的置换,它代表我们可以遵循的所有可能路径。然后,对于每个排列,我们将通过添加每两个连续节点之间的最短路径的长度来计算它的成本;计算当前排列的成本后,我们会检查是否存在成本小于回答值,然后我们将更新回答

最后,我们返回回答,它存储访问给定图中所有节点的最短路径的成本。

3.3。复杂

这里的时间复杂度是\ boldsymbol {o(v ^ 3 + v \ times v!)}。让我们检查这种复杂性背后的原因。

首先,Floyd-Warshall算法具有复杂性o(v ^ 3)。接下来,所有不同排列的数量V.节点等于阶乘V.以及每个排列,我们通过通过它来计算成本,所以它是o(v)

因此,总复杂性将是o(v ^ 3 + v \ times v!)

4.Dijkstra算法的方法

4.1。大意

在这种方法中,我们将使用Dijkstra算法的修改版本。对于每个状态,我们需要跟踪除了当前的所有访问的所有访问节点。因此,要获取每个状态的所有访问的节点,我们将表示它们作为位掩码,其中每个位接通的手段之前我们以前访问过这个节点。

最后,我们的答案我们将成为所有节点的最小值,其中包含BitMask(访问所有节点)。

4.2。执行

让我们来看看这样的实现:

呈现由QuickLaTeX.com

最初,我们声明一个叫做阵列成本,它存储访问节点子集的某些节点的最短路径。我们还声明了存储节点和位掩码的优先级队列。BitMask表示访问此节点的所有访问节点。此优先级队列将根据状态的成本对状态进行排序。

接下来,我们尝试通过将每个节点添加到优先级队列并转动它们的位置来启动每个节点的最短路径。然后,我们运行Dijkstra算法。

我们迭代的孩子节点当前的节点。对于每一个人孩子,我们检查是否是成本访问大于当前节点的特定子集时的值成本加上连接的边缘的重量当前的节点与孩子。在本例中,我们需要更新成本价值孩子节点。此外,我们添加了孩子和当前面具按位或者2 ^ {child}到优先级队列。这个面具意味着我们转动了一下孩子节点上。

最后,我们的答案将是访问所有节点的所有节点成本中的最小值。

4.3。复杂

这里的时间复杂度是\ boldsymbol {o(v \ times 2 ^ {v} \ times log(v \ times 2 ^ {v}))}, 在哪里V.是节点数量和2 ^ V.是所有可能的节点子集的数量,以及日志(V \ * 2 ^ {V})将每个状态添加到优先级队列。

结论

在本文中,我们介绍了找到所有节点的最短路径的问题。我们解释了两种不同方法背后的主要想法,以解决这个问题并通过他们的实施。

对这篇文章的评论关闭!