Matlab 广度优先搜索求解迷宫问题

qibbxxt

前面写过一个深度优先搜索的算法，可以求出所有解，再写一个广度优先搜索的算法，但是只能求出一个解，希望大家多多指教

1. function BFS_Maze(maze)% maze:是迷宫矩阵，其中0表示可以去走的路
   
2. %                     1表示障碍
   
3. %                     2表示入口
   
4. %                     3表示出径
   
5. %                     5表示路径
   
6. %             0 2 0 0 1
   
7. %             0 1 1 0 1
   
8. %             0 1 3 0 1
   
9. %             0 1 0 0 1% copyright: qbb 2013-3-12
   
10. if nargin == 0
    
11.     maze = [0 2 0 0 1
    
12.         0 1 1 0 1
    
13.         0 1 3 0 1
    
14.         0 1 0 0 1];
    
15. end
    
16. mazecopy = maze;
    
17. % 定义四个方向
    
18. directions = kron(eye(2),[-1,1]);
    
19. % 数组存储解的情况，I, J ,Pre
    
20. remark = zeros(100,3);
    
21. [I,J] = find(maze == 2);% 找到起点
    
22. remark(1,:) = [I,J,-1];
    
23. count = 2;
    
24. search(1);
    
25. sol = remark(count-1,:);
    
26. while(sol(end,3) > 0)
    
27.     sol = [sol;remark(sol(end,3),:)];
    
28. end
    
29. mazecopy(sub2ind(size(maze), sol(2:end-1,1), sol(2:end-1,2))) = 5;
    
30. disp(mazecopy);
    
31. disp(sol);
    
32.     function search(front)
    
33.         x = remark(front,1);
    
34.         y = remark(front,2);        
    
35.         for i = 1 : 4
    
36.             if cango(x + directions(1,i),y + directions(2,i))
    
37.                 remark(count,1) = x + directions(1,i);
    
38.                 remark(count,2) = y + directions(2,i);
    
39.                 remark(count,3) = front;
    
40.                 count = count + 1;
    
41.                 if maze(x + directions(1,i),y + directions(2,i)) ~= 3
    
42.                     maze(x + directions(1,i),y + directions(2,i)) = 5;% 记录下来
    
43.                 else
    
44.                     return;
    
45.                 end
    
46.                
    
47.             end
    
48.         end
    
49.         search(front + 1);
    
50.     end
    
51. % 该函数判断该点是否可以经过
    
52.     function z = cango(x,y)
    
53.         % 用try来判断边界
    
54.         z = true;
    
55.         try
    
56.             if ismember(maze(x,y),[1,2,5])% 路障或者已经走过
    
57.                 z = false;
    
58.             end
    
59.         catch
    
60.             z = false; % 边界
    
61.         end
    
62.     end
    
63. end
    

复制代码

nwcwww

求all simple paths本来就不是BFS的用途所在啊，毕竟DFS（你上个主题里的程序）要好用多了。

另外如果只求一个最优解，也可以考虑用图像处理工具箱里的函数。解法以前在mathworks的网站上看到过，还是挺漂亮的。但是对编程者而言就不涉及到算法层面了，也少了许多趣味。解法类似这样吧:

1. maze = [0 2 0 0 1
   
2.         0 1 1 0 1
   
3.         0 1 3 0 1
   
4.         0 1 0 0 1];
   
5. Dist1 = bwdistgeodesic(maze ~= 1, maze == 2, 'quasi-eu');
   
6. Dist2 = bwdistgeodesic(maze ~= 1, maze == 3, 'quasi-eu');
   
7. Dist = round((Dist1 + Dist2) * 8) / 8;
   
8. Dist(isnan(Dist)) = inf;
   
9. paths = imregionalmin(Dist)
   

复制代码

qibbxxt

nwcwww 发表于 2013-3-18 05:37
求all simple paths本来就不是BFS的用途所在啊，毕竟DFS（你上个主题里的程序）要好用多了。

另外如果只求 ...

嗯，如果求最短路，也可以用一些图论算法的，另外这个程序我的运行结果四

1. >> mazePropaths =     0     1     1     0     0
   
2.      0     0     0     1     0
   
3.      0     0     1     0     0
   
4.      0     0     0     0     0
   

复制代码

不知道该如何理解行走路线？

nwcwww

qibbxxt 发表于 2013-3-18 07:35
嗯，如果求最短路，也可以用一些图论算法的，另外这个程序我的运行结果四

不知道该如何理解行走路线？

mazePropaths矩阵里的1即是计算出来的通路。mazePropaths(1, 2)为起点，之后（1, 3), (2, 4), (3, 3)。
如果禁止斜走的话，可以修改下bwdistgeodesic里的选项。