首页 文章

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

提问于
浏览 次
2

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

在互联网上研究后，我有两个算法： Dijkstra's 和 TSP . Dijkstra's 将找到节点与每个其他节点之间的最短路径， TSP 将找到连接所有点的最短路径 . 是否有 TSP 的任何变体只找到一组节点之间的最短路径？毕竟，在 TSP 中，所有节点都标记为 "must-pass" . 我还没有考虑电池限制 .

提前致谢！

algorithm dijkstra shortest-path traveling-salesman

2 回答

  • 1

    您可能还想查看广义旅行商问题（GTSP）：节点被划分为子集，问题是找到每个子集中只访问一个节点的最小长度路由 . 允许模型从每个子集中选择它想要的任何节点 . 如果有必须访问的节点，您可以将它们全部放在一个子集中 .

    回复于
  • 3

    您可以将图形缩减为TSP，然后在其上调用TSP算法：

    • 使用Floyd-Warshall算法查找所有顶点对 u 和 v 的距离 u,v .

    • 创建一个仅包含"desired"顶点的新图形，并将两个此类顶点 u 和 v 之间的权重设置为Floyd-Warshall找到的距离 .

    • 在修改后的图形上运行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-Solver的正确性，通过使用 D0->D1->...->Dk->D{k+1} ，您将获得至少与候选最佳路径一样好的路径 .

    回复于

相关问题