A*算法——启发式搜索

A*算法

本质还是搜索：加了优化而已

关于这个优化，听到两种说法：

1.剪枝

通过判断预计最少还要几步，加强版剪枝

比如说一个经典剪枝：

如果

步数≥已知最小值

则

剪枝

升级|

如果

步数+最少还要几步≥已知最小值

则

剪枝

2.修改顺序

每次搜索时优先考虑最有可能是最有解的选项

（启发的感觉）

可以建个优先队列来维护每次取到的f最小

注：

f=g+h

g为已经用的步数

h为预计要用的步数

——我倾向于这一种，因为感觉更加神奇，而且写出来是非递归（递归的心理阴影）——

下面来一道水题：BFS轻松过的我来写A*

http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19699

poj3984

事实上既然m n都是5，BFS说不定会比A*更优

但是说明问题就好

 1 #include <cstdio>
 2 #include <queue>
 3 #include <cmath>
 4 using namespace std;
 5 struct hh
 6 {
 7     int x,y,z;
 8 };
 9 priority_queue<hh> q;
10 int n,m,t,x1,yy,x2,y2,_x,_y;
11 bool ma[101][101],b[101][101],c[101][101];
12 int f[101][101],g[101][101],h[101][101],fa[101][101],mo[101][101];
13 bool operator <(hh a,hh b)
14 {
15     return a.z>b.z;
16 }
17 int add(int x,int y,int z)
18 {
19     hh p;
20     p.x=y;p.y=z;p.z=x;
21     q.push(p);
22     return 0;
23 }
24 int check(int x,int y,int z,int ff,int m)
25 {
26     if(!ma[x][y])
27     {
28         if(b[x][y])
29         {
30             if(g[x][y]>z)
31             {
32                 g[x][y]=z;
33                 f[x][y]=z+h[x][y];
34                 fa[x][y]=ff;
35                 mo[x][y]=m;
36                 add(f[x][y],x,y);
37             }
38         }
39         else
40         if(!c[x][y])
41         {
42             b[x][y]=true;
43             g[x][y]=z;
44             h[x][y]=abs(x-x2)+abs(y-y2);
45             f[x][y]=g[x][y]+h[x][y];
46             fa[x][y]=ff;
47             mo[x][y]=m;
48             add(f[x][y],x,y);
49         }
50     }
51     return 0;
52 }
53 int a_star()
54 {
55     check(x1,yy,0,0,0);
56     while(!q.empty())
57     {
58         int x=q.top().x;
59         int y=q.top().y;
60          q.pop();
61         if((x==x2)&&(y==y2))
62             return g[x][y];
63         b[x][y]=false;
64         c[x][y]=true;
65         check(x-1,y,g[x][y]+1,x,y);
66         check(x,y-1,g[x][y]+1,x,y);
67         check(x+1,y,g[x][y]+1,x,y);
68         check(x,y+1,g[x][y]+1,x,y);
69     }
70     return 0;
71 }
72 int print(int x,int y)
73 {
74     if(fa[x][y]>0)
75         print(fa[x][y],mo[x][y]);
76     printf("(%d, %d)
",x-1,y-1);
77     return 0;
78 }
79 int main()
80 {
81     n=5;m=5;
82     for(int i=1;i<=n;i++)
83         for(int j=1;j<=m;j++)
84             scanf("%d",&ma[i][j]);
85     x1=1;yy=1;x2=5;y2=5;
86     a_star();
87     print(5,5);
88     return 0;
89 }

代码不是很长，而且因为刚写完别的题，这里只是套了一下，很多代码是多余的

print递归输出不用管

a_star是主要程序（一看就知道）

check用于检查当前点周围一圈的点能不能加入队列，b表示点是否已经加入，c表示该点是否已经退出（已退出的不用管了）

记得在有更优值时更新

其实像是一种更加神奇的Dj——优先级是预计中的全路而不是已搜到的路，让程序能稍稍有点远见前面是坑还是会钻

这样写最神奇的地方在于它会向着目标一头栽过去，而不是像广搜只顾着预定的顺序，更加接近正常人的逻辑，因此搜索范围大大减小。

既然每个点都只能进队列一次，这个算法的复杂度最差情况下还是很低的