搜索算法III：启发式搜索
[TABS_R id=2260]
在对最短路搜索时，如果起点与终点的距离较远，使用BFS会扩展出非常多的结点，运算量将是以指数式增长。尤其是比较“空旷”的状态转移，从起点到终点几乎没有阻碍，但是使用BFS仍然需要添加那些绕远路的节点。这时，我们应想一个办法，使我们的搜索优先去找“最有希望最短到达终点”的新结点，即使偶尔会绕远路，但在一马平川的情况，其高效就体现出来了。
但是，如果让搜索径直朝向终点扩展，那可能因为没有大局观而某几步走了近路反而导致一条路走到黑。实际上从起点出发的步数也应当考虑在代价之内。于是，启发式搜索便是这样的思路：定义函数\( F(X)= G(X) + H(X) \),其中\( G(X) \)就是常规的BFS扩展到状态\( X \)所用的步数，而 \( H(X) \) 则是我们为问题设计的评估函数，如果对所有状态的评估函数的值都一样就是常规的BFS，而经过设计的评估函数\( H(X) \)可以使启发式搜索比BFS更加优先快速地找到最短路。可以说\( H(X) \)设计的好坏决定了对问题使用启发式搜索效率的高低。
在设计\( H(X) \) 时，\( H(X) \)的值越大，就会越强烈地去搜索更近的路，效果也会越快，但应当注意，过于大的\( H(X) \)值会使搜索过程丢失最优解。所以，评估函数\( H(X) \)的值必须不大于实际当前状态到目标状态的代价.
启发式搜索在实际表现时，未必一定能比BFS要高效，一方面取决于评估函数的选取，另一个方面由于在选取状态时也会有额外的开销。而快速趋近目标结果所减少的时间，能否弥补这一部分开销也是非常关键的。
首先，我们使用走迷宫任务来探讨启发式搜索。从’+’出发到达’*’，并二者直线方向设立墙，使之需要稍微绕一下才能走到：
13 9 --------- --------- --------- --------- -+----#-- ------#-- ------#-- ------#-- ------#-- --#####-- --------- -------*-
直接使用BFS的走迷宫这样编写，我们将board访问的顺序用小写英文字母表示，’a’表示第1步的访问，’b’表示第2步的访问，…。
输出结果如下所示
可以看出搜索的结点非常多，即使是完全反方向的那些结点也全部搜索到了。启发式搜索则一定程度上少搜索一些绕远路的结点（但也不能完全不搜索，因为可能直线距离的近路是“死胡同”，怎么设计就看评估函数\(H(X)\)的好坏）。
如果我们使用启发式搜索，首先应使用两个表openList和closeList，定义\(F\)为初始到状态的步数\(G\)与评估函数\(H\)之和。流程为：
- 计算初始的\(F\)值加入openList.
- 从openlist中取出\(F\)值最小的状态\(u\)，并将 \(u\) 加入closelist。若 \(u\) 为目标状态，结束搜索；
- 对 \(u\) 进行扩展，假设其扩展的状态为 \(v\) ：若 \(v\) 未出现过，计算 \(v\) 的\( F\)值并加入openlist；若 \(v\) 在openlist中，更新 \(v\) 的 \( F\) 值，取较小的一个；若 \(v\) 在closelist中，抛弃该状态。
- 若openlist为空，结束搜索。否则回到2。
在实现这个算法时，openList的操作有取得最小值和元素存在性，而closeList只需要判断存在性，所以openList稍微麻烦一些。若使用C++ STL中的priority_queue虽然可以较快取出最小元素，但无法判断元素存在性。所以我们还要自己编写一个小顶堆，在取得最小元素的同时，能够遍历整个堆来判断其存在性。而closeList只需要用保存状态的0/1数组即可。
利用这个方法可以避免搜索一些明显会远离目标状态的状态，从而缩小搜索空间，早一步搜索到目标结果。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <set>
#include "heap.cpp"
#define MAXN 25
char closeList[MAXN][MAXN];
char board[MAXN][MAXN];
int H,W;
void outputBoard()
{
for (int i=0;i<=H+1;i++){
for (int j=0;j<=W+1;j++){
printf("%c",board[i][j]);
}
printf("\n");
}
}
int evaluate(qNode c,int endX,int endY)
{
return abs(c.x-endX) + abs(c.y - endY);
}
void AStarSearch(int startX,int startY)
{
int i,j,endX,endY;
for(i=1;i<=H;i++)
for(j=1;j<=W;j++){
if(board[i][j]=='*') {
endX=i;
endY=j;
}
}
int dir[8][2] = {
{0, -1},{0, 1},{-1, 0},{1,0},
{1, -1},{1, 1},{-1, -1},{-1,1}
};
heap_t *h = heap_create(1,cmp_qNode);
heap_push(h,qNode(startX,startY,0,0,0));
while(!heap_empty(h)){
qNode curr = heap_top(h);
if(curr.x==endX && curr.y==endY)
{
break;
}
heap_pop(h);
closeList[curr.x][curr.y]=1;
for(i=0;i<8;i++)
{
int dx = curr.x+dir[i][0];
int dy = curr.y+dir[i][1];
if(board[dx][dy]!='#'){
qNode next;
next.x = dx;
next.y = dy;
next.G;
next.H;
next.F = next.G + next.H;
if(heap_exists(h,next)){
if(next.F > next.H + curr.G+1){
next.F = next.H + curr.G + 1;
}
} else if(closeList[dx][dy]==1){
continue;
} else {
next.G = curr.G+1;
next.H = evaluate(next,endX,endY);
next.F = next.G + next.H;
board[dx][dy]='a'+next.G-1;
heap_push(h,next);
}
}
}
}
outputBoard();
}
int main(void)
{
int i,j;
memset(board,'#',sizeof(board));
memset(closeList,0,sizeof(closeList));
scanf("%d%d",&H,&W);
getchar();
for (i=1;i<=H;i++){
for (j=1;j<=W;j++){
scanf("%c",&board[i][j]);
}
getchar();
}
outputBoard();
AStarSearch(6,2);
return 0;
}
这时的搜索顺序是这样的
可以看出，启发式搜索会尽量地朝向终点的方向去搜索，不会向“南辕北辙”的路走，减少了搜索的结点。