博客

动态规划，Dijkstra算法，A*算法的框架是相同的，不同点仅在于“推进点的选取”和“算法终止条件”。

一，动态规划：（参见

http://blog.csdn.net/iwantnon/archive/2009/07/07/4329269.aspx

）

推进点选取：

（1），在粗犷的动态规划算法中：

根本不进行选择，而是对所有已存在节点全部推进一遍。这可能造成如下两点浪费：

[1]，重复推进：对某点v已经作了推进，而下一次在其valu值没有发生更改的情况下又一次对它进行推进，显然这第二次推进得不到任何新东西，所以是白费的。

[2]，推进失效：对某点v作了推进以后，又对点u作推进，而u恰好将点v的valu值刷新，于是当初对点v所作的推进失效（应该用点v的新valu值重新推进）。

（2），在带open标记的动态规划算法中：

对点v进行推进后将其关闭（令v.open=false），由于在选择推进点时只从处于开启状态的点中选，这样就避免了重复推进v点，除非v点valu值被刷新而再次变为开启(v.open=true)状态。即解决了”重复推进“问题，但并没有解决”推进失效“问题。

终止条件：

无论是在粗犷动态规划算法还是在带open标记的动态规划算法中，为了保证得到终点的最优值都必须“充分推进”–