查找给定源和一组目标之间的最短路径

Question

你会得到一个加权连接图（20个节点），所有边的权重都是正的。我们有一个从A点开始的机器人，它必须在B点，D和E点通过。这个想法是找到连接所有这 4 个点的最短路径。机器人的电池电量也有限，但在某些点可以充电。

在互联网上研究后，我想到了两种算法：Dijkstra和TSP。Dijkstra将找到一个节点和每个其他节点之间的最短路径，TSP将找到连接所有点的最短路径。是否有任何 TSP 变体只能找到一组节点之间的最短路径？毕竟，在 TSP 中，所有节点都被标记为"必须通过"。我仍然没有考虑电池限制。

提前感谢！

Answer 1

您可以将

图形简化为 TSP，然后对其调用 TSP 算法：

1. 使用弗洛伊德-沃歇尔算法找到所有顶点对u和v的距离u,v。
2. 创建一个仅包含"所需"顶点的新图形，并将两个此类顶点之间的权重设置为u和v，作为 Floyd-Warsshall 找到的距离。
3. 对修改后的图形运行 TSP 求解器以获取修改后的图形中的路径，并使用原始图形的最短路径切换修改后的图形中的每个边。

---

以上是最佳的，因为假设有一条更短的路径。

D0=u->...D1->...->D2->...->Dk->...->t=D{k+1}

Di->...->D{i+1}至少具有FloydWarshall(Di,D{i+1})的权重（Floyd-Warshall的正确性），因此边(D0,D1),(D1,D2),...,(Dk,D{k+1)存在于修改后的图形中，其权重小于/等于给定路径中的权重。

因此，从 TSP 求解器的正确性来看，通过使用 D0->D1->...->Dk->D{k+1} ，您可以获得至少与候选最佳路径一样好的路径。

Answer 2

您可能还想研究广义旅行推销员问题 （GTSP）：节点被划分为子集，问题是找到在每个子集中恰好访问一个节点的最小长度路由。允许模型从每个子集中选择所需的节点。如果存在必须访问的节点，则可以将它们单独放在一个子集中。