在宽度优先和深度优先的搜索中，我们按顺序搜索搜索顺序，因此被称为盲搜索，搜索效率非常低。
启发式搜索大大提高了搜索效率，从这两幅图可以看出它们的区别。
(左图类似盲搜索，右图为启发式搜索()图像源) ) )。
显然启发式搜索效率远大于盲搜索。
什么是启发式搜索？ 健康搜索
通过利用关于当前问题的信息作为启发式信息，能够提高检索效率，减少检索次数。
如何使用这些信息，定义了评价函数h(x )。 H(X )是对当前状态x的估计，表示从x状态到目标状态的距离。
有： 1、h(x )=0； 2、h(x )越小，表示x越接近目标状态； 3、如果h(x )==0，则达到了目标状态。
关于问题的启发式信息都被计算为一定的h(x )值，并引入搜索过程。
但是，即使有启发式信息也不行，从开始状态到x状态的成本也是必要的，我们称为g(x )。 例如，在迷宫问题和八数字问题中，我们的g(x )是从起点到x位置的步数，g(x )是距离或远离目标状态曼哈顿的数。 在最短路径中，我们的g(x )是到x点的权重，h ) x )是从x点到目标节点的最短短路或直线距离。
现在，虽然从h(x )和h(x )的定义中不知道，但是假设检索依据是f ) x )函数。
f(x )=g (x )时为等角搜索，完全按照花费了多少成本进行搜索。 例如bfs，我们每次都从相近的层开始搜索，一层一层地搜索； 然后dijkstra算法也开始根据各边的代价选择搜索方向。
f(x )=h ) x )时相当于贪婪优先搜索。 每次都接近离目标最近的状态。
发现等成本搜索具有完整性，可以找到最佳解，但效率太低。 贪婪优先搜索没有完整性，不一定能找到解，最坏的情况类似于dfs。
此时，有人提出了a算法。 设f(x )=g (x ) f(x ) )。 (这里的h ) x )没有限制。 算法的效率提高了，但不能保证找到最佳解，不匹配的h(x )定义将导致算法找不到解。 没有完整性和最优性。
几年后，有人提出了A*算法。 该算法只对a算法进行了少量的修改。 并证明，只要评价函数满足一定条件，算法一定会找到最优解。 评价函数满足一定条件的算法称为A*算法。
其限制条件为f(x )=g ) x (h ) x )。 成本函数g(x ) 0； h(x )的值小于等于从x到目标的实际成本h*(x )。 即定义的h(x )是可以接受的，也是乐观的。
你怎么理解第二个条件？
例如，假设你从x到目的地，h(x )是你感觉到或目测到的大概距离，h ) ) x )是你到达目的地后，你发现你实际上已经走了的距离。 你预计的距离一定比实际距离短，或者正好等于实际距离。 这样我们说你的h(x )是可以接受的，很乐观。
不同的评价函数可能对算法的效率有很大的影响。 特别地，对于h(x )的选择，例如，在以下八进制数字问题中，曼哈顿距离的和可以被选择为h )-x )，但是不同的网格也可以被选择为h )-x )。 但是，检索的次数不同。 h(x )越接近h* ) x )，扩展的节点越少！
A*算法的具体实现如何？
1、在open表中添加源点
2，
wile (打开！=NULL )
{
从OPEN表中取f(n )最小的节点n；
if(n节点==目标节点) () ) ) ) ) ) ) ) )。
布雷克；
for (当前节点n的每个子节点x ) ) ) )。
{
f (计算x；
if (新打开) )。
if (新f ) x ) ) )。
{
让n成为x的父亲；
如果不要求更新OPEN表的f(n )//路径的记录，可以直接参加OPEN表，但是旧的x节点不能先于新的离开队伍
}
是if (新关闭)
继续；
是if(Xnotinboth )
{
让n成为x的父亲；
求出f(x )
将x插入OPEN表中；
}
}//endfor
将n节点插入CLOSE表中；
根据f(n )对OPEN表的节点进行排序； //实际上是比较OPEN表内的节点f的大小，从最小路径的节点开始向下移动。
//end while (打开！=空)
3、保存路径，从目标点出发，按照父节点的指针遍历直到找到起点。
以八数字问题为例：
我们只考虑1、成本函数； 2、只考虑贪婪优先3、A*算法。
1 #包含
2 usin
g namespace std;3 struct Maze{
4 char s[3][3];
5 int i,j,fx,gx;
6 bool operator < (const Maze &a )const{
7 return fx>a.fx;
8 }
9 } c;
10 int fx[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
11 map mp;
12 int T;
13 int get_hx(char s[3][3]){
14 int hx=0;
15 for(int i=0;i<3;i++){
16 for(int j=0;j<3;j++){
17 hx+=abs(mp[s[i][j]].i-i)+abs(mp[s[i][j]].j-j);
18 }
19 }
20 return (int)hx;
21 }
22 void pr(char s[3][3]){
23 cout<
24 for(int i=0;i<3;i++){
25 for(int j=0;j<3;j++)
26 cout<
27 cout<
28 }
29 cout<
30 }
31 int key(char s[3][3]){
32 int ans=0;
33 for(int i=0;i<3;i++)
34 for(int j=0;j<3;j++)
35 ans=ans*10+(s[i][j]-'0');
36 return ans;
37 }
38 void BFS(){
39 T=0;
40 mapflag;
41 queue < Maze > q;
42 q.push(c);
43 flag[key(c.s)]=1;
44 while(!q.empty()){
45 Maze now=q.front();
46 q.pop();
47 pr(now.s);
48 if(get_hx(now.s)==0){
49 break;
50 }
51 for(int i=0;i<4;i++){
52 int x,y;
53 x=now.i+fx[i][0];
54 y=now.j+fx[i][1];
55 if(!(x>=0&&x<3&&y>=0&&y<3)) continue;
56 Maze tmp=now;
57 tmp.s[now.i][now.j]=tmp.s[x][y];
58 tmp.s[x][y]='0';
59 tmp.i=x ; tmp.j=y ;
60 tmp.fx++;
61 if(!flag[key(tmp.s)]){
62 q.push(tmp);
63 flag[key(tmp.s)]=1;
64 }
65 }
66 }
67 }
68 void Greedy_best_first_search(){
69 T=0;
70 priority_queue< Maze > q ;
71 mapflag;
72 c.fx=get_hx(c.s);
73 q.push(c);
74 flag[key(c.s)]=1;
75 while(!q.empty()){
76 Maze now=q.top();
77 q.pop();
78 pr(now.s);
79 if(get_hx(now.s)==0){
80 break;
81 }
82 for(int i=0;i<4;i++){
83 int x,y;
84 x=now.i+fx[i][0];
85 y=now.j+fx[i][1];
86 if(!(x>=0&&x<3&&y>=0&&y<3)) continue;
87 Maze tmp=now;
88 tmp.s[now.i][now.j]=tmp.s[x][y];
89 tmp.s[x][y]='0';
90 tmp.i=x ; tmp.j=y ;
91 tmp.fx=get_hx(tmp.s);
92 if(!flag[key(tmp.s)]){
93 q.push(tmp);
94 flag[key(tmp.s)]=1;
95 }
96 }
97 }
98 }
99 void A_star(){
100 T=0;
101 priority_queue< Maze > q ;
102 mapflag;
103 c.gx=0;
104 c.fx=get_hx(c.s)+c.gx;
105 q.push(c);
106 while(!q.empty()){
107 Maze now=q.top();
108 q.pop();
109 flag[key(now.s)]=now.fx;
110 pr(now.s);
111 if(get_hx(now.s)==0){
112 break;
113 }
114 for(int i=0;i<4;i++){
115 int x,y;
116 x=now.i+fx[i][0];
117 y=now.j+fx[i][1];
118 if(!(x>=0&&x<3&&y>=0&&y<3)) continue;
119 Maze tmp=now;
120 tmp.s[now.i][now.j]=tmp.s[x][y];
121 tmp.s[x][y]='0';
122 tmp.i=x ; tmp.j=y ;
123 tmp.gx++;
124 tmp.fx=get_hx(tmp.s)+tmp.gx;
125 if(!flag[key(tmp.s)]){
126 q.push(tmp);
127 }else if(flag[key(tmp.s)]>tmp.fx){
128 flag[key(tmp.s)]=0;
129 q.push(tmp);
130 }
131 }
132 }
133 }
134 int main(){
135 mp['1'].i=0;mp['1'].j=0;
136 mp['2'].i=0;mp['2'].j=1;
137 mp['3'].i=0;mp['3'].j=2;
138 mp['4'].i=1;mp['4'].j=2;
139 mp['5'].i=2;mp['5'].j=2;
140 mp['6'].i=2;mp['6'].j=1;
141 mp['7'].i=2;mp['7'].j=0;
142 mp['8'].i=1;mp['8'].j=0;
143 mp['0'].i=1;mp['0'].j=1;
144 for(int i=0;i<3;i++){
145 for(int j=0;j<3;j++){
146 cin>>c.s[i][j];
147 }
148 char x=getchar();
149 }
150 cin>>c.i>>c.j;
151 c.fx=0;
152 cout<
153 BFS();
154 cout<
155 Greedy_best_first_search();
156 cout<
157 A_star();
158 return 0;
159 }
160 /*
161 283162 164163 705164 2 1165 */
结果显示：
1、仅考虑代价函数：36步。
2、仅考虑贪婪优先：5步。
3、A*算法：5步。
明显，在引入了启发式信息后，大大的提高了搜索的效率。
引申问题： 第 k 短路问题。
思路： 先从终点求出最短路，作为 h(x) 。然后维护优先队列，维护 F(x) 最小，第一次出来的终点是最短路，终点第二次出来的是次短路……
求第k短路时，A*算法优化的是查找的次数，可以理解为剪枝，更快速的找到最短路，次短路……
其他操作和正常的求最短路没有什么区别，找到终点第k次出队的值，就是第k短路。
(可能你会说在无向图中存在有回头路，没错，有可能次短路只是最短路走了一次回头路，但这确实也是一条次短路)。