我已经学习了一种动态编程算法,它可以找到从A到B的“最便宜”路径。每条子路径都有一个相关的成本。
每个角的计算方法是
D(i,j).value = min( (D(i-1,j).value + D(i,j).x), (D(i,j-1).value + D(i,j).y))
其中x和y是节点左侧和节点下方的路径的成本。
我现在很难在最好的时间内计算出可能最便宜的路径数量。
有什么建议吗?
发布于 2010-02-07 00:52:09
您所描述的动态编程方法称为DAG shortest path。它只适用于有向无环图(即没有圈的图)。它的渐近运行时间是O(V+E) (其中V和E分别是顶点和边数),比Dijkstra算法更快。
我不确定,你是在问如何计算长度等于最短路径的路径数吗?
您可以通过在计算最短路径长度时维护前置任务信息来实现这一点。当您移动到节点j时,存储所有对(i,j),使得从i到j是最短路径的一部分。实现这一点的一种方法是添加两个字段,D(x,y).optimalUp和D(x,y).optimalRight (数据类型boolean),表示如果分别向上或向右输入(x,y),是否获得最优解。例如,如果从(x,y-1)向上的结果是最便宜的路径,则将D(x,y).optimalUp设置为true。
然后,您可以使用动态编程进行第二次遍历,以计算最便宜路径的数量。添加另一个字段,比方说D(x,y).count (整数),它保存以最便宜的方式从A到(x,y)的路数。有两种方法可以达到(x,y):Via (x-1,y)和(x,y-1)。如果可以通过经过(x,y-1)获得到(x,y)的最便宜路径,则应该仅将(x,y-1)的计数加到(x,y)的计数上。同样的原理也适用于(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中的条件运算符。)
从你的图片来看,你的图似乎是一个网格。注意,只往上走或往右走并不一定会得到最短的路径。在下面的图表中,从A到B的最短路径是8,但是如果你只往右往上走,你就不能达到12以上。
x -1-- x -1-- B
| | |
1 9 9
| | |
x -1-- x -1-- x
| | |
9 9 1
| | |
A -1-- x -1-- x因为这被标记为家庭作业,所以我现在不会提供比这更多的细节。然而,这应该是在正确的方向上的一个推动(如果我正确地理解了您的问题)。尽管如此,请随时提出后续问题。
发布于 2010-02-05 22:57:03
你在找Dijkstra's algorithm。它是一种图搜索算法,用于解决具有非负边路径成本的图的单源最短路径问题,生成最短路径树。
发布于 2010-02-07 05:59:15
看起来您正在处理一个图,其中的节点是2D网格上的点,每个节点都有一个指向其上方节点的有向边,以及另一个指向其右侧节点的有向边。
我认为仅仅应用Dijkstra的算法在这里是行不通的。它会找到一条成本最低的路径,但实际上没有办法修改它来找到所有最短路径。
由于这是一个特殊的图(即有向图和无环图),如果您知道最便宜路径的成本是多少,则可以使用简单的递归来计算最便宜路径的数量。请注意,
number_paths(i,j)=number_of_paths(i-1,j)+number_of_paths(i,j-1)即,来自任何节点的路径数是来自上方和其右侧的节点的路径数之和。(这省略了当前节点是目标节点以及目标节点无法从当前节点到达的基本情况。)
唯一需要做的就是修改它,只计算那些最便宜的路径。现在,我们已经知道最便宜的路径有一些成本X。我们可以用它来增加我们的重复性,以便它只计算最便宜的路径。在开始节点,我们知道剩余路径的成本是X。从任何相邻节点到开始节点(即从其正上方和右侧的节点),因此成本是X-e,其中e是这些节点之间的边的成本。此规则适用于任何已知到达当前节点的成本的节点。因此,当我们到达目的地节点时,我们知道我们已经遍历了最便宜的路径,并且该节点的值是0(即,我们已经减去了形成最便宜路径的边的所有成本)。
因此,我们可以增加递归,这样我们就可以保留3个值,而不是2个值,即路径的坐标和剩余成本(本质上转化为3D图的相同问题,其中第3维是成本)。起始节点的格式为(x_start,y_start,cost),目的节点的格式为(x_end,y_end,0)。我们的递归过程如下所示:
paths(x,y,cost_left)=
0 if x_end,y_end is unreachable from x,y or cost_left<0
1 if x==X-end and y==y_end and cost_left==0
paths(x-1,y,cost_left-edge(x,y,x-1,y))+paths(x,y-1,cost_left-edge(x,y,x,u-1)) otherwise算法的复杂度应该是O(n_m_C),其中n和m是网格的维度,C是最便宜路径的成本。
https://stackoverflow.com/questions/2207987
复制相似问题