鬼畜搜索

asuldb · 2018-07-21 17:38:31 · 个人记录

A*算法

好像是个并不是太常见的算法，好像没有什么题的正解是A*

但是这并不影响A*作为一个非常好用的瞎搞算法

发现网上讲的A*都太学术了，代码都太神了，好像并不适合在OI中使用

那干脆就根据自己的理解yy一波吧

我们考虑这样一个经典的问题

给定一张网格图，图上有一些障碍，求两个点之间的最短路

对于这个问题，我们最常规的思路其实是BFS，因为这的确是BFS的入门题

但我们的BFS效率并不高有可能遍历完整张图我们才能找到最短路

那我们还有什么方法呢

其中h(n)为估值函数，表示对n到t距离的估计值

其中g(n)表示s到n距离的真实值

至于怎么找最优的点自然是维护一个堆就行了

这里当然是维护一个小根堆了

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<cstdlib>
#define re register
#define maxn 5001
#define mp make_pair
#define x second.first
#define y second.second
#define step first.second
#define dis first.first
//dis[x]对应f(x)，step[x]对应g(x)
using namespace std;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
typedef pair< pair<int,int> ,pair<int,int> > pii;
priority_queue< pii,vector<pii>,greater<pii> > q;
char map[maxn][maxn],vis[maxn][maxn];
int n,m,ddx,ddy;
pii start,mid;
inline int h(int xx,int yy)
{
    return abs(xx-ddx)+abs(yy-ddy);
}//启发函数
inline void A_bfs()
{
    while(!q.empty()) q.pop();
    start.dis=h(start.x,start.y);
    vis[start.x][start.y]=1;
    q.push(start);
    while(!q.empty())
    {
        mid=q.top();
        q.pop();
        for(re int i=0;i<4;i++)
        {
            int xx=mid.x+dx[i];
            int yy=mid.y+dy[i];
            if(xx<1||yy<1||xx>n||yy>m||vis[xx][yy]) continue;
            if(xx==ddx&&yy==ddy) 
            {
                cout<<mid.step+1<<endl;
                return;
            }
            vis[xx][yy]=1;
            q.push(mp(mp(mid.step+1+h(xx,yy),mid.step+1),mp(xx,yy)));
        }
    }
    cout<<"-1"<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    while(1)
    {
        cin>>n>>m;
        if(!n) return 0;
        memset(vis,0,sizeof(vis));
        for(re int i=1;i<=n;i++)
        for(re int j=1;j<=m;j++)
        {
            cin>>map[i][j];
            if(map[i][j]=='@') start.x=i,start.y=j;
            if(map[i][j]=='#') vis[i][j]=1;
            if(map[i][j]=='*')  ddx=i,ddy=j;
        }
        A_bfs();
    }
}

还有一道例题

[SCOI2005]骑士精神

题目

好像是很多人的A*算法入门题

也是我的

这道题靠什么双向BFS，迭代加深也能刚过去

但是这道题在A*上对于我们估值函数的设计有了新的启发

我们这里要考虑的并不是简单的寻路问题，而是一个较为复杂的棋盘移动问题

我们还是可以利用A*来做的

但是估值函数的设计是一个引人深思的问题

反正这里也不能设计成什么曼哈顿距离了

那我们怎么设计呢

其实也是距离，到最终目标状态的距离

即不在位的棋子的数量

由于我们一次移动还不一定能保证有一个棋子归位，所以我们这样设计估值函数正确性还是有一定保障的

代码，这里的A*写成了DFS的形式了

#include<iostream>
#include<cstdio>
#include<cstring>
#define re register
#define maxn 15
#define INF 9999999
using namespace std;
char map[maxn][maxn];
const char ch[6][6]={
    '0','0','0','0','0','0',
    '0','1','1','1','1','1',
    '0','0','1','1','1','1',
    '0','0','0','*','1','1',
    '0','0','0','0','0','1',
    '0','0','0','0','0','0',
};
const int dx[]={-2,-2,-1,-1,1,1,2,2};
const int dy[]={-1,1,-2,2,-2,2,-1,1};
int T,ans;
inline int pd()
{
    int tot=0;
    for(re int i=1;i<=5;i++)
    for(re int j=1;j<=5;j++) 
    if(map[i][j]!=ch[i][j]) tot++;//统计不在位棋子的数量
    return tot;
}
void dfs(int x,int y,int now,int px,int py)
{
    int k=pd();
    if(now>=ans) return;//普通的最优性剪枝，当前交换次数超过答案就退出
    if(now+k>16) return;//启发性的剪枝，当前答案加上我们的估计值如果大于16这个次数上限的话也退出
    if(!k)
    {
        ans=min(ans,now);
        return;
    }
    for(re int i=0;i<8;i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx<1||yy<1||xx>5||yy>5) continue;
        if(xx==px&&yy==py) continue;//不能退回到上一个状态
        swap(map[xx][yy],map[x][y]);
        dfs(xx,yy,now+1,x,y);
        swap(map[xx][yy],map[x][y]);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--)
    {
        int sx,sy;
        for(re int i=1;i<=5;i++)
        for(re int j=1;j<=5;j++)
        {
            cin>>map[i][j];
            if(map[i][j]=='*') sx=i,sy=j;
        }
        ans=INF;
        dfs(sx,sy,0,0,0);
        if(ans==INF) puts("-1");
        else printf("%d",ans),putchar(10);
    }
    return 0;
}