我有一个有向无环图，需要找到资源约束的最短路径。我的约束是所选路径必须具有消耗的最小数量的设置资源。资源约束的最短路径
目前我使用Yen's K Shortest Path algorithm计算K最短路径，然后只接受那些满足我的约束。这里的问题在于猜测K，就好像它被错误地选择一样，可能没有找到可行的路径。
我发现很多这方面的文献，this提供了一个很好的概述，我认为。然而，我很难理解它，并找到一个能够实现的简洁算法（我正在使用Python，但是任何明确的算法思想都很棒）。
我知道这个问题是NP-Complete，因此我对任何好的近似算法以及确切的方法感兴趣。
任何人都有什么好的建议？
你可以做的是你的图形(V,E)转变为(V',E')，其中
P(v)是原来的节点vR的价格是最大的资源利用。V' = {(v,k) | v in V and k in [0..R]}E'((v,k),(w,l)) = E(v,w) and k+P(w)=l那么你就从(v0,P(v0))一个Dijkstra算法搜索。如果有可能找到到v1的路径，给定限制，最短距离将是(v1,k)顶点中最短的距离。
您显然不会创建实际的展开图。修改后的dijkstra会发生什么，除了迄今为止的距离之外，您还可以保持资源的使用。如果没有超过限制，你只能沿着一条路径行进。而不是保留dist[v]，你会保持dist[v,k]代表到目前为止的最短路径，正好使用k资源。
如果您的资源绑定非常大，这可能会增长很大。因此，NP的完整性。但是，如果您的资源限制很小，或者您不介意舍入到最接近的10,100或1000，它将以快速多项式时间运行。 尤其是，如果您在达到可用的(v1,k)后执行停止的优化。
解决此问题为k最短路径患有您不知道如何选择k的事实。
解决它作为接受的答案建议，患有这样一个事实，即您需要保留dist[v,k]，以便从源到节点v的所有不同路径中的k的潜在所有值（这导致非常低效的算法）。
有解决这个问题，这是所谓的，因为你所期望的，“与资源约束最短路径问题”（SPPRC）伪多项式时间算法。这个问题通常出现在车辆路径问题（VRP）和船员配对问题（两者都是交通问题，这些问题大多在运筹学中处理）。有关资源约束的最短路径问题，G. Desaulniers，J. Desrosiers，M. Solomon（编）：Column Generation，Springer， 2005.
你可以谷歌的文章的标题，你应该能够免费下载它。我应该提到，尽管你的问题有一个不寻常的约束结构：即，你需要“花费”至少一定量的资源，而不是确保你不花费太多的资源......
你能解释一下资源约束是什么意思吗？如果这些限制具有特定的格式，似乎这个问题不会是NP难的。 – templatetypedef 2011-12-30 20:55:09
我不仅试图找到最短的路径，而是一条满足约束条件的路径（现在只有一条是我正在工作，但可能在将来会更多）。这是最小限制。 图中的每个节点N对总资源计数N_x贡献x。 要使路径有效，对于路径中的所有N，sum（N_x）> = Min。 – steven 2011-12-31 11:22:33
您的概览链接对我无效，但您是否尝试过Eppstein的k-最短路径算法？它不需要预先限制k，而是逐个生成最短路径，并且可以简单地继续生成它们，直到找到满足约束条件的路径。 – han 2011-12-31 14:59:45