python实现A*搜索算法的学习_a*算法 python 搜索树

维基百科：

A*算法：一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。该算法像Dijkstra算法一样，可以找到一条最短路径；也想BFS一样，进行启发式的搜索。

公式：f(n) = g(n) + h(n),g(n)表示起点到任一点n的实际距离，h（n）表示任一点n到目标顶点的估算距离。

特性：a，若h（n）为0，只需求出g(n),既求出起点到任一点的最短路径，则转化为单元最短路径问题，Dijkstra算法

b，若h(n) <= 'n到目标的实际距离'，则一定可以求出最优解。而已h(n)越小，需要计算的节点越多，算法效率越低。

伪代码：

 function A*(start,goal)
     closedset := the empty set                 //已经被估算的节点集合    
     openset := set containing the initial node //将要被估算的节点集合
     came_from := empty map
     g_score[start] := 0                        //g(n)
     h_score[start] := heuristic_estimate_of_distance(start, goal)    //h(n)
     f_score[start] := h_score[start]            //f(n)=h(n)+g(n)，由于g(n)=0࿰