用matlab编写程序解决人狼羊菜过河问题，要求转化为最短路径问题解决

人狼羊菜过河问题是经典的图搜索问题，也可以转换成寻找最短路径的问题。在MATLAB中，我们可以利用其图形处理库（Graph Toolbox）来解决这个问题。通常的做法是：

1. **建立图模型**：
- 将河流看作边，每条边有特定的成本（例如安全度、时间等），表示移动的难易程度。
- 标记各个岛屿（人、狼、羊和菜）为节点，并设置起始点和终点。

2. **定义状态空间**：
- 状态可以用一个二进制数组表示，比如1代表人，2代表狼，3代表羊，4代表菜，0代表水域。
- 每一步移动，都会改变当前位置的状态，并检查新的位置是否允许移动（比如狼不能和羊同处一岛）。

3. **选择算法**：
- 可能会用到Dijkstra算法或A*算法，因为这是一个单源最短路径问题。
- Dijkstra适用于所有非负权重的图，而A*更适合具有启发式信息（如估计距离）的情况。

4. **编写函数**：
- 创建一个函数，接受起始点、目标点以及当前状态作为输入。
- 使用循环遍历所有相邻节点，更新邻接节点的距离并选择下一个最小成本节点。

5. **求解并回溯**：
- 找到从起点到终点的最短路径，同时记录每个节点的前驱节点，用于回溯生成解决方案。

function [path, distance] = shortestPathWolfSheepCabbage(riverEdges, initialState, goalState)
    % 初始化图
    G = graph();
    for edge in riverEdges
        G = addEdge(G, edge.src, edge.dst, edge.cost);
    end

    % 设置起点和终点
    startNode = find(initialState == 1); % 找到人所在的位置
    endNode = find(goalState == 1);       % 同理找目标位置

    % 搜索并获取最短路径
    [distances, path] = dijkstra(G, startNode);

    % 回溯路径
    solution = [];
    while ~isempty(path(end))
        if initialState(path(end)) ~= 0 % 避免添加水域节点
            solution = [solution; initialState(path(end))];
        end
        path = path(1:end-1);
    end

    % 返回结果
    path = reverse(solution); % 因为搜索是从起点开始，所以需要反向
end