头像

ieqefcr


访客:1190

离线:10个月前


分享 IDA*

ieqefcr
11个月前

IDA星其实就是迭代深搜版的A星,每个状态下,如果当前深度加上估计函数的值大于当前限制的深度,那么就返回。这样相比A星的编程难度要小一点,在一些地方效率高于A星。

例题:排书

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define per(i,j,k) for(int i=j;i>=k;i--)
typedef long long ll;
using namespace std;

template<typename T>void in(T &x) {
    char ch = getchar();bool flag = 0;x = 0;
    while(ch < '0' || ch > '9') flag |= (ch == '-'), ch = getchar();
    while(ch <= '9' && ch >= '0') x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
    if(flag) x = -x;return ;
}

int n,limit ;

bool IDA_Star(int dep,int a[16]){
    int tot=0;
    if(dep>limit) return 0;
    rep(i,1,n-1)
        if(a[i+1]!=a[i]+1) tot++;
    if(a[n]!=n) tot++;
//  printf("%d\n%tot",dep,tot);
    if(!tot) return 1;
    int b[16];
    tot=(tot-1)/3+1;
    if(dep+tot>limit) return 0;
    rep(i,1,n-1){
        rep(j,1,n-i+1)   //选择位置的开头 
            rep(k,1,j-1){   //只能往前放 
                int num=0;
                rep(q,1,k-1) b[++num]=a[q];
                rep(q,j,j+i-1) b[++num]=a[q];
                rep(q,k,j-1) b[++num]=a[q];
                rep(q,j+i,n) b[++num]=a[q];
                if(IDA_Star(dep+1,b)) return 1;
            }
    }
    return 0;
}

void solve(){
    in(n);
    int g[16];
    rep(i,1,n) in(g[i]);
    for(limit=0;limit<=4;limit++)
        if(IDA_Star(0,g)) {
            printf("%d\n",limit);
            return ;
        }
    printf("5 or more\n");
}

int main(){
    int T;
    in(T);
    while(T--)solve();
    return 0;
}



ieqefcr
11个月前

A*算法就是加了估价函数求最短路,每次从堆中取出 dis[i]+g[i]最小的那个节点,其中g[i]是i到目标节点的估计距离,这个估计距离不能比实际距离大。
这样可以避免一种情况:当前节点dis最小,但是实际上到达目标时花费较大,这样就增加了无用操作。
有许多例子,比如网格图中估价函数可以是曼哈顿距离。

例题:

K短路

代码:

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define per(i,j,k) for(int i=j;i>=k;i--)
typedef long long ll;
using namespace std;
template<typename T>void in(T &x) {
    char ch = getchar();bool flag = 0;x = 0;
    while(ch < '0' || ch > '9') flag |= (ch == '-'), ch = getchar();
    while(ch <= '9' && ch >= '0') x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
    if(flag) x = -x;return ;
}
typedef pair<int,int> node;
#define maxn 1010
#define maxm 100010
struct edge{
    int v,nxt,c;
};
int k,s,t,n,m;
int g[maxn];

namespace spfa{
    int head[maxn];
    edge e[maxm];
    bool vis[maxn],inq[maxn];
    queue<int> q;
    void add(int u,int v,int t){
        e[++head[0]]={v,head[u],t};head[u]=head[0];
        return ;
    }
    void solve(){
        g[t] = 0;vis[t]=inq[t]=1;
        q.push(t);
        while( !q.empty() ) {
            int x = q.front();
            q.pop();
            inq[x]=0;
            for( int i = head[x]; i ; i = e[i].nxt ) {
                int y = e[i].v;
                if( vis[y] == 0 || g[y] > g[x] + e[i].c ) {
                    g[y]=g[x]+e[i].c;
                    vis[y]=1;
                    if(inq[y] == 0 )
                        q.push(y),inq[y]=1;
                }
            }
        }
        return ;
    }
}

namespace dij{
    edge e[maxm];
    int head[maxn],tim[maxn];
    priority_queue <node,vector<node>,greater<node> > q;
    void add(int u,int v,int t){e[++head[0]]={v,head[u],t};head[u]=head[0];return ;}

    void solve(){
        q.push( (node) {g[s],s} );
        while( q.size() ) {
            int x = q.top().second,dist=q.top().first-g[x];
            q.pop();
            tim[x]++;
            if(tim[t]==k){
                printf("%d",dist);
                return ;
            }
            for( int i = head[x]; i; i = e[i].nxt ) {
                int y = e[i].v;
                if(tim[y]!=k)
                    q.push(node{dist+e[i].c+g[y],y});
            }
        }
        printf("-1");
        return ;
    }
}

void input(){
    in(n);in(m);
    for(int a,b,l,i=1;i<=m;i++){
        in(a);in(b);in(l);
        spfa::add(b,a,l);
        dij::add(a,b,l);
    }
    in(s);in(t);in(k);
    if(s==t){
        k++;
    } 
}

int main(){
    input();
    spfa::solve();
    dij::solve();
    return 0;
}


分享 快读

ieqefcr
11个月前

快读

#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define per(i,j,k) for(int i=j;i>=k;i--)
typedef long long ll;

template<typename T>void in(T &x) {
    char ch = getchar();bool flag = 0;x = 0;
    while(ch < '0' || ch > '9') flag |= (ch == '-'), ch = getchar();
    while(ch <= '9' && ch >= '0') x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
    if(flag) x = -x;return ;
}
#define maxn 100010
struct edge{
    int v,nxt,t;
}e[maxn<<1];
int head[maxn];
void add(int u,int v,int t){e[++head[0]]={v,head[u],t};head[u]=head[0];}

int main(){

}