如果我的资金有限,我如何在DAG中找到最便宜的方式？

Question

所以,如果我有一个定向非循环图,其中每个边的成本为0或大于0,如果它大于0它将具有负重量(所以你可以用它5美元它将缩短你的方式例如-20).

我知道我们可以在DAG中轻松找到最短/最便宜的方式,但如果我们的资金有限呢？

想象一下下一个情况:

我们有8个钱.算法会找到最短路径-10 + -3 = -13,但它会花费12但我们只有8个钱,所以它不是一个选项.理想的路径是-10 + 0,只需7美元.有没有一种算法可以用来解决这个问题？

Answer 1

这个问题是NP-Hard,从背包问题减少了.

简短直观的"证明":这个想法是,为每个项目创建一个顶点 - 你可以通过选择带有成本或"自由"顶点的顶点来"接受"或"不接受".

草图:

在上面你可以看到,从背包问题中,创建一个图表,对于每个项目,你可以选择接受它 - 并支付成本并获得"价值",或忽略它.

更正式的:

鉴于背包与一个实例weights=w1,w2,w3,...cn,并cost=c1,c2,..,cn与一些最大的权重W,创建图形G=(V,E)与

V= { V_i,U_i,W_i | i=0,...n }
E= { (W_i,V_i+1,U_i+1 | i=0,...,n-1} U {(V_i,W_i+1), (U_i,W_i+1) | i=0,...,n-1 }

value(W_i,V_i+1) = c_i+1
money(W_i,V_i+1) = w_i+1
value(W_i,U_i+1) = 0
money(W_i,U_i+1) = 0
money(V_i,W_i+1) = cost(V_i,W_i+1) = money(U_i,W_i+1) = cost(U_i,W_i+1) = 0

使用最多W钱的这个问题的解决方案也将是具有最大容量W的背包的解决方案.

一个可能的伪多项式解决方案可能是(使用动态编程技术):

D(start,0) = 0
D(v,x) = infinity     x < 0
D(v,x) = min { D(u,x-money(u,v)) + value(u,v) | for each edge (u,v) } U {infinity}

在上面D(v,x)是从起始节点到v完全支付x金钱所需的最小距离.

请注意,它可以完成,因为它是一个DAG,因此您可以根据图形的拓扑排序从头到尾计算值.

完成后,你需要搜索的所有值x从0到MAXIMAL_AMOUNT_OF_MONEY_ALLOWED找到的最小值D(target,x),这就是答案.
通过回溯您的步骤来完成实际成本,就像在其他动态编程解决方案中所做的那样.

上面的运行时间是 O(|V|*MAX_MONEY + |E|)