这里会显示出您选择的修订版和当前版本之间的差别。
两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
2020-2021:teams:no_morning_training:shaco:知识点:搜索:a [2020/08/20 19:01] shaco |
2020-2021:teams:no_morning_training:shaco:知识点:搜索:a [2020/08/20 19:30] (当前版本) shaco |
||
---|---|---|---|
行 1: | 行 1: | ||
====== A* ====== | ====== A* ====== | ||
===== 简介&思想 ===== | ===== 简介&思想 ===== | ||
- | 通过估价函数预计搜索到的结点与终点的距离,以估价距离从小到大为顺序搜索终点,得到最短路,减少搜索时间。 | + | 通过估价函数预计搜索到的结点与终点的距离,以估价距离从小到大为顺序搜索终点,得到最短路,减少搜索时间。与dijkstra相似。\\ |
+ | 估价函数越大搜索越少,但估价函数小于等于真实距离时才能得到正确的结果,因此要注意估价函数的选取,可以调整估价函数的倍数。 | ||
===== 例题 ===== | ===== 例题 ===== | ||
- | ==== ==== | + | ==== 八数码难题 ==== |
- | **来源**: | + | **来源**:洛谷 p1379 |
- | **概述**: | + | **概述**:3x3的棋盘上有八个棋子和一个空白,空白前后左右的棋子可以填到空白处,给定初始布局和目标布局,求最少移动次数。 |
- | **答案**: | + | **答案**:统计当前布局每个数字距离目标布局中相同数字的距离作为估价,估计距离则为估价+当前移动次数,按照类似dij的做法,按估价距离的优先级更新结点,同时更新已知结点的最优移动次数并更新其估价距离,直到得到终点。 |
<hidden code> | <hidden code> | ||
<code cpp> | <code cpp> | ||
- | + | #include<cstdio> | |
- | </code> | + | #include<map> |
- | </hidden> | + | #include<queue> |
- | ---- | + | #include<string> |
- | ===== ===== | + | #include<cstring> |
- | **来源**: | + | using namespace std; |
- | + | map<string,int>vist,D,H; | |
- | **概述**: | + | struct unit |
- | + | { | |
- | **答案**: | + | string state; |
- | <hidden code> | + | int d,h,f,p; |
- | <code cpp> | + | bool operator < (const unit&x) const |
- | + | { | |
- | </code> | + | return f>x.f; |
- | </hidden> | + | } |
- | ===== ===== | + | }; |
- | **来源**: | + | priority_queue<unit>q; |
- | + | string End("123804765"); | |
- | **概述**: | + | int targ[9]={4,0,1,2,5,8,7,6,3},dpos[4][9]={{-1,-1,-1,0,1,2,3,4,5},{3,4,5,6,7,8,-1,-1,-1},{-1,0,1,-1,3,4,-1,6,7},{1,2,-1,4,5,-1,7,8,-1}}; |
- | + | int dis[9][9]={{0,1,2,1,2,3,2,3,4},{1,0,1,2,1,2,3,2,3},{2,1,0,3,2,1,4,3,2},{1,2,3,0,1,2,1,2,3},{2,1,2,1,0,1,2,1,2},{3,2,1,2,1,0,3,2,1},{2,3,4,1,2,3,0,1,2},{3,2,3,2,1,2,1,0,1},{4,3,2,3,2,1,2,1,0}}; | |
- | **答案**: | + | void read() |
- | + | { | |
- | <hidden code> | + | string s; |
- | <code cpp> | + | s.resize(9); |
+ | scanf("%s",&s[0]); | ||
+ | unit zero; | ||
+ | zero.state=s; | ||
+ | zero.d=zero.h=0; | ||
+ | for(int i=0;i<9;i++) | ||
+ | { | ||
+ | zero.h+=dis[i][targ[s[i]-48]]; | ||
+ | if(s[i]==48) | ||
+ | zero.p=i; | ||
+ | } | ||
+ | zero.f=zero.h>>1; | ||
+ | q.push(zero); | ||
+ | D[s]=0; | ||
+ | H[s]=zero.h; | ||
+ | } | ||
+ | int main() | ||
+ | { | ||
+ | read(); | ||
+ | int m=1; | ||
+ | unit head; | ||
+ | while(m--) | ||
+ | { | ||
+ | head=q.top(); | ||
+ | q.pop(); | ||
+ | if(head.state==End) | ||
+ | { | ||
+ | printf("%d",head.d); | ||
+ | return 0; | ||
+ | } | ||
+ | if(vist[head.state]==-1) | ||
+ | continue; | ||
+ | vist[head.state]=-1; | ||
+ | string state_; | ||
+ | for(int i=0,p_,h_,d_;i<4;i++) | ||
+ | { | ||
+ | p_=dpos[i][head.p]; | ||
+ | if(p_>=0) | ||
+ | { | ||
+ | state_=head.state; | ||
+ | state_[head.p]=state_[p_]; | ||
+ | state_[p_]=48; | ||
+ | if(vist[state_]==-1) continue; | ||
+ | d_=head.d+1; | ||
+ | if(!vist[state_]) | ||
+ | { | ||
+ | h_=head.h-dis[head.p][targ[0]]-dis[p_][targ[head.state[p_]-48]]+dis[head.p][targ[state_[head.p]-48]]+dis[p_][targ[0]]; | ||
+ | q.push({state_,d_,h_,d_+(h_>>1),p_}); | ||
+ | m++; | ||
+ | D[state_]=d_; | ||
+ | H[state_]=h_; | ||
+ | vist[state_]=1; | ||
+ | } | ||
+ | else if(d_<D[state_]) | ||
+ | { | ||
+ | q.push({state_,d_,d_+(H[state_]>>1),p_}); | ||
+ | m++; | ||
+ | D[state_]=d_; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | return 0; | ||
+ | } | ||
</code> | </code> | ||
</hidden> | </hidden> | ||
---- | ---- | ||
===== 总结 ===== | ===== 总结 ===== | ||
- |