动态规划算法

动态规划时运筹学的一个分支，是求解多阶段决策过程最优问题的数学方法。
各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展。当各个阶段的决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动路线，这样的一个前后关联具有链状结构的多阶段过程就称为多阶段决策问题。

算法思想：
最优化原理，把多阶段决策问题转化为一系列单阶段最优化问题。
对最佳路径（最佳决策过程）所经过的各个阶段，其中每个阶段始点到全过程终点的路径，必定是该阶段点到全过程终点的一切可能路径中的最佳路径（最优决策）。
简而言之，一个最优策略的子策略必然也是最优的。

逆向寻优，正向求解。
DP算法本质由三层循环构成。
第一层遍历每一个阶段。
第二层遍历第i个阶段的每一个状态。
第三层循环遍历第i+1个阶段的每一个状态。

A*算法

A*算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。
广泛应用于室内机器人路径搜索、游戏动画路径搜索。

算法思想：
A*算法结合了贪心算法（深度优先）和狄克斯特拉算法（广度优先），是一种启发式搜索算法。
路径优劣评价公式为：f(n)=g(n)+h(n)
f(n)是从初始状态由状态n到目标状态的代价估计，
g（n）是在状态空间中从初始状态到状态n的实际代价，
h（n）是从状态n到目标状态的最佳路径的估计代价。
使用了两个状态表，分别称为openList表和closeList表。
openList表由待考察的节点组成，closeList表由已考察过的节点组成。
算法步骤：
将地图栅格化
确定栅格属性（可走和不可走）
定义两个列表集合，（类似于狄克斯特拉算法的U和S集合）
确定起始点和目标点
路径优劣判断标准，单步移动代价，把横向和纵向移动一个节点的代价定义为10.斜向移动代价参考等腰三角形计算斜边的方式距离为14.
(其中考察其它点时，如果某个相邻节点已经在open list中，则检查这条路径是否更优，也就是说经由当前节点(我们选中的节点)到达那个节点是否具有更下的g值。如果没有不做任何操作)