搜索是人工智能中解决问题采用的主要策略，在看《人工智能，一种现代的方法》的时候，发现了这个搜索算法。但书上讲的主要是理论，以下是该算法的总结和与ACM的结合训练
盲目搜索
无信息搜索（盲目）搜索策略，指的是除了问题定义中提供的状态信息外，没有任何附加的信息。搜索也只会盲目的进行。搜索方式如下：
- 宽度优先搜索（BFS）
- 一致代价搜索（类Dijkstra最短路径搜索算法）
- 深度优先搜索（DFS）
- 深度受限搜索（用于控制无限深度的树，定义一个深度搜索的界限l）
- 迭代加深的深度优先搜索（与深度优先搜索结合使用来确定最好的深度界限）
- 双向搜索（从两端同时进行搜索，因为bd/2+bd/2要比dd小很多）
以上搜索在我以前做的题中，或多或少都遇到过。但是因为题的范围限制，搜索的深度都不是很高。一旦遇到深度大的搜索树，就尴尬了
启发式搜索
有信息的（启发式）搜索可以知道一个非目标的状态是否比其他的状态“更有希望”接近目标，从而达到比盲目搜索更好的搜索效果
首先，什么是目标状态，什么是非目标状态
如下图是一个八数码问题。空格子附近的数字可以移到空格子里面。，左边的方格状态经过怎样的移动之后能变成右边的方格状态
即，左边这个方格的状态就是非目标状态，而右边这个格子的状态就是目标状态
一个随机产生的八数码问题的平均解的步骤是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)来选择行动的路径
实战
hdu1043，也就是上面的八数码问题
在存储状态图的时候，我们使用了康拓展开算法，具体参考前面写的文章
花式全排列，不服不行（康拓展开）
AC代码如下
#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将给出最短解的精确步数。
减少了行动限制的问题，我们称为松弛问题
原有问题中的任一最优解同样是松弛问题的最优解；但是松弛问题可能有更好的解，理由是增加的边可能导致了捷径
一个名为ABSOLVER的程序可以从原始问题出发，使用“松弛问题”的技术和各种其他的技术自动的生成启发式（Prieditis，1993）
更多关于启发式的理论知识可以详见《人工智能，一种现代的方法》
网友评论