搜索算法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数组即可。
利用这个方法可以避免搜索一些明显会远离目标状态的状态，从而缩小搜索空间，早一步搜索到目标结果。
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;}这时的搜索顺序是这样的
可以看出，启发式搜索会尽量地朝向终点的方向去搜索，不会向“南辕北辙”的路走，减少了搜索的结点。