找回密码
 注册
Simdroid-非首页
查看: 404|回复: 6

[演示项目] 八数码的Recursive Best-First Searching(递归最优搜索)实现

[复制链接]
发表于 2009-2-25 21:55:42 | 显示全部楼层 |阅读模式 来自 山西太原
本帖最后由 FreddyMusic 于 2009-11-16 03:11 编辑

八数码的Mathematica实现。应用了Recursive Best-FirstSearching,也就是递归最优搜索。关于递归最优搜索算法请参考Nils J.Nilsson写的《人工智能:新合成》。书里面对RBFS只是简单说了一下,但是讲的非常明白。这个算法比较新颖,但却很容易理解。这本书对现有的启发式搜索算法都进行了比较全面的描述并进行了比较,当然有可能的话更应该看看书中引用的文献,不过那些文献通常要交钱……回头潜进老师的实验室上SpringerLink找找。



Black block means the empty position.
  1. ClearSystemCache[];
  2. EightEntropy[lis_List]:=Inversions[Flatten[lis]];
  3. EightEntropy2=Function[x,Plus@@Flatten@Abs@(Flatten[Position[x,#]&/@Range[9],1]-Flatten[Position[Partition[Range[9],3],#]&/@Range[9],1])];

  4. (*I use the inversion of permutation as the cost,the inversion of original state is 0,The Manhattan Distance is another option,which people said it is not satisfying,but I haven't try it.*)

  5. (*EightEntropy2 is the destance of the current position of every number to their original position,which works for ALL legal state! WAHAHAHAHA*)
  6. Swap={{p___,{9,a_,b_},s___}:>{p,{a,9,b},s},{p___,{a_,9,b_},s___}:>{p,{9,a,b},s},{p___,{a_,9,b_},s___}:>{p,{a,b,9},s},{p___,{a_,b_,9},s___}:>{p,{a,9,b},s}};

  7. Move=Join[ReplaceList[#,Swap],Transpose/@ReplaceList[Transpose[#],Swap]]&;
  8. (*Generate all possible moves.Swap can only affect horizonal triple,for vertical ones,apply swap on a transposed matrix and transpose it back.*)

  9. UpdateWeight={ent_,state_?MatrixQ,sub_}:>{Min@@First/@sub,state,sub}/;ent!=Min@@First/@sub;
  10. (*Replace all values of non-leaf node to the minimal value of its subnodes.*)

  11. ExpandBranch={ent_,state1_,{Prev___,{ent_,state2_?MatrixQ},Succ___}}:>{ent,state1,{Prev,{ent,state2,{EightEntropy2[#],#}&/@Complement[Move[state2],{state1}]},Succ}};
  12. (*Complement can eliminate the repeated state in the new generated states*)

  13. DeleteBranch={ent1_,state1_,{Prev___,{ent2_,state2_?MatrixQ,sub_},Succ___}}:>{ent1,state1,{Prev,{ent2,state2},Succ}}/;ent1!=ent2;
  14. (*Delete all subtree if the value of the node is not equal to its subnodes'*)

  15. Original=Nest[RandomChoice[Move[#]]&,Partition[Range[9],3],20];
  16. Original={EightEntropy2[#],#,Function[x,{EightEntropy2[x],x}]/@Move[#]}&[Original]//.UpdateWeight
  17. (*Initializing*)

  18. While[First[Original]!=0,Original=Original//.ExpandBranch//.UpdateWeight//.DeleteBranch//.UpdateWeight]
  19. (*work work*)

  20. Grid[Join[Partition[#,10],{Part[#,-Mod[Length[#],10];;-1]}]&[ArrayPlot/@Cases[DeleteCases[Original,{ent_/;ent!=0,state_?MatrixQ},Infinity],_?MatrixQ,Infinity]]]
  21. (*Show the path*)
复制代码

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?注册

×

评分

1

查看全部评分

发表于 2009-2-25 22:06:33 | 显示全部楼层 来自 北京海淀
Simdroid开发平台
挺羡慕你的,可以在老师的实验室里玩mathematica
回复 不支持

使用道具 举报

发表于 2009-2-26 08:36:55 | 显示全部楼层 来自 江苏无锡
本帖最后由 FreddyMusic 于 2009-2-26 10:30 编辑

Cool !Publish !

http://demonstrations.wolfram.com/participate.html
回复 不支持

使用道具 举报

发表于 2009-2-26 13:26:04 | 显示全部楼层 来自 甘肃兰州
2# waynebuaa
在老师实验室与自己的电脑上有什么很大的区别吗?
回复 不支持

使用道具 举报

发表于 2009-11-16 01:37:06 | 显示全部楼层 来自 加拿大
本帖最后由 smarten 于 2009-11-15 11:56 编辑

老师实验室的可能是8核的,推大的显示器,可以戴耳机听音乐,如果你玩得很熟,还可以开一个小窗口来看电影。如果是3屏就不得了,你可以自己想想吧。
我自己家也是双屏的(笔记本+台式机的屏幕,分辨率2560 x 800)。
我感觉现在已经要求从研究一般的问题转向giga(国内的工程已经是mega的,这个别的地方都做不了的)的问题,例如能源问题和气象问题。

最简单的梦想:如果我们能控制风,地球上大部分地方都是水包围地的,把风从海上向内陆吹,然后人工降水,这样得到的是很软的淡水(做啤酒什么都很好),而且是要什么时候有就什么时候有(JIT),那些很内陆的地方可以等到近海的地方稍微湿了以后然后再向内陆吹(到了内陆,如果没什么大风,水基本上就被固定在那儿了)。有了这个,基本上人要住哪儿就住哪儿了。要求也很高,需要有特别强的城市排水系统(现在要么觉得太干,稍微不小心就成灾了)。 然后需要精确的模拟全球的大气,真的能manipulate气流(天气),不然一些麻木的自我主张就会导致自然的惩罚,例如台风。
当然了最难的还是怎么产生风:原理上风就是从高压流向低压。一般的小风没有用,例如飞机飞行的时候螺旋桨产生的风。
创新是一个特别的元素,这样成本才低。不这样的话,现在的南水北调和水坝建设就很好了。
4# jimogsh
回复 不支持

使用道具 举报

发表于 2009-12-8 21:14:17 | 显示全部楼层 来自 陕西铜川
自己的电脑也可以是16核的、8屏的,分辨率14400*204800,就是控制不了风,只能拿鞭子在风中抽。
回复 不支持

使用道具 举报

发表于 2010-7-18 21:19:20 | 显示全部楼层 来自 安徽马鞍山
LZ 太有想象力了!虽然想象力有时能够让我们超越自己,但是不根据自然规律的想象,我想那可能只是科幻!哎,说实话,我也想有一天能有个八核三屏的计算机,可怜现在还是P4,512MB!为什么现实和理想差那么远!
回复 不支持

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|小黑屋|联系我们|仿真互动网 ( 京ICP备15048925号-7 )

GMT+8, 2024-3-28 20:36 , Processed in 0.045278 second(s), 18 queries , Gzip On, MemCache On.

Powered by Discuz! X3.5 Licensed

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表