网站基础建设和维护,大型门户网站制作教程,网站不符合个人备案性质,来宾建设工程造价网站IDA*#xff1a;非常好用的搜索#xff0c;可以解决很多深度浅#xff0c;但是规模大的搜索问题。 估价函数设计思路#xff1a;观察一步最多能向答案靠近多少。 埃及分数 题目大意#xff1a; 给出一个分数#xff0c;由分子a 和分母b 构成#xff0c;现在要你分解成一…IDA*非常好用的搜索可以解决很多深度浅但是规模大的搜索问题。 估价函数设计思路观察一步最多能向答案靠近多少。 埃及分数 题目大意 给出一个分数由分子a 和分母b 构成现在要你分解成一系列互不相同的单位分数形如1/a即分子为1要求分解成的单位分数数量越少越好如果数量一样最小的那个单位分数越大越好。 如 19/45 1/3 1/12 1/180; 19/45 1/5 1/6 1/18; 以上两种分解方法都要3个单位分数但下面一个的最小单位分数1/18比上一个1/180大所以第二个更优。 题解dfs直接搜爆炸因为深度无限。 bfs爆炸空间不行。 所以采用有深度限制的并且不耗费空间的迭代加深搜索。 深度即分数的个数。 配合一下A*思想。 剪枝 1.每次一步到达小于剩余分数的最小分母。 return b/a1 2.如果当前可以选择的分数已经是最大的*剩下的步数剩下的分数return A*思想 3.如果只剩最后一步直接判断能否取到。 对于不能取的处理开一个数组记录。1000都可以取的。 分数运算手推式子。注意约分 #includebits/stdc.h
using namespace std;
typedef long long ll;
const int N10005;
ll a,b;
int k,T;
bool fl;
ll ans[N];
ll mem[N];
bool no[N];
int dp;
ll getfirst(ll a,ll b){return b/a1;
}
bool cmp1(ll s1,ll m1,ll s2,ll m2){//s1/m1 s2/m2 ?return (ll)s1*m2(ll)m1*s2;
}
bool cmp2(ll s1,ll m1,ll s2,ll m2){//s1/m1 s2/m2 ?return (ll)s1*m2(ll)m1*s2;
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;
}
void sub(ll s1,ll m1,ll s2,ll m2){s1s1*m2-s2*m1;m1m1*m2;ll ggcd(s1,m1);s1/g;m1/g;
}
bool better(){for(int idp;idp;i--){if(mem[i]!ans[i]){//coutmem[i] ans[i]endl; return (ans[i]0)||(mem[i]ans[i]);} } return false;
}
void dfs(int now,ll lim,ll rs,ll rm){//if(dp4) coutnow lim rs rmendl;if(nowdp){if(rs1){if(rmlim) return;//if(rm1000no[rm]) return;fltrue;//cout ok endl;mem[dp]rm;if(better()){///coutbetter endl;for(int i1;idp;i){//coutmem[i] ;ans[i]mem[i];}//coutendl;}mem[dp]0;}return;}limmax(lim,getfirst(rs,rm));for(int ilim;;i){if(cmp1(rs,rm,(dp-now1),i)) return;if(cmp2(rs,rm,1,i)){ll hsrs,hmrm;sub(hs,hm,1,i);mem[now]i;dfs(now1,i1,hs,hm);mem[now]0;}}
}
int main(){scanf(%lld%lld,a,b);int t;for(int i1;ik;i){scanf(%d,t);no[t]1;}flfalse;while(!fl){dp;//if(dp4) coutdpendl;dfs(1,2,(ll)a,(ll)b);}for(int i1;idp;i){printf(%lld ,ans[i]);}return 0;
} View Code The Rotation Game 每次8种选择吃不消。 迭代加深直接做。 A*估价中间8个数最多的那一个一次转动最多多一个。如果中间的8个最多的那一个和8的差距比剩余步数多return 代码 #includecstdio
#includecstring
#includealgorithm
using namespace std;
typedef long long ll;
const int N9;
int mp[N][N];
int st[N][N];
char sta[10005],top;
char ans[10005],sum;
int dp,num;
bool fl;
int cnt[4];
int fan[9]{0,6,5,8,7,2,1,4,3};
int fin(){cnt[1]cnt[2]cnt[3]0;for(int i3;i5;i)for(int j3;j5;j)cnt[mp[i][j]];if(cnt[1]8) return 1;if(cnt[2]8) return 2;if(cnt[3]8) return 3;
}
int che(){cnt[1]cnt[2]cnt[3]0;for(int i3;i5;i){for(int j3;j5;j){cnt[mp[i][j]];}}int bigmax(cnt[1],max(cnt[2],cnt[3]));return 8-big;
}
void mvh(int d){if(d3){int tmpmp[3][7];for(int i7;i2;i--) mp[3][i]mp[3][i-1];mp[3][1]tmp;}else if(d4){int tmpmp[5][7];for(int i7;i2;i--) mp[5][i]mp[5][i-1];mp[5][1]tmp; }else if(d7){int tmpmp[5][1];for(int i1;i6;i) mp[5][i]mp[5][i1];mp[5][7]tmp;}else{int tmpmp[3][1];for(int i1;i6;i) mp[3][i]mp[3][i1];mp[3][7]tmp;}
}
void mvz(int d){if(d1){int tmpmp[1][3];for(int i1;i6;i) mp[i][3]mp[i1][3];mp[7][3]tmp;}else if(d2){int tmpmp[1][5];for(int i1;i6;i) mp[i][5]mp[i1][5];mp[7][5]tmp;}else if(d5){int tmpmp[7][5];for(int i7;i2;i--) mp[i][5]mp[i-1][5];mp[1][5]tmp;}else{int tmpmp[7][3];for(int i7;i2;i--) mp[i][3]mp[i-1][3];mp[1][3]tmp;}
}
bool cmp(){for(int i1;idp;i){if(sta[i]ans[i]) return true;if(sta[i]ans[i]) return false;}return false;
}
void dfs(int now,int las){if(che()dp-now1) return;if(nowdp1){if(che()0){if(!fl){memcpy(ans,sta,sizeof sta);numfin();}else if(cmp()){memcpy(ans,sta,sizeof sta);numfin();}fltrue;}return;}for(int i1;i8;i){if(ifan[las]) continue;if((i-1)%41) mvh(i);else mvz(i);sta[top]i-1A;dfs(now1,i);sta[top--] ;if((fan[i]-1)%41) mvh(fan[i]);else mvz(fan[i]);}
}
void clear(){dp0;flfalse;
}
int main(){while(1){clear();scanf(%d,st[1][3]);//coutaa endl;if(st[1][3]0) break;scanf(%d,st[1][5]);scanf(%d%d,st[2][3],st[2][5]);for(int i1;i7;i) scanf(%d,st[3][i]);scanf(%d%d,st[4][3],st[4][5]);for(int i1;i7;i) scanf(%d,st[5][i]);scanf(%d%d,st[6][3],st[6][5]);scanf(%d%d,st[7][3],st[7][5]);memcpy(mp,st,sizeof st);if(che()0){printf(No moves needed\n);printf(%d\n,fin());continue;}flfalse;while(!fl){dp;memcpy(mp,st,sizeof st);dfs(1,0);}printf(%s\n,ans1);printf(%d\n,num);}return 0;
} View Code 骑士精神 也许可以折半爆搜。 但是显然不够漂亮。 明显“超15步-1”就迭代加深了。 估价函数每次骑士最多归位一个。如果算上最后一步的空格可能归位2个。 所以当前和终止的差距-1大于剩余步数的话一定不行。 代码 #includebits/stdc.h
using namespace std;
typedef long long ll;
const int N6;
int T;
char st[6][6];
int dp;
bool fl;
int nd[6][6]{{0,0,0,0,0,0},{0,1,1,1,1,1},{0,0,1,1,1,1},{0,0,0,2,1,1},{0,0,0,0,0,1}, {0,0,0,0,0,0}
};
int mp[6][6];
int mv[8][2]{{-1,2},{-1,-2},{-2,1},{-2,-1},{1,2},{1,-2},{2,-1},{2,1}};
int che(int re){int dif0;for(int i1;i5;i){for(int j1;j5;j){dif(mp[i][j]!nd[i][j]);}}if(dif0) return 2;return dp-re1dif-1;
}
void dfs(int now,int x,int y){if(!che(now)) return;if(fl) return;if(nowdp1){if(che(now)2) {fltrue;return;}}for(int i0;i8;i){int dxxmv[i][0],dyymv[i][1];if(dx1||dx5) continue;if(dy1||dy5) continue;swap(mp[x][y],mp[dx][dy]);dfs(now1,dx,dy);swap(mp[x][y],mp[dx][dy]);}
}
void clear(){flfalse;dp0;
}
int main(){scanf(%d,T);while(T--){clear();int sx,sy;for(int i1;i5;i){scanf(%s,st[i]1);for(int j1;j5;j){if(isdigit(st[i][j]))mp[i][j]st[i][j]-0;else {mp[i][j]2;sxi,syj;}}}flfalse;for(dp0;dp15;dp){dfs(1,sx,sy);if(fl) break;}if(fl) printf(%d\n,dp);else printf(-1\n);}return 0;
} View Code 转载于:https://www.cnblogs.com/Miracevin/p/9780322.html
