A*算法简介及例题

A*算法和一个例题

A*算法是一种很常用的路径查找和图形遍历算法。它有较好的性能和准确度。今天小编就为大家演示一遍A*算法的运算过程并用A*求解SCIO2005骑士精神的例题。

BFS算法回顾

谈到广度优先搜索就不得不说深度优先搜索，他们是一对孪生兄弟。深度优先搜索（DFS）的搜索方式是，不管有多少条岔路，先一条路走到底，不成功就返回上一个路口然后就选择下一条岔路。而广度优先搜索（BFS）的搜索方式是，面临一个路口时，把所有的岔路口都记下来，先选择其中一个进入，然后将它的分路情况记录下来，最后再返回来进入另外一个岔路，并重复这样的操作。

例如如图所示的案例，从黑色起点出发，目标为红色方块（假设不能斜着走）。第一次搜索只有两个方块可以选择，选择这两个方块并标记为走一步可以到达的地方。记录所有的岔路口，然后选择其中一个方向走进去。例如走黑点方块上面的那一个，然后将这个路口可走的方向记录下来并标记为2，意思是走两步可以到达的地方。很显然有三个方块是走两步就可以到达的地方。依此类推，分别继续标记3、4直到标记到红色方块。

A*算法

「A *（A-star）」算法是静态路网中求解最短路径最有效的直接搜索方法，也是许多其他问题的常用启发式算法。小编将用先图示演示一遍A*算法的运行过程，再介绍一段A*算法的代码，帮助小伙伴们更好地理解和运用A*。

如下图所示，需要找到从绿色方块出发，到红色方块的最短路径。蓝色区域为不可通行区域，需要绕道。

「第一步：开始搜索」

将起点周围的7个点纳入一个待检查列表A（起点正下方的点不能经过，因此忽略），这里的思想与前文介绍的BFS算法的思路类似。需要注意的是必须标注这些进入列表A的节点的父节点，以便在接下来的步骤中形成最短路径。结果如下图所示。

「第二步：计算成本」

假设总成本为f(n)，每个方格的f(n)都由当前成本g(n)和启发式信息计算函数h(n)组成，即f(n)=g(n)+h(n)。

当前成本g(n)就是指从起点到当前方格的路径长度，例如在本例中横向和纵向的移动代价为10，对角线的移动代价为14（√2）。那么在列表A中的最小g(n)就是10。

启发式信息计算函数h(n)指从当前方格到终点的估算成本（永远不会高估距离），这里我们可以使用曼哈顿距离来估算。所谓曼哈顿距离，其实就是获得两个方格之间的行数差，并将其与列数差相加而得到。例如下图中1号方格与0号方格和，曼哈顿距离为行差加列差：h(n)=4+6=10。

「第三步：继续搜索」

有第二步我们算出来每个方格的成本，显而易见，起点正右方的方格成本最低。

选择该方格，将它放入列表B（已检查列表）。接着检视其相邻方格，若相邻方格可走且不在列表A中，则将他们加入；若相邻方格已经在列表A中，则检查这条路径是否更优，也就是说经由当前方格是否具有更小的g(n)。若有更小的g(n)，则将那个方格的父亲设为当前选中的方格，然后重新计算成本。

在本例中，把首先选择的成本为40的方格从列表A中移出，移到已检查列表B中。它的右侧三块都是不能走的，左边是在列表B中的起点，没有新加入列表的方格。现在比较它相邻方格是否经过它成本更低，没有发现经由当前方格的更好路径，因此我们不做任何改变。

那么是时候选择下一个待处理方格了。按照成本计算，有两个方格的成本都是54，两者都可以作为下一个目标，简便起见我们就选择下面一个方格。如第一步，将新方块四周未进入列表A的方块加入列表A，如下图。

再次计算所有列表A中方块的成本：

选择成本为54的方格作为新的当前方格，将它四周的空余方格加入列表A。

当前方块没有其他可操作的内容了，我们进入下一方块。此时的成本最小方块为起点上面和起点左边的方块，都是60, 我们选择上面的方块。先将左上角的方块放入列表A。注意，此时检查当前方块正上方的方块时可以发现，经由当前方块其成本更低，因此改变其“父亲”。

接下来的步骤与之前类似：

如图，我们的最短路径长度就是56。那么我们怎么样去确定实际路径呢？很简单，从终点开始，按着箭头向父节点移动，这样你就被带回到了起点，这就是你的路径。

「A*算法总结：」

「1、」把起点加入待检查列表A中。

「2、」重复如下过程：

「a.」 遍历列表A，查找成本f(n)最小的节点，把它作为当前要处理的节点。

「b.」 把这个节点移到已检查的列表B中。

「c.」 对当前方格的 8 个相邻方格的每一个方格

◆ 如果它是不可抵达的或者它在列表B中，忽略它。

◆ 如果它不在列表A中，则将它加入A，并且把当前方格设置为它的父亲，记录该方格的成本f(n)。

◆ 如果它已经在列表A中，检查这条路径是否更好，用g(n)作参考。更小的g(n)表示这是更好的路径。如果是这样，把它的父亲设置为当前方格，并重新计算它的g(n)和f(n)。

「d.」 停止，当你

◆ 把终点加入到了列表A中，此时路径已经找到了

◆ 查找终点失败，并且列表A是空的，此时没有路径。3.保存路径。从终点开始，每个方格沿着父节点移动直至起点，这就是你的路径。

「下面是一道可以使用A*算法来做的题目：」

（题目来源：SCOI 2005 骑士精神）

问题描述：

一个5*5的棋盘上有12个黑骑士和12个白骑士，有且仅有一个空位。“骑士”棋子的移动方式基本等同于中国象棋中的马，即走“日”字。现在给定棋盘上棋子的一个状态，求使其恢复如图初始状态的棋盘最少需要多少步。

棋盘的目标状态

「输入格式」：第一行有一个正整数T(T<=10)，表示一共有N组数据。接下来有T个5×5的矩阵，0表示白色骑士，1表示黑色骑士，*表示空位。两组数据之间没有空行。

「输出格式：」对于每组数据都输出一行。如果能在15步以内(包括15步)到达目标状态，则输出步数，否则输出－1。

问题分析：

看起来就很像是写一个暴力搜索的题目。BFS和DFS的基本思路其实都很好找。但是暴力搜索的效率实在是太低了。所以本题我们给普通的BFS加上一个估价函数成为A*，让我们的搜索更加具有「方向性」，就可以大大减少算法的耗时。

本题中，我们选用当前实际步数g(n)和未来最完美步数的估计值h(n)之和作为估价函数f(n)。而对于h(n)，我们可以分析知，对于一匹不在自己位置上的马，在最优的情况下，我们只需要一次移动就能使这匹马归位。假设每一匹这样的马都需要移动一次，所以我们统计这样的马的个数作为h(n)即可。

更加详细的讲解已经注释在本题代码之中。

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
//f=g+h
int OneMove[8][2]={{2,1},{-2,-1},{1,2},{-1,-2},{2,-1},{-2,1},{1,-2},{-1,2}};
//八个偏移数组，特别地把两个相反的方向写在临近的位置上，这样每个方向相反的方向就是它的编号^1
int Goal[5][5]={
 {1, 1, 1, 1, 1},
 {0, 1, 1, 1, 1},
 {0, 0,-1, 1, 1},
 {0, 0, 0, 0, 1},
 {0, 0, 0, 0, 0}
};
//1表示黑子，0表示白子，-1表示空格 
int Times;
struct Node{//以空格为节点 
     int g,h;//g为以及走过的步数，h为估计接下来要走的步数 
     int xx,yy;
     int map[5][5];//记录当前状况 
     int las;//来时的方向，不再加入搜索范围内 
     Node() {
          g=h=0;
          las=-1; //初始的没有上一方向
     }
     bool operator <(const Node &a)const{
      return g+h>a.g+a.h;
     }//把估值函数作为优先队列的排序标准 
};
int Evaluate(Node tar)
{
     int cnt=0;
     for(int i=0;i<5;i++)
     {
          for(int j=0;j<5;j++) if(tar.map[i][j]!=Goal[i][j]) cnt++;
     }
// cout<<cnt<<endl;
     return cnt;
}//计算估值中的h值 
void A_star(Node &START)
{
     priority_queue<Node>q;
     q.push(START); 
     while(!q.empty())
     {
          Node now=q.top(); q.pop();
          if (now.g>15) 
          { //每次弹出的一定是g+h最小的，既然他的g都超过15了，那他后边的一定也超过15了，所以直接判断-1
               cout <<-1<< endl;
               break;
          }
          if (!Evaluate(now)) 
          { //evaluate也可当做判断两个状态是否相等的函数
               cout<<now.g<<endl;
               break;
          }
          for(int i=0;i<8;i++)//向8个可能的方向移动
          {
               if(i==now.las) continue;
               Node tmp=now;
               tmp.xx=now.xx+OneMove[i][0]; tmp.yy=now.yy+OneMove[i][1];
               if(tmp.xx<=4&&tmp.xx>=0&&tmp.yy<=4&&tmp.yy>=0)//判断是否越界 
               {
                    tmp.g++;
                    tmp.las=i^1;
                    swap(tmp.map[now.xx][now.yy],tmp.map[tmp.xx][tmp.yy]); 
                    tmp.h=Evaluate(tmp);//计算h值 
                    q.push(tmp);
               } 
          }
     }
} 
int main()
{
     cin>>Times;
     string s;
     while(Times--)
     {
          Node First;
          for(int i=0;i<5;i++)
          {
               cin>>s;
               for(int j=0;j<5;j++)
               {
                    if(s[j]=='0') First.map[i][j]=0;
                    if(s[j]=='1') First.map[i][j]=1;
                    if(s[j]=='*') 
                    {
                         First.map[i][j]=-1;
                         First.xx=i; First.yy=j;
                    }
               }
          }
          A_star(First);
     }
 return 0;
} 

-The End-

文案&排版：王思涵、黄锐扬

指导老师：秦虎老师 （华中科技大学管理学院）

如对文中内容有疑问，欢迎交流。PS：部分资料来自网络。