A*算法简介

这把年纪，依然不清楚A*算法，有点可耻了
看了结构之法的博客，google相关内容，总结A*算法如下

问题可以简单描述为 找到从指定起点到指定终点的最短路径
一般的搜索如BFS、DFS、Dijkstra算法往往是一种盲目的四周方向的搜索，搜索空间大，效率低
而A*算法引入估价函数的概念

公式表示为： f(n)=g(n)+h(n),
其中f(n) 是从初始点经由节点n到目标点的估价函数，
    g(n) 是在状态空间中从初始节点到n节点的实际代价，
    h(n)是从n到目标节点最佳路径的估计代价。

在当前节点的候选节点中，选取估价函数值f(n)最小的节点

以上时A*算法的主要的内容


使得具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法的充分条件是：
1、搜索树上存在着从起始点到终了点的最优路径。
2、问题域是有限的。
3、所有结点的子结点的搜索代价值>0。
4、h(n)=<h*(n) （h*(n)为实际问题的代价值）

一般情况下，前三个条件容易满足，关键在于第4个，估计代价h(n)的设计
因为实际情况下，h*(n)并不知道，h（n）的好坏与A*算法的表现优劣关系很大。
h(n)与h*(n)越接近，算法的效果越好。

如何设计一个合理的f(n)，是后续关注的重点。

以上是本人对A*算法的简单理解，不足之处，请指正。