algorithm - 最小续航里程电动汽车需要经过每个城市

Question

我有点卡在这个任务上。

我们有一个矩阵，其中包含每个城市(60 个城市)之间的距离。我们必须开着电动汽车至少经过每个城市一次。每个城市都有汽车充电点。我们可以在一个城市停留多少次没有限制。

我必须找到汽车一次充电所需的最小续航里程，这样我们才能穿过每个城市。

我应该如何遇到这个任务？

Answer 1

更新:

而 MST (minimum spanning tree)适用于这个问题，它可能 ¹没有最佳时间复杂度。该问题应视为MSBT (minimum bottleneck spanning tree)相反，存在以边数为线性时间复杂度的算法，例如Camerini's_algorithm .

---

您正在寻找 MST 的最大边缘。寻找 MST 的著名算法有很多，其中 Kruskal's和 Prim's (btilly 在他的回答中使用)是最容易实现的。

很容易看出，为什么MST的最大边缘足以开车穿过每个城市:你可以穿越所有城市，在每个城市充满电，只驾驶属于树的道路。

至少需要 MST 的最大边的范围，否则您将无法访问该边所连接的两个城市。这可以从 Kruskal 算法的构造方式中看出。如果只取小于 MST 最大边的边，则 Kruskal 算法将无法将所有顶点连接成单个连通分量。

---

假设有一棵最小生成树，其边大于其他(最小或非)生成树的最大边。然后我们将尝试用较小的替换它。为此，首先删除这条边。现在我们剩下两组顶点。第二棵树必须用边连接这些集合。让我们把这条边添加到第一棵树上。由于这条边比删除的边小，所以我们得到了一棵边的总和小于最小生成树的树，所以这棵树一开始就不可能是最小生成树，并且存在矛盾。总结:

• 较大的生成树不能有较小的最大边
• 生成树的每个最小值的所有最大边都是相同的

第一个语句表示 MST 是要寻找解决方案的树，第二个语句表示使用哪种算法来查找 MST 无关紧要