宽度优先搜索解迷宫

guocong89

花半个小时帮朋友解一个迷宫问题，整理出来做个备案吧。
题目描述：

Mazes can keep one captured for hours if you actually walk in one. Still there are many approaches to logically find the exit. Some may take more time, and might in practice not be possible esspecially if there would be other perons walking in the same maze messing with your trail! We can however program a few algorithms on the computer to see how well they are doing. A small list of possible algorithms is:



       - Random mouse algorithm        - Wall follower        - Pledge algorithm        - Tremaux's algorithm        - Dead-end filling        - Shortest path algorithm


If you cannot imagine what they are look them up at (http://en.wikipedia.org/wiki/Maze_solving_algorithm, if you can't acces this let us now). An example maze with solution is given by:






算法很简单，宽搜向外扩展可行区域，逆向返回即可。

1. maze = ImageData[\!\(\*
   
2. GraphicsBox[
   
3. TagBox[RasterBox[CompressedData["
   
4. 1:eJylUskNgDAMi8QCPFiAlRihC7D/i0NFkbHTlCOCqkprO3E6l3Upg5lN13/u
   
5. /8Q4b/Qdya0ReB9J6qljVcWxvnoSj3LdHKty2CNhidbZahdqiErUpPOgUKs8
   
6. UtERIEqxNALceA25LeQG1tOtua7h9J9glUovhP1i40mm1S+9BNJVbFe35Weo
   
7. gpCQmXTD+vUo9NnuoyTbE+yrMHh1n2MHv03QpQ==
   
8. "], {{0, 20}, {20, 0}}, {0,
   
9.          255},
   
10. ColorFunction->RGBColor],
    
11. BoxForm`ImageTag["Byte", ColorSpace -> "RGB", Interleaving -> True],
    
12. Selectable->False],
    
13. BaseStyle->"ImageGraphics",
    
14. ImageSize->{246., Automatic},
    
15. ImageSizeRaw->{20, 20},
    
16. PlotRange->{{0, 20}, {0, 20}}]\)][[;; , ;; , 3]];

复制代码

1. shortestPath[maze_, start_, end_] := Module[
   
2.   {curIndex = 1, cur = start, queue = {start},
   
3.    dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}, i},
   
4.   While[! MemberQ[queue, end],
   
5.    For[i = 1, i < 5, i++,
   
6.     If[! MemberQ[queue, cur + dir[[i]]] &&
   
7.        Extract[maze, cur + dir[[i]]] == 1,
   
8.       AppendTo[queue, cur + dir[[i]]]
   
9.       ];
   
10.     ];
    
11.    curIndex++;
    
12.    cur = queue[[curIndex]];
    
13.    ];
    
14.   NestWhileList[
    
15.    First@Select[queue, Function[u, Total[Abs[u - #]] == 1]] &,
    
16.    end, # != start &]
    
17.   ]
    

复制代码

1. path = shortestPath[maze, {2, 1}, {19, 20}];
   
2. Image@MapAt[0.5 &, maze, path]

复制代码

FreddyMusic

http://blog.wolfram.com/2010/12/ ... m-palace-continues/

Wolfram Blog 前一阵子，为了算Maze 还打起来了。

你认为他们的方法怎么样，有何评论吗？

guocong89

2# FreddyMusic
我在google reader上看了这篇文章，当时看得时候是把它当作一篇关于图像处理的文章进行分类的。
它在进行了第一步处理（DeleteSmallComponents或者Pruning)之后，实际上已经得到了一个连通图，而且图结构高度简化，没有很多无关分支，所以通过求图的最短路就求出了迷宫答案。寻找最短路有很简单的算法，Dijstra，Floyd 都可以。

但是根据我的做题经验（ACM），迷宫问题一般是和图论没有什么联系的，迷宫问题考察的是搜索技术。所以我觉得这篇文章并没有探讨迷宫理论问题，而是侧重于如何把一个实际图片建模成一个图结构。

解迷宫我一般使用dfs，速度相对较快，但是会很难得到最短路径，而且不够稳定，最糟糕的情况会把整个地图遍历一遍。使用BFS就稳定一些，只是空间和时间复杂度都较高。

FreddyMusic

想法不错，分析也有一定的道理。

我建议你可以将自己的迷宫算法和以下的一个演示项目相结合，自己动手写个新的演示项目。

http://demonstrations.wolfram.com/InteractiveMaze/

他的程序主要是生成一个随机的迷宫题，而你的算法正好可以解题。

tiancai3385

谢谢～～，好东西～～，就是看不懂。哈哈

chungyuandye

1. 
   
2. maze=ImageData[\!\(\*
   
3. GraphicsBox[
   
4. TagBox[RasterBox[CompressedData["
   
5. 1:eJylUskNgDAMi8QCPFiAlRihC7D/i0NFkbHTlCOCqkprO3E6l3Upg5lN13/u
   
6. /8Q4b/Qdya0ReB9J6qljVcWxvnoSj3LdHKty2CNhidbZahdqiErUpPOgUKs8
   
7. UtERIEqxNALceA25LeQG1tOtua7h9J9glUovhP1i40mm1S+9BNJVbFe35Weo
   
8. gpCQmXTD+vUo9NnuoyTbE+yrMHh1n2MHv03QpQ==
   
9. "],{{0,20},{20,0}},{0,
   
10. 255},
    
11. ColorFunction->RGBColor],
    
12. BoxForm`ImageTag["Byte",ColorSpace->"RGB",Interleaving->True],
    
13. Selectable->False],
    
14. BaseStyle->"ImageGraphics",
    
15. ImageSize->{246.,Automatic},
    
16. ImageSizeRaw->{20,20},
    
17. PlotRange->{{0,20},{0,20}}]\)][[;;,;;,3]][[2;;-2,2;;-2]]
    
18. 
    
19. maze//Dimensions
    
20. 
    
21. maze//ArrayPlot
    
22. 
    
23. n1=Table[If[maze[[i,j]]*maze[[i,j+1]]==1,
    
24. UndirectedEdge[Length@maze*(i-1)+j,Length@maze*(i-1)+j+1]],{i,1,Length@maze},{j,1,Length@maze-1}];
    
25. n2=Table[If[maze[[i,j]]*maze[[i+1,j]]==1,UndirectedEdge[Length@maze*(i-1)+j,Length@maze*i+j]],{i,1,Length@maze-1},{j,1,Length@maze}];
    
26. medge=Select[Flatten[{n1,n2}],Length@#>=2&]
    
27. 
    
28. mg=Graph[Range[Length@maze*Length@maze],
    
29. medge,{FrameTicks->None,VertexCoordinates->
    
30. Flatten[Table[{i,j},{i,0,Length@maze-1},{j,0,Length@maze-1}],1]}]
    
31. 
    
32. mpath=FindShortestPath[mg,First@VertexList[mg],Last@VertexList[mg]]
    
33. 
    
34. HighlightGraph[mg,PathGraph@FindShortestPath[mg,First@VertexList[mg],Last@VertexList[mg]]]
    
35. 
    
36. sp[k_]:=Flatten[{UndirectedEdge[#[[1]],#[[2]]]->{Thickness[0.01],
    
37. Red}}&/@Partition[FindShortestPath[mg,First@VertexList[mg],Last@VertexList[mg]],
    
38. 2,1]][[1;;k]]
    
39. 
    
40. Animate[Graph[Range[Length@maze*Length@maze],
    
41. medge,{FrameTicks->None,VertexCoordinates->Flatten[
    
42. Table[{i,j},{i,0,Length@maze-1},{j,0,Length@maze-1}],
    
43. 1]},GraphHighlightStyle->Thick[0.01],
    
44. EdgeStyle->sp[z]],{z,1,52,1}]
    

复制代码

guocong89

4# FreddyMusic
正在preview状态，不知道为什么没有发表

http://demonstrations.wolfram.com/preview.html?draft/67796/000001/MazeGeneratorAndSolver

FreddyMusic

然后选 Submit for publications.就可以了.