如何为最短路径问题制定LP? [英] How to formulate LP for shortest path problems?

问题描述

我试图了解最短路径问题的LP公式是如何工作的.但是我在理解约束时遇到了麻烦.为什么这种配方有效?

I'm trying to understand how the LP formulation for shortest path problem works. However I'm having trouble understanding constraints. Why does this formulation work?

http://ie.bilkent.edu.tr/~ie400/Lecture8. pdf

我在理解第15页和第17页上的约束如何工作时遇到了麻烦.我有了主要思想，也了解了x应该如何以及为什么应采用某些值，但是我不理解整个系统在数学方面的工作方式.有人可以解释吗?在考试中，我应该能够创建和修改这样的约束，但是我还差得远.

I'm having trouble understanding how the constraints work at pages 15 and 17. I got the main idea and I understand how and why x should take some values but I did not understand how the whole system works in terms of math. Can someone explain? In the exam, I am supposed to be able to create and modify such constraints but I am pretty far from doing that.

推荐答案

在这些幻灯片(第15和17页)上不太清楚的是，以"s.t."开头的行.实际上是在每个顶点i中指定一个约束，即总共有n个单独的约束(如果有n个顶点).通常，可以通过在约束旁边编写∀iϵ V"之类的东西来传达这种信息.

What isn't very clear on those slides (pp. 15 and 17) is that the line beginning with "s.t." is actually specifying one constraint per vertex i, i.e., n separate constraints in total (if there are n vertices). Normally this would be communicated by writing something like "∀i ϵ V" alongside the constraint.

无论如何，该行表示对于每个顶点i，从任何其他顶点进入它的总流量必须等于离开它的总流量-除非顶点是源，在这种情况下，总和离开它的流量必须大于1或汇，在这种情况下，进入它的总流量必须大于1.最初如何提出这种约束系统可能并不明显，但是通过查看一些示例，您应该能够看到任何最短路径(或者实际上是从s到t的任何路径)都满足它们:路径中的每个内部顶点将具有1个进入边和1个离开边，而s和t分别只有1个传出边缘或1个传入边缘.完全不参与路径的顶点的流入流为0，流出流为0，因此它们也可以工作.

In any case, this line says that for each vertex i, the total amount of flow entering it from any other vertices must equal the total amount of flow leaving it -- unless the vertex is the source, in which case the total amount of flow leaving it must be greater by 1, or the sink, in which case the total amount of flow entering it must be greater by 1. It may not be obvious how to come up with this system of constraints in the first place, but by looking at some examples you should be able to see that any shortest path (or in fact, any path from s to t at all) satisfies all of them: every internal vertex in the path will have 1 incoming edge and 1 outgoing edge, while s and t will have just 1 outgoing, or 1 incoming, edge, respectively. Vertices that don't participate in the path at all have 0 incoming and 0 outgoing flow, so they work too.

还有一点是，在流量问题中，标记边缘的数字通常表示容量约束-两个端点之间流量的最大限制-而不是像此处那样花费

One more point is that with flow problems, very often the numbers labelling the edges represent capacity constraints -- maximum limits on the amount of flow between the two endpoints -- not costs as they do here.

这篇关于如何为最短路径问题制定LP?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！