具有资源约束的最短路径
我有一个有向无环图，需要找到具有资源限制的最短路径。我的限制是所选路径必须消耗最少数量的一组资源。
目前我正在使用 Yen 的 K 最短路径算法 来计算 K 最短路径，然后只接受那些满足我的约束的路径。这里的问题在于猜测K，如果选择错误，有可能找不到可行的路径。
我发现了很多关于这个主题的文献， 这 提供了一个很好的概述。然而，我正在努力理解它并找到一个能够实现的简洁算法（我正在使用Python，但是任何清晰的算法思想都会很棒）。
我知道这个问题是 NP 完全问题，因此我对任何好的近似算法和精确方法感兴趣。
大家有什么好的建议吗？
I have a directed acyclic graph and need to find the shortest paths with resource constraints. My constraint is that the paths selected must have a minimum number of a set resource consumed.
Currently I am using Yen's K Shortest Path algorithm to calculate K shortest paths and then only accept those that satisfy my constraint. The issue here is in guessing K, as if it is incorrectly chosen, it is possible that no feasible paths will be found.
I have found quite a lot of literature on this topic, this provides a good overview I think. However, I am struggling to make sense of it and find a concise algorithm that is able to be implemented (I am using Python, however any clear algorithmic ideas would be great).
I understand that this problem is NP-Complete, and as such I am interested in any good approximation algorithms as well as exact approaches.
Anyone have any good recommendations?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您可以做的是将图形
(V,E)转换为(V',E')，其中P(v)是原始节点vR的价格是最大资源使用量。V' = {(v,k) | v 在 V 中，k 在 [0..R]}E'((v,k),(w,l)) = E(v,w) 和 k+P(w)= l然后，您从
(v0,P(v0))进行 dijkstra 搜索。如果可以找到到v1的路径，则在给定限制的情况下，到它的最短距离将是(v1,k)顶点中最短的距离。显然您没有创建实际的展开图。修改后的 dijkstra 中会发生的事情是，除了到目前为止的距离之外，您还将保留到目前为止的资源使用。您只会遵循不超过限制的路径。而不是保留
dist[v]，而是保留dist[v,k]表示到目前为止 v 的最短路径，完全使用k资源。如果您的资源限制非常大，那么它可能会变得很大。因此NP完备性。但是，如果您的资源限制很小，或者您不介意舍入到最接近的 10、100 或 1000，则它将在快速多项式时间内运行。
特别是如果您在达到可用的
(v1,k)后实施停止优化。What you can do is to transform your graph
(V,E)into(V',E')whereP(v)is the price of the original nodevRis the maximum resource use.V' = {(v,k) | v in V and k in [0..R]}E'((v,k),(w,l)) = E(v,w) and k+P(w)=lThen you do a dijkstra search from
(v0,P(v0)). If it was possible to find a path tov1, given the limit, the shortest distance to it, will be the shortest among the(v1,k)vertices.You obviously don't create the actual expanded graph. What would be going on in your modified dijkstra is that in addition to the distance so far, you would keep the resource use so far as well. You would only follow a path if it didn't exceed the limit. And instead of keeping a
dist[v]you would keepdist[v,k]representing the shortest path to v so far, using exactlykresources.If your resource bound is very large, this can potentially grow as big. Hence the NP completeness. However if your resource bound is small, or you don't mind rounding of to nearest 10, 100 or 1000, it will run in fast polynomial time.
Especially if you implement the optimization of stopping once you've reached a useable
(v1,k).作为 k-最短路径来解决这个问题会受到以下事实的困扰：您不知道如何选择
k。按照已接受的答案的建议来解决它，会受到以下事实的影响：您需要为从源到节点 v 的所有不同路径中潜在的所有 k 值维护
dist[v,k]（这会导致在非常低效的算法中）。有伪多项式时间算法可以解决这个问题，如您所料，它被称为“资源约束的最短路径问题”(SPPRC)。该问题经常出现在车辆路径问题（VRP）和乘员配对问题（两者都是运输问题，主要在运筹学中处理）中。有关起点，请参阅以下（评论）论文：S. Irnich & G. Desaulniers, “Shortest Path Problems with Resource Constraints”, In G. Desaulniers, J. Desrosiers, M. Solomon (eds): Column Generation, Springer, 2005。
您可以通过 google 搜索论文标题，您应该是可以免费下载。我应该提到，你的问题有一个不寻常的约束结构：即，你需要“花费”至少一定数量的资源，而不是确保你不会花费“太多”的资源......
Solving this problem as a k-shortest path suffers from the fact that you don't know how to choose
k.Solving it as the accepted answer proposes, suffers from the fact that you need to maintain
dist[v,k]for potentially all values of k from all distinct paths arriving from the source to node v (which results in very inefficient algorithm).There are pseudo-polynomial time algorithms for solving this problem, which is called, as you'd expect, "Shortest Path Problem with Resource Constraints" (SPPRC). The problem appears often in Vehicle Routing Problems (VRP) and Crew Pairing Problems (both are transportation problems, that are mostly dealt with in Operations Research). For a starting point see the following (review) paper: S. Irnich & G. Desaulniers, "Shortest Path Problems with Resource Constraints", In G. Desaulniers, J. Desrosiers, M. Solomon (eds): 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...