matlab中求解迷宫的广度优先搜索算法[副本]

Question

如果有人有主意请帮帮我。

Answer 1

听起来好像您已经知道如何实现一个算法，但是请查看Djikstra的算法，以了解解决这个问题的简单方法。

至于MATLAB，我只是简单地使用了一系列矩阵来表示每个单元格的信息。使用Djikstra的算法，从单个开放节点开始，检查其邻居并计算每个节点的路径开销，然后转移到开销最低的邻居。诀窍是将您访问过的节点设置为关闭，将您检查过的邻居设置为打开，并将未检查的节点保留为未知。

下面是我的代码，它基于障碍物的图像运行，其中自由单元格为白色，障碍物单元格为黑色。因此，您可以打开一个简单的绘画程序，如MSPaint和绘制地图非常容易。然后只需相应地更改代码顶部的文件名。

% read map file
map_file = 'obstacle_map.png';
obstacleMap = imread(map_file);
obstacleMap = 1 - obstacleMap(:,:,1)';

% get map size
Ni = size(obstacleMap,1);
Nj = size(obstacleMap,2);

% set initial position node
i0 = 1;
j0 = 1;

% set target position node
iTrg = Ni;
jTrg = Nj;

% initialize open node map, and close obstacle nodes
open_map = zeros(Ni,Nj);
open_map = open_map - 2*double(obstacleMap);

% initialize best score map
f_score = 0*ones(Ni,Nj);

% initialize previous node maps
Iprev = zeros(Ni,Nj);
Jprev = zeros(Ni,Nj);

% start open map with initial position node open
open_map(i0,j0) = 1;
is_open = 1;

% skip this many frames during plotting
Ngtf = 100;

% keep searching while there are open nodes
count = 0;
while is_open > 0;

    % loop counter
    count = count + 1;

    % find open node with the lowest score
    F_score = f_score + (1e9)*(open_map ~= 1);      % take the scores and add some big number to nodes that aren't open
    [ic,jc] = find(F_score == min(min(F_score)));

    % we might have more than one with the lowest score, so just take the
    % first candidate
    ic = ic(1);
    jc = jc(1);    

    % exit if we reach the target node
    if (ic == iTrg) && (jc == jTrg);
        break;
    end

    % set the current node to be closed
    open_map(ic,jc) = -1;

    % for each neighbour of the current node
    for i = (ic-1):(ic+1);

        % don't try checking neighbours out of bounds
        if i < 1 || i > Ni;
            continue;
        end

        for j = (jc-1):(jc+1);

            % don't try checking neighbours out of bounds
            if j < 1 || j > Nj;
                continue;
            end

            % skip if the neighbour has already been visited (i.e., it is
            % closed)
            if open_map(i,j) < 0;
                continue;
            end

            % compute the new best score to the neighbour (the best
            % score to the current node plus the distance to the neighbour
            % node from the currend node)
            f_score_new = f_score(ic,jc) + sqrt((i - ic)^2 + (j - jc)^2);

            % if the new best score is less than the previous best score
            % for the neighbour node, or the neighbour node has never been
            % checked
            if open_map(i,j) ~= 1 || f_score_new < f_score(i,j);

                % set the previous node indices (keep track of the actual
                % path)
                Iprev(i,j) = ic;
                Jprev(i,j) = jc;

                % update the new score
                f_score(i,j) = f_score_new;

                % set the neighbour node to be open
                open_map(i,j) = 1;
            end

        end
    end

    % plotting
    curr_map = open_map;
    curr_map(ic,jc) = 2;
    if mod(count,Ngtf) == 0;
        clf;
        surf(curr_map,'edgealpha',0);
        axis equal
        view(2)
        getframe;
    end

    % check how many nodes are open
    is_open = sum(sum(open_map == 1));

end

% final plotting map
final_map = open_map;

% final node
iF = ic;
jF = jc;

% backtrack through the list of previous nodes to construct the final path
ipath = [];
jpath = [];
while 1;
    final_map(iF,jF) = 2;
    if iF == i0 && jF == j0;
        break;
    end
    iprev = Iprev(iF,jF);
    jprev = Jprev(iF,jF);
    ipath = [iprev ipath];
    jpath = [jprev jpath];
    iF = iprev;
    jF = jprev;     
end


clf;
surf(final_map,'edgealpha',0);
hold on;
plot3(jpath,ipath,100000*ones(size(ipath)),'k.-');
axis equal
view(2)