我见过的 Dijkstra 算法的所有实现都没有递归函数,但我也读到,根据定义,动态规划是一种具有递归函数和已计算事物“记忆”的算法。
那么带有循环的 Dijkstra 算法是否符合动态规划的资格?
或者为了符合动态算法的资格,我必须将循环更改为递归函数。
我见过的所有 Dijkstra 算法的实现都没有 递归函数
递归给了我们一个堆栈。但我们这里不需要堆栈。我们需要一个优先级队列。实现 Dijkstra 算法的有效方法是使用 heap(c++ 中的 stlpriority_queue)。
但我也读到,根据定义,动态规划是一种 具有递归函数和事物“记忆”的算法 计算出来了。
动态规划不需要以递归方式编写,尽管大多数人更喜欢以递归方式编写。
例如:
int dp[MAX]={-1,-1,...};
find fibonacci(int n){
if(n <= 1) return n;
if(dp[n]!=-1) return dp[n];
return dp[n]=fibonacci(n-1)+fibonacci(n-2);
}
是DP的递归实现
和
int dp[MAX]={0,1,-1,-1,-1,..};
int lastFound = 1;
int fibonacci(int n){
for(int i=lastFound+1;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
是一种迭代的编写方式,以节省堆栈内存。
记住任何算法
不会重新计算已经找到的结果并且
使用现有结果找到所需结果
可以称为DP。
带有循环的 Dijkstra 算法也被称为动态算法吗? 编程?
Dijkstra 是 DP!
或者为了有资格成为动态算法,我必须更改循环 变成递归函数。
没有
有一篇关于它的论文,题为“Dijkstra 算法重温:动态规划连接”,作者 Moshe Sniedovich。 http://matwbn.icm.edu.pl/ksiazki/cc/cc35/cc3536.pdf
论文声称 Dijkstra 算法受到 Bellman 算法的强烈启发 最优性原理以及它在概念上和技术上的 构成动态规划逐次逼近程序 卓越。
Dijkstra 算法就像一个注水算法。它在每一步都会选择局部最小值,这就是许多人将其视为贪婪算法的原因。如果您尝试选择任意路径而不是局部最小值来尝试相同的算法,那么您会发现它仍然有效。选择局部最小值只是为了最佳地注水,正如我之前提到的,这就像注水算法。因此,Dijkstra 算法背后的主要概念是存储之前的结果来预测即将到来的结果,这就是动态方法。
更多详情请参考以下链接
您解决了两个问题:
动态算法意味着将过程分解为更简单的任务。几种动态算法包含递归的思想但也不限于..
考虑 Dijkstra 算法,经典解决方案是由 for 循环给出的,而不是动态算法解决方案。
但是,从动态规划的角度来看,Dijkstra算法是一种逐次逼近方案,通过Reaching方法求解最短路径问题的动态规划函数方程。
其实Dijkstra对算法背后逻辑的解释,即:
Problem 2. Find the path of minimum total length between two given nodes P and Q.
注:摘自维基百科