本文主要是介绍十滴水 java_[Drops 十滴水] 强大的搜索(中),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
{
我们用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 constm=20;2 dx:array[1..4]oflongint=(1,0,-1,0);3 dy:array[1..4]oflongint=(0,1,0,-1);4 varansx,ansy:array[1..m]oflongint;5 ansc:array[1..m,1..6,1..6]oflongint;6 x,y,d,p:array[1..1000]oflongint;7 c:array[1..6,1..6]oflongint;8 bool,flag:boolean;9 i,j,n:longint;10 functionh:longint;11 vari,j,k,t:longint;12 begin13 t:=0;14 fori:=1to6do15 begin16 k:=0;17 forj:=1to6do18 ifc[i,j]>019 thenbegin20 inc(k);21 t:=t+5-c[i,j];22 end;23 ifk>1thent:=t-k-k+3;24 end;25 forj:=1to6do26 begin27 k:=0;28 fori:=1to6do29 ifc[i,j]>0theninc(k);30 ifk>1thent:=t-k-k+3;31 end;32 ift<0thenh:=0elseh:=t;33 end;34 proceduredfs(dep:longint);35 vari,j,k,l,o,t,tt,tx,ty:longint;36 b,f:array[1..6,1..6]oflongint;37 flag,bool:boolean;38 begin39 t:=1;//t:=h;40 ifdep+t-1>nthenexit;41 fori:=1to6do42 forj:=1to6do43 ifc[i,j]>2thenbegin44 move(c,b,sizeof(b));45 inc(c[i,j]);46 ifc[i,j]=547 thenbegin48 c[i,j]:=0;49 tt:=0;50 fork:=1to4do51 begin52 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 whileflagdo58 begin59 t:=tt;60 bool:=true;61 fillchar(f,sizeof(f),0);62 fork:=1totdo63 ifp[k]=0thenbegin64 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 thenbegin69 p[k]:=1;70 continue;71 end;72 if(odd(x[k])xor(odd(y[k])))73 thenbegin74 tx:=x[k]+dx[d[k]]+1;75 ty:=y[k]+dy[d[k]]+1;76 ifc[tx shr1,ty shr1]>077 thenbegin78 f[tx shr1,ty shr1]:=1;79 p[k]:=1;80 inc(c[tx shr1,ty shr1]);81 ifc[tx shr1,ty shr1]=582 thenbegin83 c[tx shr1,ty shr1]:=0;84 forl:=1to4do85 begin86 inc(tt);87 x[tt]:=tx-1; y[tt]:=ty-1;88 d[tt]:=l; p[tt]:=0;89 end;90 end;91 end92 elseiff[tx shr1,ty shr1]=193 thenp[k]:=1;94 end;95 end;96 flag:=notbool;97 end;98 end;99 flag:=true;100 fork:=1to6do101 forl:=1to6do102 flag:=flagand(c[k,l]=0);103 ifflag104 thenbegin105 fork:=1todep-1do106 begin107 writeln(ansx[k],'',ansy[k]);108 forl:=1to6do109 begin110 foro:=1to5do111 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 begin126 assign(input,'drop.in'); reset(input);127 assign(output,'drop.out'); rewrite(output);128 {randomize;129 if random(9999)=0130 then begin131 writeln('WARNING:LOW LOW RP...');132 writeln('Tips:Please do not zhuang B');133 close(input); close(output);134 halt;135 end;}136 fori:=1to6do137 forj:=1to6do138 read(c[i,j]);139 n:=0;140 whilen
下一篇介绍一个比较麻烦的游戏 bloxorz
极力推荐!
我用的算法么 下次说
BOB HAN原创 转载请注明出处
这篇关于十滴水 java_[Drops 十滴水] 强大的搜索(中)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!