最短路径口罩分配算法：高效解决社区口罩短缺问题

% 家庭住址坐标 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);

% 根据最短路径给不充足家庭分配口罩 [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

% 回溯算法函数 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