Matlab 广度优先搜索求解迷宫问题
前面写过一个深度优先搜索的算法，可以求出所有解，再写一个广度优先搜索的算法，但是只能求出一个解，希望大家多多指教function BFS_Maze(maze)% maze:是迷宫矩阵，其中0表示可以去走的路
% 1表示障碍
% 2表示入口
% 3表示出径
% 5表示路径
% 0 2 0 0 1
% 0 1 1 0 1
% 0 1 3 0 1
% 0 1 0 0 1% copyright: qbb 2013-3-12
if nargin == 0
maze = [0 2 0 0 1
0 1 1 0 1
0 1 3 0 1
0 1 0 0 1];
end
mazecopy = maze;
% 定义四个方向
directions = kron(eye(2),[-1,1]);
% 数组存储解的情况，I, J ,Pre
remark = zeros(100,3);
= find(maze == 2);% 找到起点
remark(1,:) = ;
count = 2;
search(1);
sol = remark(count-1,:);
while(sol(end,3) > 0)
sol = ;
end
mazecopy(sub2ind(size(maze), sol(2:end-1,1), sol(2:end-1,2))) = 5;
disp(mazecopy);
disp(sol);
function search(front)
x = remark(front,1);
y = remark(front,2);
for i = 1 : 4
if cango(x + directions(1,i),y + directions(2,i))
remark(count,1) = x + directions(1,i);
remark(count,2) = y + directions(2,i);
remark(count,3) = front;
count = count + 1;
if maze(x + directions(1,i),y + directions(2,i)) ~= 3
maze(x + directions(1,i),y + directions(2,i)) = 5;% 记录下来
else
return;
end
end
end
search(front + 1);
end
% 该函数判断该点是否可以经过
function z = cango(x,y)
% 用try来判断边界
z = true;
try
if ismember(maze(x,y),)% 路障或者已经走过
z = false;
end
catch
z = false; % 边界
end
end
end
求all simple paths本来就不是BFS的用途所在啊，毕竟DFS（你上个主题里的程序）要好用多了。
另外如果只求一个最优解，也可以考虑用图像处理工具箱里的函数。解法以前在mathworks的网站上看到过，还是挺漂亮的。但是对编程者而言就不涉及到算法层面了，也少了许多趣味。解法类似这样吧:maze = [0 2 0 0 1
0 1 1 0 1
0 1 3 0 1
0 1 0 0 1];
Dist1 = bwdistgeodesic(maze ~= 1, maze == 2, 'quasi-eu');
Dist2 = bwdistgeodesic(maze ~= 1, maze == 3, 'quasi-eu');
Dist = round((Dist1 + Dist2) * 8) / 8;
Dist(isnan(Dist)) = inf;
paths = imregionalmin(Dist)
nwcwww 发表于 2013-3-18 05:37 static/image/common/back.gif
求all simple paths本来就不是BFS的用途所在啊，毕竟DFS（你上个主题里的程序）要好用多了。
另外如果只求 ...
嗯，如果求最短路，也可以用一些图论算法的，另外这个程序我的运行结果四
>> mazePropaths = 0 1 1 0 0
0 0 0 1 0
0 0 1 0 0
0 0 0 0 0
不知道该如何理解行走路线？
qibbxxt 发表于 2013-3-18 07:35 static/image/common/back.gif
嗯，如果求最短路，也可以用一些图论算法的，另外这个程序我的运行结果四
不知道该如何理解行走路线？
mazePropaths矩阵里的1即是计算出来的通路。mazePropaths(1, 2)为起点，之后（1, 3), (2, 4), (3, 3)。
如果禁止斜走的话，可以修改下bwdistgeodesic里的选项。
页:
[1]