是Dijkstra的算法,动态编程

Question

我所见过的Dijkstra算法的所有实现都没有递归函数,但我还读到,根据定义,动态编程是一种具有递归函数和已计算事物的"记忆"的算法.

那么Dijkstra的算法是否具有作为动态编程的循环？
或者为了有资格作为动态算法,我必须将循环更改为递归函数.

Answer 1

我见过的Dijkstra算法的所有实现都没有递归函数

递归给了我们一个堆栈.但是我们这里不需要堆栈.我们需要一个优先级队列.实现Dijkstra算法的有效方法是使用堆(c ++中的stl priority_queue).

但我还读到,根据定义,动态编程是一种具有递归函数和已计算事物的"记忆"的算法.

动态编程不需要以递归方式编写,尽管大多数人更喜欢以递归方式编写它.

例如:

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.

那么Dijkstra的算法是否具有作为动态编程的循环？

Dijkstra是DP!

或者为了有资格作为动态算法,我必须将循环更改为递归函数.

没有

Answer 2

您提出两个问题：

动态算法意味着将过程分解为更简单的任务。几种动态算法包括递归的思想，但也不限于此。

考虑 Dijkstra 算法，经典解决方案由 for 循环给出，而不是动态算法解决方案。

然而，从动态规划的角度来看，Dijkstra算法是一种逐次逼近方案，通过Reaching法求解最短路径问题的动态规划函数方程。

事实上，Dijkstra 对算法背后逻辑的解释是：

Problem 2. Find the path of minimum total length between two given nodes P and Q.

注：摘自维基百科