基于最短路径的口罩共享方案优化

本程序模拟了多个家庭之间口罩共享的场景，并使用最短路径算法找到最省钱的口罩分配方案。

1. 数据准备

% 家庭住址坐标
address = [
    30 35; % 班主任
    18 12
    23 17
    10 0
    15 25
    13 10
    20 20
    20 25
    32 15
    15 18
    24 9
    3 8
    33 3
    34 26
    37 23
    18 4
    42 8
    50 23
    53 16
    55 38
    7 42
];

% 拥有口罩数和最低需求口罩数
masks = [
    14 15
    14 9
    15 9
    4 8
    8 10
    12 8
    13 18
    7 11
    11 18
    23 24
    15 4
    17 10
    5 9
    19 27
    11 5
    20 7
    2 6
    10 8
    11 18
    13 18
];

% 初始化共享方案矩阵和口罩分配方案矩阵
sharing_scheme = zeros(20);
mask_allocation = zeros(20);

% 初始化充足口罩的家庭列表和不充足口罩的家庭列表
sufficient_list = [];
insufficient_list = [];

% 遍历每个家庭，标记是否口罩充足
for i = 1:20
    if masks(i, 1) >= masks(i, 2) % 口罩充足
        sufficient_list = [sufficient_list; i];
    else % 口罩不足
        insufficient_list = [insufficient_list; i];
    end
end

% 计算每个家庭之间的距离
distances = pdist(address);
dist_matrix = squareform(distances);

2. 最短路径算法

% 根据最短路径给不充足家庭分配口罩
[shortest_path, shortest_distance] = backtrack([1], 0, [1]);

% 根据最短路径给不充足家庭分配口罩
for i = 2:length(shortest_path)-1
    receiver_idx = shortest_path(i);
    receiver_demand = masks(receiver_idx, 2) - masks(receiver_idx, 1); % 口罩需求量
    for j = 1:length(sufficient_list)
        donor_idx = sufficient_list(j);
        donor_supply = masks(donor_idx, 1) - masks(donor_idx, 2); % 口罩供应量
        if donor_supply >= receiver_demand % 口罩充足，满足需求并退出循环
            sharing_scheme(donor_idx, receiver_idx) = receiver_demand;
            mask_allocation(receiver_idx, donor_idx) = receiver_demand;
            masks(donor_idx, 1) = masks(donor_idx, 1) - receiver_demand;
            break;
        else % 口罩不足，分配所有可供应的口罩
            sharing_scheme(donor_idx, receiver_idx) = donor_supply;
            mask_allocation(receiver_idx, donor_idx) = donor_supply;
            masks(donor_idx, 1) = masks(donor_idx, 2);
            receiver_demand = receiver_demand - donor_supply;
        end
    end
end

% 输出最省钱的共享方案和总共需要支付的快递费
disp('最省钱的共享方案：')
disp(sharing_scheme)

% 输出给不充足家庭口罩的家庭列表
disp('给不充足家庭口罩的家庭列表：')
for i = 1:length(insufficient_list)
    receiver_idx = insufficient_list(i);
    donors = find(mask_allocation(receiver_idx, :) > 0);
    for j = 1:length(donors)
        donor_idx = donors(j);
        disp(['家庭', num2str(donor_idx), ' 给予家庭', num2str(receiver_idx), ' ', num2str(mask_allocation(receiver_idx, donor_idx)), ' 个口罩'])
    end
end

3. 回溯算法

% 回溯算法函数
function [shortest_path, shortest_distance] = backtrack(path, distance, visited)
    if length(path) == 21 % 所有家庭都已访问
        shortest_path = path;
        shortest_distance = distance;
        return;
    end
    
shortest_path = [];
shortest_distance = Inf;
    
    for i = 2:21 % 从家庭2到家庭21依次访问
        if ~ismember(i, visited) % 当前家庭未被访问
            new_distance = distance + dist_matrix(path(end), i); % 更新路径距离
            if new_distance < shortest_distance % 剪枝：如果当前路径距离已经大于最短路径，不再继续搜索
                [new_path, new_distance] = backtrack([path, i], new_distance, [visited, i]); % 递归搜索下一个家庭
                if new_distance < shortest_distance % 更新最短路径
                    shortest_path = new_path;
                    shortest_distance = new_distance;
                end
            end
        end
    end
end

4. 总结

本程序通过计算家庭之间距离，利用最短路径算法找到最省钱的口罩分配方案，有效地提高了口罩资源利用率。该算法可以推广到其他资源共享场景，例如药品、食物等。

**注意：**程序中假设快递费用与距离成正比。实际应用中，快递费用可能受多种因素影响，需要根据具体情况进行调整。

程序中使用的主要函数：

pdist: 计算两点之间的距离
squareform: 将距离矩阵转换为方阵
ismember: 判断元素是否在数组中
find: 查找数组中满足条件的元素索引
num2str: 将数字转换为字符串
disp: 显示输出