启发式搜索

启发式搜索

启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。

在启发式搜索中，我们每次找到当前“最有希望是最短路径”的状态进行扩展。对于每个状态的我们用函数F来估计它是否有希望。F包含两个部分：

F = G + H

G：就是普通宽度优先搜索中的从起始状态到当前状态的代价，

H：是一个估计的值，表示从当前状态到目标状态估计的代价。

H是由我们自己设计的，H函数设计的好坏决定了启发式算法的效率。H值越大，算法运行越快。

但是在设计评估函数时，需要注意一个很重要的性质：评估函数的值一定要小于等于实际当前状态到目标状态的代价。

否则虽然你的程序运行速度加快，但是可能在搜索过程中漏掉了最优解。相对的，只要评估函数的值小于等于实际当前状态到目标状态的代价，就一定能找到最优解

F：评估值和状态值的总和。

 

同时在启发式搜索中将原来的一个队列变成了两个队列：openlist和closelist。

在openlist中的状态，其F值还可能发生变化。而在closelist中的状态，其F值一定不会再发生改变。

整个搜索解的流程变为：

计算初始状态的F值，并将其加入openlist

从openlist中取出F值最小的状态u，并将u加入closelist。若u为目标状态，结束搜索；

对u进行扩展，假设其扩展的状态为v：若v未出现过，计算v的f值并加入openlist；若v在openlist中，更新v的F值，取较小的一个；若v在closelist中，抛弃该状态。

若openlist为空，结束搜索。否则回到2。

利用这个方法可以避免搜索一些明显会远离目标状态的状态，从而缩小搜索空间，早一步搜索到目标结果。

在启发式搜索中，最重要的是评估函数的选取，一个好的评估函数能够更快的趋近于目标状态。

 

启发式搜索在某些情况下并不一定好用，一方面取决于评估函数的选取，另一个方面由于在选取状态时也会有额外的开销。而快速趋近目标结果所减少的时间，能否弥补这一部分开销也是非常关键的。

所以根据题目选取合适的搜索方法才是最重要的。

 

问题：八数码求解的步数

伪代码：

search(status):start.status = statusstart.g = 0 // 实际步数start.h = evaluate(start.status)start.f = start.g + start.hopenlist.insert(start)While (!openlist.isEmpty()) u = openlist.getMinFStatus()closelist.insert(u)For v is u.neighborStatusIf (v in openlist) Then// 更新v的f值If (v.f > v.h + u.g + 1) Thenv.f = v.h + u.g + 1End IfElse If (v in closelist)continueElse v.g = u.g + 1v.h = evaluate(v.status)v.f = v.g + v.hopenlist.insert(v)End IfEnd ForEnd While

源码：

#include <cstring> #include <cmath> #include <queue> #include <stack> #include <algorithm> #include <iostream> using namespace std; struct node{ int f,h,g; int x,y;char map[3][3]; friend bool operator< (const node &a,const node &b){if(a.f==b.f) return a.g<b.g; return a.f>b.f; } }; node start; int Hash[15]; // Hash[i] 存 i! 1~9 int pos[][2]= {{0,0},{0,1},{0,2},{1,0},{1,1},{1,2},{2,0},{2,1},{2,2}}; // 0~8 的目标位置的坐标 int to[4][2]={0,-1,0,1,-1,0,1,0}; bool vis[500000]; //判断不可能的状况 bool check(){ int s[20]; int cnt = 0; for(int i = 0; i<3; i++){ for(int j = 0; j<3; j++){ s[3*i+j] = start.map[i][j]; if(s[3*i+j] == 'x') continue; for(int k = 3*i+j-1; k>=0; k--){if(s[k] == 'x') continue; if(s[k]>s[3*i+j]) cnt++; } } } if(cnt%2) return false; return true; } //康托 int solve(node a){ int s[20]; int ans = 0; for(int i = 0; i<3; i++){ for(int j = 0; j<3; j++){ s[3*i+j] = a.map[i][j]; int cnt = 0; for(int k = 3*i+j-1; k>=0; k--){ if(s[k]>s[3*i+j]) cnt++; } ans = ans+Hash[i*3+j]*cnt; } } return ans; } //得到 H值 ,曼哈顿距离之和 int get_h(node a){ int ans = 0; for(int i = 0; i<3; i++){ for(int j = 0; j<3; j++){ if(a.map[i][j] == 'x') continue; int k = a.map[i][j]-'1'; ans+=abs(pos[k][0]-i)+abs(pos[k][1]-j); }} return ans; }int bfs(){ memset(vis,0,sizeof(vis)); // queue<node> Q; priority_queue<node> Q; start.g = 0; start.h = get_h(start); start.f = start.h; vis[solve(start)]=true;if(solve(start)==0) return 0;Q.push(start); node next;while(!Q.empty()){ node a = Q.top(); Q.pop(); // node a = Q.front();int k_s = solve(a); vis[k_s]=true;for(int i = 0; i<4; i++){next = a; next.x+=to[i][0]; next.y+=to[i][1]; if(next.x < 0 || next.y < 0 || next.x>2 || next.y > 2) continue; next.map[a.x][a.y] = a.map[next.x][next.y]; next.map[next.x][next.y] = 'x'; next.g+=1; next.h = get_h(next); next.f = next.g+next.h; int k_n = solve(next); if(vis[k_n]) continue; Q.push(next); if(k_n == 0) return next.g; } } } int main(){ Hash[0] = 1; for(int i = 1; i<=9; i++) Hash[i] = Hash[i-1]*i; int t=0;cin>>t;char a=0;while(t--){for (int i=0;i<3;i++){for (int j=0;j<3;j++){cin>>a;start.map[i][j]=a;if(a=='0'){start.map[i][j]='x';start.x=i;start.y=j;}}}if(!check()){ cout<<"No Solution!"<<endl; } else cout<<bfs()<<endl; } return 0; } View Code

 

转载于:https://www.cnblogs.com/ygdblogs/p/5578653.html

总结

以上是生活随笔为你收集整理的启发式搜索的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。