我见过的所有 Dijkstra 算法的实现都没有递归函数,但我也读到,根据定义,动态规划是一种具有递归函数和“内存”已计算事物的算法。
那么带循环的 Dijkstra 算法是否符合动态规划的条件?
或者为了符合动态算法的条件,我必须将循环更改为递归函数。
最佳答案
All implementation of Dijkstra's algorithms I have seen do not have a recursive function
递归给了我们一个堆栈。但是我们这里不需要堆栈。我们需要一个优先队列。实现 Dijkstra 算法的有效方法是使用 heap (c++ 中的 STL priority_queue)。
but I have also read that by definition dynamic programming is an algorithm with a recursive function and "memory" of things already calculated.
动态编程不需要以递归方式编写,尽管大多数人更喜欢以递归方式编写。
例如:
int dp[MAX]={-1,-1,...};
find fibonacci(int nthTerm){
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 nthTerm){
for(int i=lastFound+1;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
是一种迭代的方式来编写它以节省堆栈内存。
记住任何算法
1) 不重新计算已经找到的结果并且
2)利用已有的结果寻找需要的结果
可以称为DP。
So is Dijkstra's algorithm with a loop qualified as dynamic programming?
Dijkstra 是 DP!
Or in order to qualify as dynamic algorithm I have to change a loop into a recursive function.
没有
关于algorithm - 是Dijkstra算法,动态规划,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24140623/