A*算法

*搜寻算法俗称A星算法，从DFS和BFS中来。

  DFS算法：

  BFS算法：

 

盲目搜索：

前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。有可能需要试探完整个解集空间, 显然，只能适用于问题规模不大的搜索问题中。 

 

启发式搜素：

对每一个搜索位置都要通过一个启发函数来进行评估，评估代价最少的结点作为下一步搜索结点而跳转其上。

 

估价函数表示：

f(n) = g(n) + h(n)

 

成立条件：

 

 

1. 搜索树上存在着从起始点到终了点的最优路径。
2. 问题域是有限的。
3. 所有结点的子结点的搜索代价值>0。
4. h(n)=<h*(n) （h*(n)为实际问题的代价值）。

当此四个条件都满足时，一个具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法，并一定能找到最优解。

 

 

其中f(n) 是节点n的估价函数，g(n)为状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。如果说详细点，g(n)代表了搜索的广度的优先趋势。但是当h(n) >> g(n)时，可以省略g(n)，而提高效率。struct tree_node 

struct tree_node{
	double lng; //结点的经度坐标
	double lat; //结点的纬度坐标
	double fcost; //该结点对应的路径的f成本
	double gcost; // 该结点对应的路径的g成本
	double hcost; //该结点对应的路径的h成本
	bool  flag; //中间点和结点的区别位，0表示形状点，1表示结点，起止结点
	struct tree_node *father; /./指向父节点的指针，用于向上回溯
}; 
struct tree_node * p[MAXNUM];//指向路径中间点

struct link_open  //开启列表结构体
{
	struct tree_node *node; //指向表中存储的结点的指针
	double fcost_list; //表中存储结点的f成本
	double gcost_list; //表中存储结点的g成本
};
struct link_open   Openlist[20000],
 [20000];//openlist存储最新生成节点、更优节点，Closedlist存储搜索后得到最优节点。
 

 

用二叉推对openlist表排序

以下省略起始点坐标映射到路径和查找映射坐标点对应的中间点过程，即openlist表中以存储找到的其实映射点对应的最优中间点集。

 

待续。。。

 

While(Openlist!=NULL)
{
   从Openlist表中取估价值f最小的结点node;
   if(node==目标结点) 
   break;
else{
    if(node in Openlist) 
    比较两个X的估价值f //注意是同一个结点的两个不同路径的估价值
    if(node的估价值小于Openlist表的估价值 )　　　
     更新OPEN表中的估价值; //取最小路径的估价值
    if(node in Closedlist) 
     比较两个X的估价值 //注意是同一个结点的两个不同路径的估价值
   if(node的估价值小于Closedlist表的估价值 )　　　
      更新CLOSE表中的估价值; 
       把X结点放入Openlist//取最小路径的估价值
   if(node not in both)求X的估价值;　　　
       并将X插入Closedlist表中;　//还没有排序
     }
将n结点插入Closedlist表中;
按照估价值将Closedlist表中的结点排序; //实际上是比较Openlist表内结点f的大小，从最小路径的结点向下进行。
}

 

 

 

实际应用：

 最优路径查找，已知起始点和终止点坐标，要求2点映射在地图上的最优路径。