matlab商人过河代码

以下是商人过河问题的MATLAB代码示例：

function [path, time] = river_crossing()
    % 初始化状态
    state = struct('left', struct('missionaries', 3, 'cannibals', 3, 'boat', 1), ...
                   'right', struct('missionaries', 0, 'cannibals', 0, 'boat', 0));
    % 初始化路径和时间
    path = [];
    time = 0;
    
    % 深度优先搜索
    [path, time] = dfs(state, path, time);
end

function [path, time] = dfs(state, path, time)
    % 判断是否达到目标状态
    if state.left.missionaries == 0 && state.left.cannibals == 0 && state.left.boat == 0
        return;
    end
    
    % 获取当前状态的合法动作
    actions = get_actions(state);
    
    % 遍历所有合法动作
    for i = 1:length(actions)
        % 执行动作
        new_state = execute_action(state, actions(i));
        
        % 判断新状态是否合法
        if is_valid_state(new_state)
            % 更新路径和时间
            path = [path, new_state];
            time = time + 1;
            
            % 递归搜索
            [path, time] = dfs(new_state, path, time);
            
            % 如果找到解，则直接返回
            if state.left.missionaries == 0 && state.left.cannibals == 0 && state.left.boat == 0
                return;
            end
            
            % 回溯，恢复路径和时间
            path = path(1:end-1);
            time = time - 1;
        end
    end
end

function actions = get_actions(state)
    % 获取当前状态的合法动作
    actions = [];
    if state.left.boat == 1
        for i = 0:2
            for j = 0:2
                if i + j >= 1 && i + j <= 2 && i + j <= state.left.missionaries && i + j <= state.left.cannibals
                    actions = [actions, struct('missionaries', i, 'cannibals', j)];
                end
            end
        end
    else
        for i = 0:2
            for j = 0:2
                if i + j >= 1 && i + j <= 2 && i + j <= state.right.missionaries && i + j <= state.right.cannibals
                    actions = [actions, struct('missionaries', i, 'cannibals', j)];
                end
            end
        end
    end
end

function new_state = execute_action(state, action)
    % 执行动作，更新状态
    new_state = state;
    if state.left.boat == 1
        new_state.left.missionaries = new_state.left.missionaries - action.missionaries;
        new_state.left.cannibals = new_state.left.cannibals - action.cannibals;
        new_state.right.missionaries = new_state.right.missionaries + action.missionaries;
        new_state.right.cannibals = new_state.right.cannibals + action.cannibals;
        new_state.left.boat = 0;
        new_state.right.boat = 1;
    else
        new_state.left.missionaries = new_state.left.missionaries + action.missionaries;
        new_state.left.cannibals = new_state.left.cannibals + action.cannibals;
        new_state.right.missionaries = new_state.right.missionaries - action.missionaries;
        new_state.right.cannibals = new_state.right.cannibals - action.cannibals;
        new_state.left.boat = 1;
        new_state.right.boat = 0;
    end
end

function valid = is_valid_state(state)
    % 判断状态是否合法
    valid = (state.left.missionaries == 0 || state.left.missionaries >= state.left.cannibals) && ...
            (state.right.missionaries == 0 || state.right.missionaries >= state.right.cannibals);
end