启发式的搜索策略

参考    启发式的搜索策略 - 云+社区 - 腾讯云

搜索是人工智能中解决问题采用的主要策略，在看《人工智能，一种现代的方法》的时候，发现了这个搜索算法。但书上讲的主要是理论，以下是该算法的总结和与ACM的结合训练。

1、盲目搜索

无信息搜索（盲目）搜索策略，指的是除了问题定义中提供的状态信息外，没有任何附加的信息。搜索也只会盲目的进行。搜索方式如下：

1. 宽度优先搜索（BFS）
2. 一致代价搜索（类Dijkstra最短路径搜索算法）
3. 深度优先搜索（DFS）
4. 深度受限搜索（用于控制无限深度的树，定义一个深度搜索的界限l）
5. 迭代加深的深度优先搜索（与深度优先搜索结合使用来确定最好的深度界限）
6. 双向搜索（从两端同时进行搜索，因为bd/2+bd/2要比dd小很多）

以上搜索在我以前做的题中，或多或少都遇到过。但是因为题的范围限制，搜索的深度都不是很高。一旦遇到深度大的搜索树，就尴尬了。

2、启发式搜索

有信息的（启发式）搜索可以知道一个非目标的状态是否比其他的状态“更有希望”接近目标，从而达到比盲目搜索更好的搜索效果

首先，什么是目标状态，什么是非目标状态

如下图是一个八数码问题。空格子附近的数字可以移到空格子里面。，左边的方格状态经过怎样的移动之后能变成右边的方格状态。

                           

即，左边这个方格的状态就是非目标状态，而右边这个格子的状态就是目标状态

一个随机产生的八数码问题的平均解的步骤是22步。分支因子约为3（分支因子即每一次移动的可能步数，在中间时有四种移动方式，在四个角上时只有两种移动的方式，在四条边上的时候有三种移动的方式）

这就意味着，到达深度为22的穷举搜索树将考虑322≈3.1×1010个状态，图搜索可以把这个数量削减到大约170000倍，因为只有9!/2=181440个不同的状态。

但是如果扩展到15数码问题（3×3变成4×4），那么这个数目大概是1013，庞大的状态集可以把你的计算机直接弄崩溃，因此我们需要找到一个好的启发函数

在这里我们描述两个常用的启发式函数：

• h1 = 不在位的棋子数，如上图，则起始状态时，h1 = 8（所有棋子都不在正确的位置）
• h2 = 所有棋子到达其目标位置的距离和。因为棋子不能斜着移动，距离相当于水平和竖直的距离和，也称为曼哈顿距离，如上图中的曼哈顿距离h2 = 3+1+2+2+2+3+3+2=18

那么问题来了，这两个启发式函数有什么用，h1和h2能帮我们更好的解决八数码问题吗？

启发式函数有什么用？

首先我们定义：f(n) = g(n) + h(n)

其中，f(n)是从初始状态到目标状态所花的总代价。g(n)是从初始状态到目标状态的路径代价，而h(n)是初始状态到目标状态的最小代价路径的估计值，也就是一个启发式函数。然后我们假设空的格子在中间位置。那么这个空格子可以上移（我们把其他数字移到空格子里看成空格子移过去），下移，左移，右移。这四个方位的g(n)都是1。即只需要花费1步的代价就可以到达目标。h(n)这里我们采用上面的h2，可以证明得到h2的效率恒高于h1（可以自证明）。那么上下左右的四个状态则可以计算出四个不同的h(n)，通过选择最小的h(n)，继续下一步的行动。因为g(n)都是1，所以f(n)的比较也就是h(n)的比较。

是不是有点Dijkstra算法的意思，一个是从A->B，选择每一步的行动的时候，是挑最近的那条路走，然后重新刷新所有点到终点的距离。而启发式搜索，在g(n)可以相等的情况下，就是根据h(n)来选择行动的路径

实战

#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
#define inf 0x7fffffff   //整数的最大值
using namespace std;
struct node{
    int map[3][3],x,y,f,g,h;
    friend bool operator < (node a,node b){
        return a.f > b.f;   //从小到大自动排序
    }
}start,target;  //定义开始状态和目标状态
int step[400010],v[400010],book[400010],targetNum=46234;
char str[4]={'u','d','l','r' };
int Can[10]={1,1,2,6,24,120,720,5040,40320 };  //全排列的压缩序列
int an[4][2]={-1,0, 1,0, 0,-1, 0,1 };  //上下左右的移动
int Cantor(node cur){ //康托展开
    int an[10],k=0,sum=0;
    for (int i=0 ;i<3 ;i++)
        for (int j=0 ;j<3 ;j++)
            an[k++]=cur.map[i][j];  //将二维转化为一维
    for (int i=0 ;i<9 ;i++){
        int k=0;
        for (int j=i+1 ;j<9 ;j++)
            if (an[i]>an[j]) k++;
        sum += k*Can[9-i-1];  //求出当前全排列是初始全排列的第几个
    }
    return sum+1;
}
int checkRoad(node an) {  ///判断此时奇偶性（因为每次调换都不会改变其奇偶性）
    int a[10],k=0,sum=0;
    for (int i=0 ;i<3 ;i++)
        for (int j=0 ;j<3 ;j++)
            a[k++]=an.map[i][j];  //将二位状态空间转化为一维
    for (int i=0 ;i<k ;i++) 
        if (a[i]!=0)
            for (int j=0 ;j<i ;j++)
                if (a[j]>a[i]) sum ++;  //判断移动是否需要变化逆序
    if (sum&1) return 0;   //奇数返回0
    return 1;  
}
void printRoad(node cur){   //输出移动路径
    string ans;
    int sum=targetNum;
    while (step[sum] != -1){  //如果上一个状态存在
        switch (v[sum]) {  //选择从上一个状态到达此状态经过的步骤
            case 0 : ans += str[0];break;
            case 1 : ans += str[1];break;
            case 2 : ans += str[2];break;
            case 3 : ans += str[3];break;
        }
        sum=step[sum];
    }
    for (int i=ans.size()-1; i>=0; i--)  cout<<ans[i];
    cout<<endl;
    return ;
}
int getH(node cur){
    int sum=0;
    for (int i=0 ;i<3 ;i++)
        for (int j=0 ;j<3 ;j++){
            int u = cur.map[i][j];
            int x = u>0?(u-1)/3:2, y = u>0?(u-1)%3:2;
            sum += abs(x-i)+abs(y-j);
        }
    return sum;
}
void aStar(node cur){
    priority_queue<node> Q;  //优先队列，默认从大到小
    cur.g=0; 
    cur.h=getH(cur);  //取得该状态的h值
    cur.f=cur.g + cur.h;
    Q.push(cur);  //将f作为比较关键字存入到Q中
    memset(book,-1,sizeof(book));   //初始化
    memset(step,-1,sizeof(step));
    memset(v,-1,sizeof(v));
    book[Cantor(cur)]=1;   //标记已经有过这个状态
    while (!Q.empty()){
        cur=Q.top();Q.pop();  //取出最小的路径状态
        if (Cantor(cur)==targetNum){  //如果已经到达目标
            printRoad(cur);   //打印行走的路径
            return ;
        }
        for (int i=0 ;i<4 ;i++){   //上下左右移动
            target.x=cur.x+an[i][0];
            target.y=cur.y+an[i][1];
            int x=cur.x ,y=cur.y ;
            for (int u=0 ;u<3 ;u++)  //初始化移动后的状态
                for (int v=0 ;v<3 ;v++)
                    target.map[u][v]=cur.map[u][v];
            if (target.x<0||target.x>=3||target.y<0||target.y>=3) continue;  //保证不会移出格子
            swap(target.map[target.x][target.y],target.map[x][y]);
            int sum=Cantor(target);
            if (book[sum]==-1){   //如果这个状态还不存在
                if (checkRoad(target)==0) continue;
                book[sum]=1;
                target.g=cur.g+1;  //路径都是一样的1
                target.h=getH(target);   //取得新的h值
                target.f=target.g+target.h;
                step[sum]=Cantor(cur);  //用来标记上一个的状态
                v[sum]=i;  //用来标记走的方向
                Q.push(target);   
            }
        }
    }
    return ;
}
int main(){
    char str[100];  //存储了初始字符串
    while (cin.getline(str,100)){  //读入
        int tx=0,ty=0;
        for (int i=0 ;i<strlen(str) ;i++){   //遍历读入的字符串
            if (str[i]>='0' && str[i]<='9') {
                start.map[tx][ty]=str[i]-'0';  //初始化开始状态
                if (++ty==3) {tx++;ty=0; }
            } else if (str[i]=='x') {
                start.map[tx][ty]=0;  //将x以0的形式存储
                start.x=tx ;start.y=ty ;  //记录开始的x的坐标
                if (++ty==3) {tx++;ty=0; }
            }
        }
        if (checkRoad(start)==0) {  //判断是否能够移到
            cout<<"unsolvable"<<endl;
            continue; 
        } 
        aStar(start);
    }
    return 0;
}

priority_queue是一个优先队列，每插入一个新的元素，内部都会重新进行一次排列。在结构体node中我们重载了操作符<，也就是说，优先队列的首个元素，即top()取得的值，是整个队列中最小的。因为上下左右四个移动的状态进行比较需要进行额外的存储，所以我们使用优先队列，省去了比较的步骤，启发式函数要怎么得到，我们已经看到了h1（错位棋子数）和h2（曼哈顿距离）对于八数码问题是相当好的启发式，而且h2更好。那么h2是如何被提取出来的，在人工智能领域，计算机能否机械的设计出这样的启发式呢？

答案是肯定的

h1和h2估算的是八数码问题中的剩余路径的长度，对于该问题的简化版本它们也是相当精确的路径长度。如果游戏的规则改为每个棋子可以随便移动，而不是可以移动到与其相邻的空位上，那么h1就是最短解的精确步数。类似的，如果一个棋子可以向任何方向移动，甚至可以移动到被其他棋子占据的位置上，那么h2将给出最短解的精确步数。减少了行动限制的问题，我们称为松弛问题。原有问题中的任一最优解同样是松弛问题的最优解；但是松弛问题可能有更好的解，理由是增加的边可能导致了捷径。