题目大意：给定初始的x，可以通过乘法将其变为x^2，再变为x^4，x^8，x^16，x^32，也可以用除法，x^31 = x^32 / x，但是操作数必须是已经计算出来的数，给定一个指数，要求得到这个指数的最小步数。比如31输出6（1 2 4 8 16 32 31）.

想错了很多次……求最优路径问题嘛，就是ID-DFS or BFS。事实证明两种方法确实都可以。一般当时间宽裕空间紧张时选ID-DFS；当时间紧而空间宽裕时选BFS。可是因为我的姿势丑……BFS加了各种优化才勉强2s过，ID-DFS显然各种吃紧了……囧。

回到题目。首先一个直观的想法就是BFS，并且因为我们每次扩展状态时都要依据前面过程中的数，所以需要用一个数组记录下来当前状态的前面的状态。这样我们BFS队列里存的就是一个结构体，包括当前状态的指数，当前步数，和存与当前状态相关的前面状态的数组。然后为了减少状态要去重，队列中只保存得到某个数花费步数最短的一种状态。

但是结果953怎么算都是13……跑到Discuss里看了下结果：(1 2 4 8 7 15 30 60 120 240 480 473 953)，然后我们对473做一次BFS打印一下结果：(1 2 4 8 16 32 31 63 126 252 504 473)。于是我们发现了问题所在：得到某个数花费最少步数的状态可能不同，而不同的状态对后面数的影响是不同的，所以我们需要把某数步数相同且最短的状态都存起来。

（但我还有一个疑问是为什么步数更长的状态不会使后面有更好的结果……囧……反正数据没出现这种情况……）

但是因为我的姿势丑……T_T……这样还是TLE……看了一位大牛的博客又加了一个优化：限制某个数的状态在队列中只能出现limit次(我设的10)，虽然确实通过了……但是还是不会证明正确性……T_T……

PS：为什么我的姿势这么丑……T^T……

POJ 3134 - Power Calculus 迭代加深搜索(DFSID)

分类：搜索2013-07-21
19:22 106人阅读评论(0) 收藏举报

最开始想动态规划...想了好久想不通.然后试着写BFS..各种超时....参考大牛的提示..DFSID把它A掉了...效率很高啊...而且代码写起来思路也很清晰...

Program:

[cpp]view

 plaincopy

#include<iostream>  

#include<stdio.h>  

#include<cmath>  

#include<queue>  

#include<stack>  

#include<algorithm>  

#include<string.h>  

#define ll long long  

#define oo 10000007  

using namespace std;       

int way[1005],num;   

bool DFSID(int x,int step)  

{   

      int i;  

      if (num>step) return false;  

      if (way[num]==x) return true;  

      if (way[num]<<(step-num)  < x) return false; // 强力剪枝   

      for (i=0;i<=num;i++)  

      {  

             num++;  

             way[num]=way[num-1]+way[i];  

             if (way[num]<=10000 && DFSID(x,step)) return true;   

             way[num]=way[num-1]-way[i];    

             if (way[num]>0 && DFSID(x,step)) return true;             

             num--;  

      }   

      return false;      

}  

int main()  

{    

      int i,x;  

      freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);        

      while (~scanf("%d",&x) && x)   

      {  

            for (i=0;;i++)  

            {  

                 way[num=0]=1;  

                 if (DFSID(x,i)) break;  

            }  

            printf("%d\n",i);  

      }  

      return 0;  

}

{

我们用BFS解决了华容道

事实上也有比较难搜的puzzle

比如十滴水 Drops

我们需要选用其他方法

}

十滴水是一个相当简约耐玩的小游戏

建议写程序之前好好玩玩

争取发现一个牛B的启发函数

(至少我没找到好的只能裸搜之有了牛B的启发函数会很爽下面会提到)

状态空间相当巨大

如果把加入一滴水算作一步

每个状态可以生成36种子状态

　　当dep=4时节点数是160w

　　当dep=5时节点数是6000w

　　当dep=6时节点数是20000w

BFS不能承受(自然的 A*更没希望)

DFS也不适合(要求最优解)

我们选用迭代加深搜索(Iterative Deepening ) 简称ID算法

迭代加深搜索兼有BFS与DFS的优点

基本的思想就是给dfs限定深度每次只搜到选定深度

将选定深度从1-maxdep枚举一遍每次都dfs一次即可

空间消耗很小 就是DFS的空间消耗不会像BFS一样爆空间

也能像BFS一样一层一层搜索 不会像DFS一样死钻一个子树

不过每次都要从头开始DFS 似乎会浪费时间

由于搜索量是指数级的其实每次DFS开始之前的DFS的搜索量不算什么的

其实就是乘了个常数而已而且这个常数不大于2

当然ID算法也可以和A*算法结合就是IDA*算法

关键就是设计一个好的启发函数可惜我没设计好就采用了裸的ID算法效率可能不高

接下来讲讲我这不怎么样的迭代加深搜索

确定好了搜索的方法之后我们就要考虑搜索的具体需求了

首先是如何表示一个状态

　　由于是ID算法我们不需要节约空间

　　用6*6的矩阵存下即可

　　元素就是0-4的数代表泡泡的大小

其次是如何判断得到解

　　很简单循环判断是否全都是0

比较麻烦的就是生成子状态

　　对于当前状态枚举到要对(i,j)泡泡加入一滴水

　　如果

　　　　加入后小于等于4 就不用继续讨论了直接得到一个状态

　　　　否则这点水就爆裂了产生4个向4个方向的小水滴匀速直线运动

　　　　　　然后就得处理这种情况因为爆裂一个会带来连锁

　　　　　　我用一张表x[] y[] d[] p[]来存储所有飞溅的小水滴

　　　　　　具体操作就是一遍一遍的扫描这个表直到不能更新为止

　　　　　　　　x[] y[]记录坐标 d[]记录方向

　　　　　　　　p[]是用来记录当前水滴是否还存在 因为水滴撞墙或是撞到另一个大水泡就会消失

　　　　　　　　每撞开一个大水泡就要把生成的水滴加到表里

　　　　　　　　每次扫描就相当于过了1单位时间水滴同时移动了一步这样保证了同步性

　　　　　　　　为了保证绝对同步 刚爆开的水滴在本次扫描中不能移动

　　　　　　如果水滴全没了即p[]全是1 循环停止

　　　　　　　　需要注意以下几点

　　　　　　　　　　半格半格移动水滴

　　　　　　　　　　　　因为判断撞到泡泡是根据是否走到泡泡的所在格的边界判断的

　　　　　　　　　　　　而每个水滴又是从格子中间开始的

　　　　　　　　　　　2个水滴同时撞到一个泡泡就会同时消失 不管泡泡是多大我用f[]数组处理的

　　扫描完毕就得到了新的状态按照一般DFS的步骤即可

输入输出用上图为例

输入 Drops.in

0 2 1 2 1 1
3 4 3 3 3 1
3 4 2 0 4 0
3 3 1 0 2 3
2 3 1 2 2 3
0 4 0 2 0 4

输出 Drops.out

2 4
0 2 1 2 1 1
3 4 3 4 3 1
3 4 2 0 4 0
3 3 1 0 2 3
2 3 1 2 2 3
0 4 0 2 0 4

2 4
0 2 1 3 1 1
3 4 4 0 4 1
3 4 2 0 4 0
3 3 1 0 2 3
2 3 1 3 2 3
0 4 0 2 0 4

3 5
0 0 4 3 2 2
0 0 0 0 0 0
0 0 0 0 0 0
0 0 3 0 4 4
4 0 2 3 2 3
0 0 0 3 0 4

4 5
0 0 0 4 3 3
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
4 0 4 3 3 4
0 0 0 3 0 4

5 3

我用我的程序刷Drops2 刷满了一试管的水

嘿嘿

看来ID算法还是不错的

不过相应的步数达到6步使用的时间就达到1秒了 7步以上出解就困难了

希望有牛人能告诉我一个牛B的启发函数哦

代码~

  1 const    m=20;
  2     dx:array[1..4]of longint=(1,0,-1,0);
  3     dy:array[1..4]of longint=(0,1,0,-1);
  4  var    ansx,ansy:array[1..m]of longint;
  5     ansc:array[1..m,1..6,1..6]of longint;
  6     x,y,d,p:array[1..1000]of longint;
  7     c:array[1..6,1..6]of longint;
  8     bool,flag:boolean;
  9     i,j,n:longint;
 10 function h:longint;
 11 var    i,j,k,t:longint;
 12 begin
 13 t:=0;
 14 for i:=1 to 6 do
 15     begin
 16     k:=0;
 17     for j:=1 to 6 do
 18         if c[i,j]>0
 19             then begin
 20             inc(k);
 21             t:=t+5-c[i,j];
 22             end;
 23     if k>1 then t:=t-k-k+3;
 24     end;
 25 for j:=1 to 6 do
 26     begin
 27     k:=0;
 28     for i:=1 to 6 do
 29         if c[i,j]>0 then inc(k);
 30     if k>1 then t:=t-k-k+3;
 31     end;
 32 if t<0 then h:=0 else h:=t;
 33 end;
 34 procedure dfs(dep:longint);
 35 var    i,j,k,l,o,t,tt,tx,ty:longint;
 36     b,f:array[1..6,1..6]of longint;
 37     flag,bool:boolean;
 38 begin
 39 t:=1; //t:=h;
 40 if dep+t-1>n then exit;
 41 for i:=1 to 6 do
 42     for j:=1 to 6 do
 43         if c[i,j]>2 then begin
 44         move(c,b,sizeof(b));
 45         inc(c[i,j]);
 46         if c[i,j]=5
 47             then begin
 48             c[i,j]:=0;
 49             tt:=0;
 50             for k:=1 to 4 do
 51                 begin
 52                 inc(tt);
 53                 x[tt]:=2*i-1; y[tt]:=2*j-1;
 54                 d[tt]:=k; p[tt]:=0;
 55                 end;
 56             flag:=true;
 57             while flag do
 58                 begin
 59                 t:=tt;
 60                 bool:=true;
 61                 fillchar(f,sizeof(f),0);
 62                 for k:=1 to t do
 63                     if p[k]=0 then begin
 64                     bool:=false;
 65                     x[k]:=x[k]+dx[d[k]];
 66                     y[k]:=y[k]+dy[d[k]];
 67                     if (x[k]<=0)or(x[k]>=12)or(y[k]<=0)or(y[k]>=12)
 68                         then begin
 69                         p[k]:=1;
 70                         continue;
 71                         end;
 72                     if (odd(x[k])xor(odd(y[k])))
 73                         then begin
 74                         tx:=x[k]+dx[d[k]]+1;
 75                         ty:=y[k]+dy[d[k]]+1;
 76                         if c[tx shr 1,ty shr 1]>0
 77                             then begin
 78                             f[tx shr 1,ty shr 1]:=1;
 79                             p[k]:=1;
 80                             inc(c[tx shr 1,ty shr 1]);
 81                             if c[tx shr 1,ty shr 1]=5
 82                                 then begin
 83                                 c[tx shr 1,ty shr 1]:=0;
 84                                 for l:=1 to 4 do
 85                                     begin
 86                                     inc(tt);
 87                                     x[tt]:=tx-1; y[tt]:=ty-1;
 88                                     d[tt]:=l; p[tt]:=0;
 89                                     end;
 90                                 end;
 91                             end
 92                             else if f[tx shr 1,ty shr 1]=1
 93                                 then p[k]:=1;
 94                         end;
 95                     end;
 96                 flag:=not bool;
 97                 end;
 98             end;
 99         flag:=true;
100         for k:=1 to 6 do
101             for l:=1 to 6 do
102                 flag:=flag and(c[k,l]=0);
103         if flag
104             then begin
105             for k:=1 to dep-1 do
106                 begin
107                 writeln(ansx[k],' ',ansy[k]);
108                 for l:=1 to 6 do
109                     begin
110                     for o:=1 to 5 do
111                         write(ansc[k,l,o],' ');
112                     writeln(ansc[k,l,6]);
113                     end;
114                 end;
115             writeln(i,' ',j);
116             close(input); close(output);
117             halt;
118             end;
119         ansx[dep]:=i; ansy[dep]:=j;
120         move(c,ansc[dep],sizeof(c));
121         dfs(dep+1);
122         move(b,c,sizeof(b));
123         end;
124 end;
125 begin
126 assign(input,'drop.in'); reset(input);
127 assign(output,'drop.out'); rewrite(output);
128 {randomize;
129 if random(9999)=0
130     then begin
131     writeln('WARNING:LOW LOW RP...');
132     writeln('Tips:Please do not zhuang B');
133     close(input); close(output);
134     halt;
135     end;}
136 for i:=1 to 6 do
137     for j:=1 to 6 do
138         read(c[i,j]);
139 n:=0;
140 while n<m do
141     begin
142     inc(n);
143     dfs(1);
144     end;
145 writeln('WARNING:LOW LOW RP...');
146 writeln('Tips:Please do not zhuang B');
147 close(input); close(output);
148 end.
149

下一篇介绍一个比较麻烦的游戏 bloxorz

极力推荐!

我用的算法么下次说

埃及分数,迭代加深搜索

分类：搜索2013-02-04
17:21 80人阅读评论(0) 收藏举报

在古埃及，人们使用单位分数的和(形如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〈1000),编程计算最好的表达方式。

利用枚举深度上限d，每次只考虑深度不超过d的结点。

利用深度上限来剪枝，当当前的分数和为sum，此时拓展的分数为1/val，那么我们至少还需要(inval - sum)/(1/val)个分数才能使和为给定值，

那么超过了此时限定深度的结点则不必考虑，depth - d为此时剩余需要考虑的层数，inval - sum为剩余所需和的大小，（inval - sum） / （depth - d）则为每个剩余分数的值（此时将这些值视为相等）,因为我们是使分母逐渐扩大的，则相应的值应该越来越小，所以（inval - sum） / （depth - d）的倒数就是此时最大可以被接受的分母，不然就会超过限定深度。

[cpp]view

 plaincopy

#include"iostream"  

using namespace std;  

const double error = 1e-7;  

int depth = 1;  

double inval;  

_inline double mabs(double x){  

    return x > 0 ? x :(-x);  

}  

bool dfs(int d,int val,double sum){  

    if(d == depth){  

        if(mabs(sum - inval) < error)return true;  

        return false;  

    }  

    int max = (int)((depth - d)/(inval - sum));            //构造剪枝条件(此处max为最大可以取的val值，即分母)  

    for( ; val <= max ; val ++){  

        if(dfs(d + 1,val + 1,sum + (1.0 / val))){  

            printf(" + 1/ %d ",val);  

            return true;  

        }  

    }  

    return false;  

}  

int main(void){  

    int a,b;  

    scanf("%d %d",&a,&b);  

    inval = (double)a/b;  

    while(dfs(0,(int)(1.0/inval) + 1,0.0) == 0){  

        depth ++;  

    }  

    return 0;  

}

迭代加深ID-DFS搜索算法

迭代加深搜索，实质上就是限定下界的深度优先搜索。即首先允许深度优先搜索K层搜索树，若没有发现可行解，再将K+1后重复以上步骤搜索，直到搜索到可行解。

迭代加深搜索算法的实现原理及基本框架

在迭代加深搜索的算法中，连续的深度优先搜索被引入，每一个深度约束逐次加1，直到搜索到目标为止。

基本框架如下：

ProcedureID-dfs(dep:integer);

Var

J:integer;

Begin

Ifdep>深度的限界thenexit;//如果搜索的深度大于限界，则返回上一层

Forj:=1tondo // 按照规则生成子结点

If子结点安全then

Begin

入栈；

If子结点是目标结点then对目标结点进行处理，退出程序

Elseid-dfs(dep+1);

退栈；

End;

Fori:=1todepmaxdo//枚举深度的限界

Begin

Id-dfs(i);

If运行超时thenbreak;

End;

迭代加深搜索算法的复杂度分析

从上述迭代加深搜索算法的实现过程和框架，我们可以看出，迭代加深搜索算法就是仿广度优先搜索的深度优先搜索。既能满足深度优先搜索的线性存储要求，又能保证发现一个最小深度的目标结点。（时间复杂度推算详见NOI导刊2010年第6期P26）

从实际应用来看，迭代加深搜索的效果比较好，并不比广度优先搜索慢很多，但是空间复杂度却与深度优先搜索相同，比广度优先搜索小很多。

迭代加深搜索算法的应用

使用搜索算法的时候，选择正确的搜索方式很重要。当有一类问题需要做广度优先搜索，但却没有足够的空间，而时间却很充裕，碰到这类问题，我们可以选择迭代加深搜索算法。

例题：POJ 2286 The Rotation Game

四、总结

一般来说，如果目标结点离根结点远，需要遍历整棵树，可以考虑使用深度优先搜索；如果目标离根结点近，或求最小步数，则考虑广度优先搜索或迭代加深搜索；若广度优先搜索存在空间不够的问题，则考虑使用迭代加深搜索。

学步园

迭代深度递归 POJ 3134 – Power Calculus 迭代加深搜索(DFSID)埃及分数,迭代加深搜索

POJ 3134 Power Calculus ★(记录状态的BFS)

POJ 3134 - Power Calculus 迭代加深搜索(DFSID)

埃及分数,迭代加深搜索

迭代加深ID-DFS搜索算法

迭代加深ID-DFS搜索算法

作者: versace9988

书签

最新文章New

本站推荐

返回首页