农夫过河问题 matlab,农夫过河问题 宽搜（bfs）算法详解

农夫过河问题是一个经典的人工智能问题，可以用来介绍搜索算法。问题描述如下：

一个农夫带着一只狼、一只羊和一筐菜过河，只有一条小船，小船最多只能装下农夫和另外一只动物或者一筐菜。当农夫不在场时，狼会吃羊，羊会吃菜。请问农夫如何能够安全地把这三样东西都带过河？

下面是使用Matlab实现的代码：

% 农夫过河问题
% 1表示农夫、2表示狼、3表示羊、4表示菜
% 初始状态为[1,2,3,4,0],目标状态为[0,0,0,0,1]
% 状态表示为[a,b,c,d,e]，其中a,b,c,d表示四个位置上的状态，e表示小船的位置
% 0表示该位置上无人或无物

function main()
    start = [1,2,3,4,0];
    goal = [0,0,0,0,1];
    path = bfs(start, goal);
    if isempty(path)
        disp('无解');
    else
        disp('解为：');
        disp(path);
    end
end

function path = bfs(start, goal)
    queue = [start, 0];
    visited = [start];
    path = [];
    while ~isempty(queue)
        node = queue(1, :);
        queue(1, :) = [];
        if isequal(node(1:5), goal)
            path = [node(6); path];
            while node(6) ~= 0
                node = visited(node(6), :);
                path = [node(6); path];
            end
            return;
        end
        for i = 1:4
            if node(5) == 0 && node(i) == 1
                next = node;
                next(i) = 0;
                next(5) = 1;
                if ~ismember(next, visited, 'rows')
                    queue = [queue; next, size(visited, 1) + 1];
                    visited = [visited; next];
                end
            elseif node(5) == 1 && node(i) == 0
                next = node;
                next(i) = 1;
                next(5) = 0;
                if ~ismember(next(1:5), visited, 'rows') && is_valid(next)
                    queue = [queue; next, size(visited, 1) + 1];
                    visited = [visited; next(1:5)];
                end
            elseif node(5) == 0 && node(i) ~= 1 && node(i) ~= 0
                next = node;
                next(i) = 0;
                next(5) = 1;
                if ~ismember(next(1:5), visited, 'rows') && is_valid(next)
                    queue = [queue; next, size(visited, 1) + 1];
                    visited = [visited; next(1:5)];
                end
            elseif node(5) == 1 && node(i) ~= 1 && node(i) ~= 0
                next = node;
                next(i) = 1;
                next(5) = 0;
                if ~ismember(next(1:5), visited, 'rows') && is_valid(next)
                    queue = [queue; next, size(visited, 1) + 1];
                    visited = [visited; next(1:5)];
                end
            end
        end
    end
end

function valid = is_valid(node)
    if node(2) == 3 && node(3) == 4 && node(5) == 0
        valid = false;
    elseif node(2) == 0 && node(3) == 4 && node(5) == 1
        valid = false;
    elseif node(2) == 3 && node(3) == 0 && node(5) == 1
        valid = false;
    elseif node(2) == 0 && node(3) == 0 && node(5) == 0
        valid = false;
    else
        valid = true;
    end
end

其中，bfs函数是使用宽搜算法实现的，is_valid函数用来判断当前状态是否合法。程序运行后会输出解的路径，如果无解则会输出“无解”。