迷宫与过河问题.ppt

《迷宫与过河问题.ppt》由会员分享，可在线阅读，更多相关《迷宫与过河问题.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、迷宫、过河、状态空间搜索迷宫、过河、状态空间搜索王磊王磊1各种迷宫234广义的迷宫5678人鬼过河小游戏9冷静 有点条理分析使用演草纸10从初始状态开始11有几种选择？（操作）12每条路径通向一个新的状态13每到一个状态，又面临新的选择14一个迷宫？状态=路口操作=通路限制条件=死胡同无形的迷宫。15如何表示状态？怎么描述当前状态？对岸人的个数：p（0、1、2、3）对岸鬼的个数：g（0、1、2、3）船的位置：b（left，rght）p,g,b/3-p,3-g 或 p,g/b,3-p,3-g 0,0/b,3,316特殊状态什么样的状态不合法？i,j/b,k,m 或i,j,b/k,m i j,且i

2、！=0或者 k m,且k！=0什么样的状态算成功？0,0/b,3,317几种算符（操作/转移函数）？所有可能的操作步骤（算符）5种：a.运1人。b.运1鬼c.运2人d.运2鬼e.运1人1鬼abcde18OK？我们来试试！找一张演草纸190,0/b,3,32,0,b/1,30,2,b/3,11,1,b/2,21,0,b/2,30,1,b/3,2200,0/b,3,32,0,b/1,30,2,b/3,11,1,b/2,20,1/b,3,21,0/b,2,31,0,b/2,30,1,b/3,2210,0/b,3,32,0,b/1,30,2,b/3,11,1,b/2,20,1/b,3,21,0/b,2

3、,31,0,b/2,30,1,b/3,22,1,b/1,20,3,b/3,01,2,b/2,1220,0/b,3,32,0,b/1,30,2,b/3,11,1,b/2,20,1/b,3,21,0/b,2,31,0,b/2,30,1,b/3,22,1,b/1,20,3,b/3,01,2,b/2,10,2/b,3,12,2,b/1,11,3,b/2,02,0/b,1,31,1/b,2,22,1/b,1,23,1,b/0,21,3,b/2,03,0/b,0,31,2/b,2,12,1/b,1,22,1,b/1,22,0/b,1,31,2,b/2,11,2,b/2,1230,0/b,3,32,0,b/

4、1,30,2,b/3,11,1,b/2,20,1/b,3,21,0/b,2,31,0,b/2,30,1,b/3,22,1,b/1,20,3,b/3,01,2,b/2,10,2/b,3,12,2,b/1,11,3,b/2,02,0/b,1,31,1/b,2,22,1/b,1,23,1,b/0,21,3,b/2,03,0/b,0,31,2/b,2,12,1/b,1,2240,0/b,3,32,0,b/1,30,2,b/3,11,1,b/2,20,1/b,3,21,0/b,2,31,0,b/2,30,1,b/3,22,1,b/1,20,3,b/3,01,2,b/2,10,2/b,3,12,2,b/1

5、,11,3,b/2,02,0/b,1,31,1/b,2,22,1/b,1,23,1,b/0,21,3,b/2,03,0/b,0,31,2/b,2,12,1/b,1,2。25深度优先搜索Bool DeepSearch（state）判断当前状态判断当前状态S：If S 是终点，return true；算法结束！For 每一条路径（操作）oi1.执行操作（前进一步）：执行操作（前进一步）：对当前状态S执行操作oi，得到新状态S。2.If S是合法状态搜索子树搜索子树S：If（DeepSearch（S）=true，return true；搜索成功！Return false；（每棵子树都无解，所以该状态

6、无解）（每棵子树都无解，所以该状态无解）26OK?270,0/b,3,32,0,b/1,30,2,b/3,10,1/b,3,21,0,b/2,30,1,b/3,21,1,b/2,21,0/b,2,3280,0/b,3,32,0,b/1,30,2,b/3,10,1/b,3,21,0,b/2,30,1,b/3,21,1,b/2,21,0/b,2,30,0/b,3,3290,0/b,3,32,0,b/1,30,2,b/3,11,1,b/2,20,1/b,3,21,0/b,2,31,0,b/2,30,1,b/3,22,1,b/1,20,3,b/3,01,2,b/2,10,2/b,3,12,2,b/1,

7、11,3,b/2,02,0/b,1,31,1/b,2,22,1/b,1,23,1,b/0,21,3,b/2,03,0/b,0,31,2/b,2,12,1/b,1,230鬼打墙？重复搜索鬼打墙？31如何避免重复状态？在路口做标记：需要有一张“迷宫地图”还没搜索，哪来的地图？对比历史状态：记录历史状态时间代价32对比历史状态？记录所有历史状态？33Memory0,0/b,3,32,0,b/1,30,2,b/3,10,1/b,3,21,0,b/2,30,1,b/3,21,1,b/2,21,0/b,2,30,0/b,3,3曾经来过吗？空间消耗？时间消耗？顺序比较所有的历史状态。34只比较当前路径上的历

8、史节点？35stack0,0/b,3,32,0,b/1,30,2,b/3,10,1/b,3,21,0,b/2,30,1,b/3,21,1,b/2,21,0/b,2,30,0/b,3,3曾经来过吗？可以避免“鬼打墙”不能避免重复36麻烦？37傻瓜一点的解决方案广度优先搜索肯定能找到解38地毯式搜索！01234567891011121314。39广度优先搜索层层推进搜索的层数不超过答案所在的层数01234567891011121314。40广度优先搜索01234567891011121314。41广度优先搜索记录下待处理的状态（节点）：0，042广度优先搜索01取第一个待处理的节点产生下一个状态（

9、子节点）并不继续搜索，只是记录下来，等待处理0，143广度优先搜索012记录下待处理的节点：0，1，244广度优先搜索012一个节点的子节点都产生了，处理完毕1，245广度优先搜索012341，2，3，446广度优先搜索012342，3，447广度优先搜索012345678910115，6，7，8，9，10，1148广度优先搜索012345678910115，6，7，8，9，10，11先进先出队列！49Memory地毯式搜索！01234567891011问题解决了？怎么找回路径？需要保存所有历史节点（保存树结构）？50看来总要存储历史状态？51走迷宫是怎么做的？一张迷宫“地图”把所有的可能到达

10、的状态（位置）全部装入了内存！随便标记52迷宫的全貌：状态空间状态=路口操作=通路限制条件=死胡同所有可能的状态构成了一个“迷宫”53状态空间想看看迷宫的全貌？所有可能的状态？对岸人的个数：p（0、1、2、3）对岸鬼的个数：g（0、1、2、3）船的位置：b（left，rght）4*4*2=32种。画个地图540/31/22/13/00/31/22/13/0此岸对岸画出全貌有点困难，看概貌吧。人鬼550/31/22/13/00/31/22/13/0此岸对岸其实是一个3d的迷宫，画出全貌有点困难，看概貌吧。人鬼4人4鬼能过吗？56所以，我们可以用一个三维数组：map442来表示这个“迷宫”57广搜

11、与深搜比较深度优先搜索符合人走迷宫的习惯栈可以写成回溯法，占用空间小，不需要将整个“迷宫”搬入内存要想办法避免“鬼打墙”58广搜与深搜广度优先搜索只能用队列存储待处理的状态一般来说占用空间大不会“鬼打墙”两者时间效率都是指数级59与深度优先搜索相比，广度优先搜索要存储的状态是指指数级数级的深度优先搜索，写成回溯法，甚至不需要存储状态，只存储算符就行了60如果要记录搜索路径，广度优先搜索要求存储整棵树61狼羊菜过河状态：（0，1，0，1）0，1分别代表两岸操作（算符）4种：运farmer、wolf运farmer、sheep运farmer、cabbage运farmer状态空间大小？24=16Map

12、222262状态空间0111羊菜狼没反映农夫的的状态人只能在对岸人只能在此岸63状态空间搜索是否存在环路？状态空间大小？小：可以整个搬入内存，普通迷宫大：无法存储整个状态空间深度优先搜索，防止死循环广度优先搜索，考虑空间问题有规律？盲目搜索？64围棋“大约连书万字四十三,即是局之大数。”沈括 梦溪笔谈棋盘上每个点有黑,白,空三种状态,棋盘状态就有3的361次方,约为10的172次方，也就是连书万字四十三因为棋盘每个点状态不能独立，排除非法状态，合法的状态数约为10的160次方 在可观测的宇宙空间，总共约有的次方个基本粒子 65如何做决策？幸好，这个迷宫是有规律的66盲目的搜索是最后的方法最好找出问题的规律67幸好，这是个有规律的宇宙68思考题：骷髅人回家怎么表示状态？几种算符？状态空间规模？可以在内存中建立地图吗？深度搜索VS广度搜索？深度搜索，如何避免死循环？广度搜索，如何存储历史状态？69谢谢大家参考文献：未名小游戏版（littlegame）精华区70