多个源-目标路径的最小总和
Minimum sum of multiple source-destination path
给定一个无向且未加权的图，我想在每个顶点最多使用一次的约束下，找出 k 对源-目标路径之和的最小值。
例如，下图具有 2 对源-目标 (A, E) 和 (B, F)，最小步长总和为 7。也就是说，(A > G > H > I > E) = 4 步，(B > C > D > F) = 3 步。
http://i.imgur.com/W4uNiac.png
很明显，贪婪的方法依次找到所有这k条路径将导致次优解。例如，存在 8 个步骤的解决方案，其中 (A > C > D > E) = 3 个步骤，(B > J > K > L > M > F) = 5 个步骤。
我已经考虑将这个问题建模为最小成本最大流量问题。然而，这样的多个源-目的地对并不总能被区分。例如，如果 k = 2 并且两对是 (A, B) 和 (C, D)，则应用 MCMF 的解决方案可能导致 (A > ... > D) 和 (B > ... > C)在某些情况下，这显然不是我想要的解决方案。
有没有关于这个问题的想法？
提前致谢！ :)
这看起来像是修改后的多智能体路径规划问题。通常情况下，代理只限于不碰撞或交叉路径，但在您的版本中，它们不能在任何地方共享顶点。修改CBS算法来解决这个问题并不难。
我会打电话给你的 k 路径 agents 来帮助描述解决方案。
基本思想是使用二叉搜索树来寻找解决方案。首先独立地为每个 k 代理找到最短路径。然后，您检查已解决路径中的代理之间是否存在任何冲突。当您找到由两条路径共享的节点时，您将在树中分支。在树的右侧，禁止第一个代理使用该节点。在树的左侧，禁止第二个代理使用该节点。然后，被赋予新约束的代理需要在不使用给定节点的情况下重新搜索。
树中的节点根据所有代理的总路径成本以最佳优先顺序展开。当您找到解决方案时，它保证是最优的。
您还可以使用其他算法，但这个算法非常简单，因为它可以使计划分离。效率取决于您要解决的问题的确切性质。
如果我不得不猜测，问题是 NP-Hard 或 NP-Complete - 易于验证解决方案，但给定的算法以指数时间运行。
给定一个无向且未加权的图，我想在每个顶点最多使用一次的约束下，找出 k 对源-目标路径之和的最小值。
例如，下图具有 2 对源-目标 (A, E) 和 (B, F)，最小步长总和为 7。也就是说，(A > G > H > I > E) = 4 步，(B > C > D > F) = 3 步。
http://i.imgur.com/W4uNiac.png
很明显，贪婪的方法依次找到所有这k条路径将导致次优解。例如，存在 8 个步骤的解决方案，其中 (A > C > D > E) = 3 个步骤，(B > J > K > L > M > F) = 5 个步骤。
我已经考虑将这个问题建模为最小成本最大流量问题。然而，这样的多个源-目的地对并不总能被区分。例如，如果 k = 2 并且两对是 (A, B) 和 (C, D)，则应用 MCMF 的解决方案可能导致 (A > ... > D) 和 (B > ... > C)在某些情况下，这显然不是我想要的解决方案。
有没有关于这个问题的想法？
提前致谢！ :)
这看起来像是修改后的多智能体路径规划问题。通常情况下，代理只限于不碰撞或交叉路径，但在您的版本中，它们不能在任何地方共享顶点。修改CBS算法来解决这个问题并不难。
我会打电话给你的 k 路径 agents 来帮助描述解决方案。
基本思想是使用二叉搜索树来寻找解决方案。首先独立地为每个 k 代理找到最短路径。然后，您检查已解决路径中的代理之间是否存在任何冲突。当您找到由两条路径共享的节点时，您将在树中分支。在树的右侧，禁止第一个代理使用该节点。在树的左侧，禁止第二个代理使用该节点。然后，被赋予新约束的代理需要在不使用给定节点的情况下重新搜索。
树中的节点根据所有代理的总路径成本以最佳优先顺序展开。当您找到解决方案时，它保证是最优的。
您还可以使用其他算法，但这个算法非常简单，因为它可以使计划分离。效率取决于您要解决的问题的确切性质。
如果我不得不猜测，问题是 NP-Hard 或 NP-Complete - 易于验证解决方案，但给定的算法以指数时间运行。