IDA*

IDA*

A* 和 IDA* 听起来高大上

简单来说就是搜索的一个优化,通过一个估值函数让搜索不往不必要的地方发展

A*是用在BFS上的

IDA*是用在DFS上的

A*=优先队列+估价函数

IDA=迭代加深+估价函数

如果当前深度+估计还要的深度>限制深度 那就直接return 了

估价函数要区好,要尽量接近实际深度且不超过实际深度

迭代加深

例题 埃及分数

描述

在古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。对于一个分数a/b,表示方法有很多种，但是哪种最好呢？首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。

如：19/45=1/3 + 1/12 + 1/180 19/45=1/3 + 1/15 + 1/45 19/45=1/3 + 1/18 + 1/30, 19/45=1/4 + 1/6 + 1/180 19/45=1/5 + 1/6 + 1/18.  最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。

给出a,b(0计算最好的表达方式。

输入：a b 输出：若干个数，自小到大排列，依次是单位分数的分母。

样例1

样例输入1

19 45

样例输出1

5 6 18

1. 1/n=1/(n+1)+1/n*(n+1) (小学奥数)

所以对于答案,深度是无法得知的,因为可以永远拆分下去

就是说,你不知道答案由多少个分数组成

2.题目要求用最少的个数来表示分数

这对应搜索树中最小的层数

这也对应了迭代加深的条件

1.它搜索时可能会达到极大的深度，而这样的答案是没用且费时的

2.它是个最优解问题，最优的答案深度最小

于是我们可以限制搜索层数,本题也就是限制分数的个数

我们从1开始枚举深度,当有解时就直接退出(因为一定是最优解)

本题,深度为1,2都无解,当为3时,最优解为5 6 18

当同一深度有多个解时,判断一下就好了

当然,当深度为d时,会把1-d-1层重新搜索一遍

但对于第d层新增的节点,1-d-1层的就显得微不足道了

我们要保证后面搜的分母比前面的都大,不然会乱int get_ans(int d,int from,int aa,int bb){//层数,最小的分母从from开始,当前分子,分母 if(d==maxd){//maxd 为限制的层数 if(bb%aa) return false;//最后剩下的分数要满足分子为1 v[d]=bb/aa;//v[i]是当前答案,ans是最终答案 if(better(d)){//判断同一层的最优解 for(int i=0;i<=d;i++) ans[i]=v[i]; } return true; } from=max(from,bb/aa+1);//1/cbb/aa,c>=bb/aa+1 int ok=0; for(int i=from;;i++){//从from开始向上枚举 if(aa*i>=bb*(maxd-d+1)) break; //aa/bb>=i/(maxd-d+1)后面分母一定比i大,如果全是i都不行肯定不行 v[d]=i;//记录答案 int b2=bb*i,a2=aa*i-bb,g=gcd(a,b);//通分并约分 if(get_ans(d+1,i+1,a2/g,b2/g)) ok=1; } return ok;}

估价函数

对未来至少的层数做一个保守的估计

例题

输入格式：

第一行有一个正整数T(T<=10)，表示一共有N组数据。接下来有T个5×5的矩阵，0表示白色骑士，1表示黑色骑士，*表示空位。两组数据之间没有空行。

输出格式：

对于每组数据都输出一行。如果能在15步以内（包括15步）到达目标状态，则输出步数，否则输出－1。

输入样例#1：

2 10110 01*11 10111 01001 00000 01011 110*1 01110 01010 00100

输出样例#1：

7 -1

1.未知多少层

2.寻找最优解

3.层数只用枚举到15

4.考虑估价函数,如果当前状态与最终状态的不匹配的格子有x个,那么至少需要x-1次复原

于是很容易写出,h为估价函数

int h(){ int ret=0; for(int i=0;i<5;i++) for(int j=0;j<5;j++) if(Map[i][j]!=goal[i][j]) ret++; return ret;}if(h()+d-1>maxd) return 0;

代码也很简单了

#includeusing namespace std;int goal[5][5]={{1,1,1,1,1},{0,1,1,1,1},{0,0,2,1,1},{0,0,0,0,1},{0,0,0,0,0}};int Map[5][5],T,pd;int fx[8]={1,-1,2,-2,1,-1,2,-2};int fy[8]={2,2,-1,-1,-2,-2,1,1};int stx,sty;int h(){ int ret=0; for(int i=0;i<5;i++) for(int j=0;j<5;j++) if(Map[i][j]!=goal[i][j]) ret++; return ret;}bool IDA(int maxd,int d,int x,int y){ if(!h()) return 1; if(h()+d-1>maxd) return 0; for(int i=0;i<8;i++){ int x1=x+fx[i]; int y1=y+fy[i]; if(x1<0||x1>4||y1<0||y1>4) continue; swap(Map[x1][y1],Map[x][y]); if(IDA(maxd,d+1,x1,y1)) return 1; swap(Map[x1][y1],Map[x][y]); } return 0;} int main(){ //freopen("1.in","r",stdin); cin>>T; while(T--){ pd=0; for(int i=0;i<5;i++){ char s[5];scanf("%s",s); for(int j=0;j<5;j++){ if(s[j]-'0'==0) Map[i][j]=0; if(s[j]-'0'==1) Map[i][j]=1; if(s[j]=='*') Map[i][j]=2,stx=i,sty=j; } } for(int i=1;i<=15;i++) if(IDA(i,0,stx,sty)){pd=i;break;} if(pd) cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。