3

我有一个有向无环图，需要找到具有资源约束的最短路径。我的限制是所选路径必须具有最少数量的一组资源消耗。

目前我正在使用Yen 的 K 最短路径算法来计算 K 最短路径，然后只接受那些满足我的约束的路径。这里的问题在于猜测K，如果它被错误地选择了，可能会找不到可行的路径。

我发现了很多关于这个主题的文献，我认为这提供了一个很好的概述。但是，我正在努力理解它并找到一个能够实现的简洁算法（我正在使用 Python，但是任何清晰的算法想法都会很棒）。

我知道这个问题是 NP-Complete 的，因此我对任何好的近似算法以及精确方法都很感兴趣。

有人有什么好的建议吗？

4

2 回答 2

2

您可以做的是将您的图表转换(V,E)为(V',E')

  • P(v)是原始节点的价格v
  • R是最大的资源使用。
  • V' = {(v,k) | v in V and k in [0..R]}
  • E'((v,k),(w,l)) = E(v,w) and k+P(w)=l

然后你从 .dijkstra 进行搜索(v0,P(v0))。如果有可能找到到 的路径v1，给定限制，到它的最短距离将是(v1,k)顶点中最短的。

您显然没有创建实际的扩展图。在您修改后的 dijkstra 中会发生什么，除了到目前为止的距离之外，您还将保持资源使用到目前为止。只有在不超过限制的情况下，您才会遵循路径。而不是保留 adist[v]你会继续dist[v,k]代表到 v 的最短路径，使用确切的k资源。

如果您的资源绑定非常大，这可能会增长得很大。因此 NP 完备性。但是，如果您的资源限制很小，或者您不介意四舍五入到最接近的 10、100 或 1000，它将在快速多项式时间内运行。特别是如果您在达到可用的(v1,k).

于 2012-01-19T16:10:43.080 回答
1

将这个问题解决为 k 最短路径会遇到这样一个事实，即您不知道如何选择k。

按照公认的答案建议解决它，受到以下事实的困扰：您需要维护dist[v,k]来自从源到达节点 v 的所有不同路径的潜在所有 k 值（这导致算法效率非常低）。

有一些伪多项式时间算法可以解决这个问题，正如您所料，它被称为“具有资源约束的最短路径问题”（SPPRC）。该问题经常出现在车辆路线问题 (VRP) 和机组配对问题（两者都是运输问题，主要在运筹学中处理）中。有关起点，请参见以下（评论）论文：S. Irnich & G. Desaulniers，“Shortest Path Problems with Resource Constraints”，G. Desaulniers、J. Desrosiers、M. Solomon（编辑）：Column Generation，Springer， 2005 年。

You can google for the title of the paper, and you should be able to download it for free. I should mention though that your problem has an unusual constraint structure: namely, you need to "spend" at least a certain amount of a resource instead of making sure you don't spend "too much" of a resource...

于 2017-01-13T14:29:20.160 回答