最便宜的路径算法 [英] Cheapest path algorithm

问题描述

我学到了动态编程算法来寻找最便宜的路径从A到B的每个子路径都有一个相关的成本。

I've learnt a dynamic programming algorithm to find the "cheapest" path from A to B. Each sub path has an associated cost.

每个角落都使用
计算 D（I，J）。价值= MIN（（D（I-1，J）。价值+ D（I，J）.X），（D（I，J-1）。价值+ D（I，J）.Y））
其中x和y是路径上的节点的左和下方的节点的成本。

Each corner is calculated using
D(i,j).value = min( (D(i-1,j).value + D(i,j).x), (D(i,j-1).value + D(i,j).y))
Where x and y are the costs of the path on the left of the node and below the node.

我现在无法搞清楚可能的最廉价的路径量在最佳的时间。

I'm now having trouble figuring out the amount of possible cheapest paths in the best possible time.

有什么建议？

http://www.freeimagehosting.net/uploads/f6e0884a2d.png

推荐答案

您所描述的动态规划方法被称为的 DAG最短路径。它仅适用于向无环图（即，曲线图，没有循环）。其渐近的运行时间为O（V + E）（其中V和E是顶点和边，数量分别），这比Dijkstra算法更快。

The dynamic programming approach you describe is called DAG shortest path. It only works on directed acyclic graphs (that is, graphs with no cycles). Its asymptotic runtime is O(V+E) (where V and E are the number of vertices and edges, respectively), which is faster than Dijkstra's algorithm.

我不知道，但你问如何计算路径具有的长度等于最短路径？

I'm not sure, but are you asking how to calculate the number of paths which has length equal to the shortest path?

您可以做到这一点通过维持predecessor信息，当您计算最短路径的长度。当您移动到节点j，存储所有对（I，J），使得从我去j是最短路径的一部分。实现这一点的一种方式是添加两个字段，D（X，Y）.optimalUp和D（X，Y）.optimalRight（数据类型布尔值），这表明，如果你得到最佳的解决方案，如果您打算输入（X，Y）或右，分别。例如，将D（X，Y）.optimalUp为true，如果从（x，y-1）导致最廉价的路往上走。

You can do that by maintaining predecessor information when you calculate the length of the shortest path. When you move to node j, store all pairs (i,j) such that going from i to j is part of a shortest path. One way to implement this is to add two fields, D(x,y).optimalUp and D(x,y).optimalRight (datatype boolean), indicating if you get an optimal solution if you entered (x,y) by going up or right, respectively. For example, set D(x,y).optimalUp to true if going up from (x,y-1) results in the cheapest path.

然后就可以做第二遍数的最低路径的数量，使用动态规划。添加其他领域，比如D（X，Y）.Count之间（整数）持有的方式从A至去（X，Y）的最便宜的方式数。有两种方法来达到（X，Y）：通过（X-1，y）和（X，Y-1）。的（X，Y-1）的只能由通过（X，Y-1）将加至（X，Y），如果它是可以实现的最低路径到（x，y）的计数的计数。同一原则也适用于（X-1，y）的

Then you can do a second pass to count the number of cheapest paths, using dynamic programming. Add another field, say D(x,y).count (integer) which holds the number of ways to go from A to (x,y) in the cheapest way. There are two ways to reach (x,y): Via (x-1,y) and (x,y-1). The count of (x,y-1) should only be added to the count of (x,y) if it is possible to achieve the cheapest path to (x,y) by going via (x,y-1). The same principle holds for (x-1,y).

然后我们得到复发：

D(x,y).count =
    D(x,y).optimalUp   ? D(x,y-1).count : 0
  + D(x,y).optimalDown ? D(x-1,y).count : 0

（？：是在C条件运算符/ C ++ / Java的）

( ?: is the conditional operator in C/C++/Java.)

从图片来看，似乎你的图是一个网格。要注意的是即将要向上或向右不必导致的最短路径。在下面的图中，最短路径从A到B是8，但你不能达到比12，如果你去天经地义了。

Judging from your picture, it seems your graph is a grid. Beware that going only up or right need not result in the shortest path. In the graph below, the shortest path from A to B is 8, but you cannot achieve better than 12 if you go only right and up.

x -1-- x -1-- B
|      |      |
1      9      9
|      |      |
x -1-- x -1-- x
|      |      |
9      9      1
|      |      |
A -1-- x -1-- x

由于这个被标记为功课，我不会提供更多的细节比这个现在。这仍然应该是在正确的方向轻推（如果我正确地理解你的问题）。随意问后续的问题，但。

Since this is marked as homework, I won't be providing more details than this for now. This should nevertheless be a nudge in the right direction (if I have understood your problem correctly). Feel free to ask follow-up questions, though.

这篇关于最便宜的路径算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！