Matlab中迷宫的宽度优先搜索[重复]

Question

我正在尝试实现一个广度优先算法，它解决了一个迷宫。作为输入，我有一个n*m的二进制矩阵，其中“1”代表障碍物/墙，“0”代表路径/自由单元。

我确实知道该算法通常是如何工作的，但我正在努力学习如何在matlab中存储和处理信息。所以基本上我从我的启动单元开始，检查所有它的直接邻居是否有障碍物。如果它们是自由的，我将它们标记为一条潜在路径，然后我再次递归地对所有这些单元执行相同的操作。

但是我就是不知道怎么存储信息，所以最后我只有一条路。有什么想法吗？

Answer 1

这是一个通过深度优先搜索在无方向图中搜索连接组件的函数。BFS应该更容易编码。

function comp = findNodeComponentDFS(G, node)
%Find a connected component of the given node in the unoriented graph. Use
%Deep first search (Cormen, Rivest, Leiserson)
%G - connectivity matrix
%node - given node
%comp - contain the numbers of all nodes in the found connected component
%except the node itself
N = length(G);
white = ones(1,N);%unexamined vertices
grey = zeros(1,N);%vertices that are currently examining but with not all edges have been    examined yet
black = zeros(1,N);%vertices with all the edges have been examined
prev = zeros(1,N);
current = node;
stop=false;
while (~stop)
    grey(current) = 1;
    white(current) = 0;
    next = find(G(current,:) & white,1);
    if (isempty(next))
        black(current) = 1;
        if (prev(current)==0)
            stop = true;
        else
            current = prev(current);%back to previous vertice
        end
    else
        prev(next) = current;
        current = next;
    end
end
comp = find(black);

Answer 2

您可以像在a星型寻路算法中一样使用“打开”和“关闭”列表。检查所有邻居，如果邻居不是障碍物，则将其放入开放列表中。检查所有邻居和具有最小成本的邻居，将其放入封闭列表中。最后，您将在关闭列表中找到最佳路径。基本上是这样的。。