Agradeceríamos tu apoyo para difundir nuestras secciones con relación a las ciencias informáticas.
Solución:
Todas las implementaciones de los algoritmos de Dijkstra que he visto no tienen una función recursiva
La recursividad nos da una pila. Pero no necesitamos una pila aquí. Necesitamos una cola de prioridad. La forma eficiente de implementar el algoritmo de Dijkstra utiliza un montón (stl priority_queue en c++).
pero también he leído que por definición la programación dinámica es un algoritmo con función recursiva y “memoria” de cosas ya calculadas.
La programación dinámica no necesita escribirse de forma recursiva, aunque la mayoría de la gente prefiere escribirla de forma recursiva.
Por ejemplo:
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);
es una implementación recursiva de DP
y
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];
es una forma iterativa de escribirlo para ahorrar memoria de pila.
Recuerde que cualquier algoritmo
1) que no vuelve a calcular el resultado que ya se encuentra y
2) usa el resultado existente para encontrar el resultado requerido
se puede llamar como un DP.
Entonces, ¿el algoritmo de Dijkstra con un bucle se califica como programación dinámica?
Dijkstra es DP!
O para calificar como algoritmo dinámico, tengo que cambiar un bucle en una función recursiva.
No
Hay un artículo al respecto titulado "Revisión del algoritmo de Dijkstra: la conexión de programación dinámica" de Moshe Sniedovich. http://matwbn.icm.edu.pl/ksiazki/cc/cc35/cc3536.pdf
El artículo afirma que el algoritmo de Dijkstra está fuertemente inspirado en el Principio de Optimalidad de Bellman y que tanto conceptual como técnicamente constituye un procedimiento de aproximación sucesiva de programación dinámica por excelencia.
El algoritmo de Dijkstra es como un algoritmo de llenado de agua. En cada paso, elige mínimos locales, por eso muchos lo consideran un algoritmo codicioso. Si prueba este mismo algoritmo eligiendo cualquier ruta arbitraria que no sea el mínimo local, entonces sabrá que todavía está funcionando. Elegir un mínimo local es solo para llenar el agua de manera óptima, como mencioné anteriormente, es como un algoritmo de llenado de agua. Entonces, el concepto principal detrás del Algoritmo de Dijkstra es almacenar el resultado anterior para predecir el próximo resultado y eso es el Enfoque Dinámico.
Para obtener más detalles, consulte el siguiente enlace
¿Por qué funciona el algoritmo de Dijkstra?
Acuérdate de que tienes autorización de parafrasear tu experiencia si diste con la solución.