Asynchronous dynamic programming

2019-12-20 本文已影响0人学习编程王同学

本文代码点击这里下载。

动态规划方法

如果节点 $x$ 位于 $s$ 到 $t$ 的最短路径上，那么 $x$ 到 $t$ 的路径也必须是 $x$ 和 $t$ 之间的最短路径。这种“分而治之”（devide-and-conquer）的思想，被称为动态规划（dynamic programming）。

异步动态规划方法（ASYNCHDP）

记节点 $i$ 到目标节点 $t$ 的最短路径为 $h^*(i)$ 。从 $i$ 到 $t$ 的经过 $j$ （是 $i$ 的邻居）的最短路径可通过 $f^* (i,j)=w(i,j)+h^*(j)$ 给出，并且 $h^*(i)=min_j f^*(i,j)$ . 基于这种思想，给出ASYNCHDP方法的伪代码如下。

ASYNCDP算法伪代码

一个ASYNCDP算法的例子：

ASYNCDP算法寻找最短路径的例子

Asynchronous dynamic programming

动态规划方法

异步动态规划方法（ASYNCHDP）

猜你喜欢

热点阅读