笛卡尔坐标系下玩家与旗帜最优分配的Python实现方案咨询

一、优化后的距离数据存储方式 #

原数据格式用嵌套列表存单个键值对，遍历和取值效率低，推荐直接用双层字典存储，结构更清晰，操作更便捷：

dist_dict_optimized = {
    "A": {"x": 12, "y": 10, "z": 20},
    "B": {"x": 14, "y": 18, "z": 25},
    "C": {"x": 8, "y": 15, "z": 16},
}

这种格式可以直接通过dist_dict_optimized["A"]["y"]快速获取玩家y到旗帜A的距离，后续计算时无需额外解析列表。

二、Python实现方案 #

该问题属于典型的指派问题，核心是在一对一约束下找到总距离最小的分配组合，以下提供两种可行方案：

方法1：暴力枚举法（适合小规模场景） #

由于玩家和旗帜数量仅为3，所有可能的分配组合共3! = 6种，直接遍历所有排列计算总距离即可：

import itertools

# 使用优化后的距离字典
dist_dict = {
    "A": {"x": 12, "y": 10, "z": 20},
    "B": {"x": 14, "y": 18, "z": 25},
    "C": {"x": 8, "y": 15, "z": 16},
}

flags = list(dist_dict.keys())
players = list(dist_dict["A"].keys())

min_total = float('inf')
best_assignment = []

# 遍历玩家的所有排列，每个排列对应一种旗帜-玩家分配方式
for perm in itertools.permutations(players):
    total_dist = 0
    current_assignment = []
    for flag, player in zip(flags, perm):
        total_dist += dist_dict[flag][player]
        current_assignment.append({flag: player})
    # 更新最小总距离和最优分配
    if total_dist < min_total:
        min_total = total_dist
        best_assignment = current_assignment

print("最优分配方案：", best_assignment)
print("最小总移动距离：", min_total)

输出结果：

最优分配方案： [{'A': 'y'}, {'B': 'x'}, {'C': 'z'}]
最小总移动距离： 40

方法2：匈牙利算法（适合大规模场景） #

如果玩家和旗帜数量较多，暴力枚举效率会急剧下降，此时可以用匈牙利算法求解，借助scipy库的linear_sum_assignment函数实现：

1. 先安装依赖：pip install scipy
2. 代码实现：

import numpy as np
from scipy.optimize import linear_sum_assignment

dist_dict = {
    "A": {"x": 12, "y": 10, "z": 20},
    "B": {"x": 14, "y": 18, "z": 25},
    "C": {"x": 8, "y": 15, "z": 16},
}

flags = list(dist_dict.keys())
players = list(dist_dict["A"].keys())

# 构建距离矩阵：行对应旗帜，列对应玩家
dist_matrix = np.array([
    [dist_dict[flag][player] for player in players]
    for flag in flags
])

# 匈牙利算法求解最优指派
row_indices, col_indices = linear_sum_assignment(dist_matrix)

# 转换为要求的输出格式
best_assignment = [
    {flags[row]: players[col]}
    for row, col in zip(row_indices, col_indices)
]
min_total = dist_matrix[row_indices, col_indices].sum()

print("最优分配方案：", best_assignment)
print("最小总移动距离：", min_total)

输出结果与暴力法完全一致。

三、方案选择建议 #

• 暴力枚举法：实现简单，无需额外依赖，适合玩家/旗帜数量≤10的小规模场景。
• 匈牙利算法：时间复杂度为O(n³)，效率更高，适合大规模指派问题，但需要依赖第三方库。

内容的提问来源于stack exchange，提问作者akkig