【学习笔记】$A*$与$IDA*$

A*

思路

A*就是在广搜的时候添加一个估价函数$f(x)$，\[f(x) = g(x) + h(x)\]，其中$f(x)$表示当前状态的总估价，$g(x)$表示已经经过的代价，$h(x)$表示预估接下来需要的代价，然后以$f(x)$为优先级用优先队列代替普通队列维护状态。

应用

在一定程度上防止TLE或者MLE（但是如果控制不好优化的度可能会WA）。如果估价函数一定是正确的话，可以用来求第$k$优解

例题

魔法猪学院

需要知道走到第几短的路径时到达上限。可以先在反图跑最短路，然后A*广搜，估价函数是走过的距离加上还需要的最短距离。这样，第$K$个到达的就是$K$短路

代码如下

// luogu-judger-enable-o2
#include <iostream>
#include <deque>
#include <queue>
#include <cstring>

using namespace std;

const int MAXN = 5e3 + 5;
const int MAXM = 2e5 + 5;
const double EPS = 1e-6;

int head[MAXN], nxt[MAXM << 1], to[MAXM << 1], cnt;
double w[MAXM << 1];
double dis[MAXN], e;
bool vis[MAXN];
int n, m, ans = 0;

struct Data{
    int now;
    double step, g;
    
    bool operator < (const Data &b) const {return (g == b.g) ? step > b.step : g > b.g;};
};

void AddEdge(int u, int v, double w) {
    nxt[cnt] = head[u];
    to[cnt] = v;
    :: w[cnt] = w;
    head[u] = cnt;
    cnt++;
}

void Spfa() {
    memset(dis, 0x7f, sizeof(dis));
    dis[n] = 0; vis[n] = true;
    deque<int> q;
    q.push_back(n);
    while (!q.empty()) {
        int u = q.front(); q.pop_front(); vis[u] = false;
        for (int i = head[u]; ~i; i = nxt[i]) {
            int v = to[i];
            if (i % 2 == 1) {
                if (dis[v] > dis[u] + w[i]) {
                    dis[v] = dis[u] + w[i];
                    if (!vis[v]) {
                        vis[v] = true;
                        if (!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);
                        else q.push_back(v);
                    }
                }
            }
        }
    }
}

void Astar() {
    priority_queue<Data> q;
    Data s;
    s.now = 1; s.step = 0; s.g = s.step + dis[s.now];
    q.push(s);
    while (!q.empty() && (e + EPS > 0)) {
        Data x = q.top(); q.pop();
        if (x.now == n) {
            if (e - x.step + EPS > 0) ans++, e -= x.step;
            else e = -100;
        }
        if (x.g > e) break;
        for (int i = head[x.now]; ~i; i = nxt[i]) {
            if (!(i & 1)) {
                Data nx;
                nx.now = to[i];
                nx.step = x.step + w[i];
                nx.g = nx.step + dis[nx.now];
                if (nx.g > e) continue;
                q.push(nx);
            }
        }
    }
}

int main() {
    ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    memset(head, -1, sizeof(head));
    cin >> n >> m >> e;
    for (int i = 1; i <= m; i++) {
        int a, b;
        double c;
        cin >> a >> b >> c;
        AddEdge(a, b, c);
        AddEdge(b, a, c);
    }
    Spfa();
    Astar();
    cout << ans << endl;
    return 0;
}

IDA*

思想

和A*类似是对Dfs进行估价，然后迭代加深。

题目

骑士精神

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
char mapp[6][6];

char tar[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',
};
int ans=1999;
inline int check()
{
    int res=0;
    for(register int i=1;i<=5;++i)
    {
        for(register int j=1;j<=5;j++)
        {
            res+= (mapp[i][j]==tar[i][j])?0:1;
        }
    }
    return res;
}
int dx[9]={0,-2,-2,-1,-1,1,1,2,2};
int dy[9]={0,-1,1,-2,2,-2,2,-1,1};
void swap(char &aa,char &bb)
{
    char temp=aa;
    aa=bb;
    bb=temp;
    return;
}
void dfs(int steps,int last,int x,int y)
{
    if(!check())
    {
        ans=min(ans,steps);
        return;
    }
    if(check()+steps>16)
    {
        return;
    }
    for(register int i=1;i<=8;i++)
    {
        if(i+last==9)
        {
            continue;
        }
        if(x+dx[i]>5||y+dy[i]>5)
        {
            continue;
        }
        if(x+dx[i]<1||y+dy[i]<1)
        {
            continue;
        }
        if(last+i==9)
        {
            return;
        }
        swap(mapp[x][y],mapp[x+dx[i]][y+dy[i]]);
        dfs(steps+1,i,x+dx[i],y+dy[i]);
        swap(mapp[x][y],mapp[x+dx[i]][y+dy[i]]);
    }
}
void solve()
{
    ans=1999;
    int posx,posy;
    for(register int i=1;i<=5;i++)
    {
        for(register int j=1;j<=5;j++)
        {
            cin>>mapp[i][j];
            if(mapp[i][j]=='*')
            {
                posx=i;
                posy=j;
            }
        }
    }
    dfs(0,1999,posx,posy);
    printf("%d\n",ans==1999?-1:ans);
    return;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        solve();
    }
}

版权属于：Noire02

本文链接：https://noire02.moe/archives/astar.html

北京第三区交通委提醒您：复制千万条，版权第一条。转载删出处，博主两行泪。