Munkres 算法与角色匹配¶

高层战术写的是“Leader 去接球”“某个后卫去补位”“另一个角色去盯人”，但真正上场执行的是当前这几台有效机器人。于是系统每一帧都要做一件很现实的事：把“角色任务”分配给“真实车号”，并尽量让总代价最小。

这就是本队代码里角色匹配模块的核心问题。

为什么不能只靠“谁近谁上”¶

如果场上只有一个任务，那最近的车去做，大多数时候没毛病。麻烦在于比赛里几乎从来不是一个任务单独出现的。你一旦同时有 leader、receiver、back、marking 几类角色，局部最近和整体最优就不一定是一回事了。

举个很典型的直觉误区：某辆车离 L 最近，于是先把它塞给 L；接着你再给 A 挑最近的车；最后再给 B 挑最近的车。这个“逐个就近”看起来合理，但常常会把后面的选择空间挤没，导致总体跑位更差。Munkres 的价值就在这里，它不是只看当前一步，而是看整个代价矩阵的总和。

在 SRC 里，这张矩阵是怎么来的¶

Python 侧的主要实现可以顺着两处代码去看：

Algorithm/munkre.py
RoleMatch_LuaStyle/State.py

当前最常见的 cost 定义很朴素：

cost(task, vehicle) = 车辆当前位置 到 task.matchPos 的距离

其中 task.matchPos 不是“最终一定要跑到的终点”，而是为了匹配而选的代表点。比如一个 Shoot 任务最后真正执行时，还会继续考虑朝向、吸球、避障、加速度、触球条件等细节；但在做角色分配时，我们只需要先回答“哪台车最适合先接这个任务”。

一句话记忆 matchPos

matchPos 更像“这件事大概该由哪台车来接手”的参考点，而不是完整的底层控制目标。

先用一个 3x3 小例子把它讲明白¶

假设当前场上有效的三台车分别是 2、4、7 号。状态机这帧生成了三个角色任务：

L：主攻车，要先去接球
A：接应车，要去 receiver 区域
B：防守车，要补到回防点

根据三台车当前位置到三个 matchPos 的距离，我们得到下面这个代价表。这里单位不重要，你只需要把它当成“越小越合适”。

车号角色	`L`	`A`	`B`
`2`	8	12	26
`4`	14	5	9
`7`	9	11	4

如果你现在凭直觉看，似乎已经能猜到：

2 -> L
4 -> A
7 -> B

但 Munkres 并不是靠“看着像”来决定的，它会把这个问题系统化地处理。

第一步：每一行减去本行最小值¶

每一行都先减掉该行的最小值，得到：

车号角色	`L`	`A`	`B`
`2`	0	4	18
`4`	9	0	4
`7`	5	7	0

这一步的意义，不是改变最优解，而是把“每台车当前最倾向的角色”显成 0。

第二步：看每一列是否也已经有 0¶

现在三列里都已经至少有一个 0 了，所以这一轮不需要再额外做列缩减。于是我们可以开始选互不冲突的 0。

第三步：选一个 0，并划掉对应的行和列¶

先看第一行，2 号车在 L 列有个 0。我们先选它，意味着先确定：

2 号车 -> L

这时 2 号车这整行就不能再分给别的角色，L 这一列也不能再给别的车，所以把这一行和这一列划掉。剩下的可选子矩阵就变成：

车号角色	`A`	`B`
`4`	0	4
`7`	7	0

继续同样的过程：

选 4 -> A，划掉 4 这一行和 A 这一列；
最后只剩 7 -> B。

于是完整结果就是：

L -> 2 号车
A -> 4 号车
B -> 7 号车

你会注意到，Munkres 的“划行划列”其实很符合我们队里常说的“一个角色只能分一台车，一台车也只能接一个角色”。它并不是玄学算法，而是把这个约束系统化了。

如果 0 冲突了怎么办¶

上面的例子比较顺，因为每一行最后都落在不同列。真实比赛里当然没这么整齐，经常会出现两台车都更想去同一个角色，或者某一列被多个 0 挤在一起。这时 Munkres 会继续做“覆盖所有 0 的最少直线”“调整未覆盖元素”等步骤，再制造新的 0，直到能选出一组互不冲突的解。

文档里没必要把完整数学过程一口气铺完，不然反而失去重点。对我们写战术来说，更重要的是理解三件事：

这套算法在做全局最优，而不是逐个凑最近。
你的 matchPos 设计，会直接影响它的分配结果。
matchStr 决定了哪些角色要参加这次匹配，哪些角色沿用上一次身份。

`matchStr` 到底在描述什么¶

很多 Play 会返回类似这样的字符串：

{LA}(BCD)[EF]

它不是装饰，而是在定义“这几个角色该多稳定”。

[]：RealTime，每次都允许重新匹配，适合位置波动很大的角色。
()：Once，进入状态时匹配一次，适合同一状态内希望保持相对稳定的角色。
{}：Never，除非切了 Play，否则尽量不重新匹配，适合强依赖身份连续性的角色。

所以 matchStr 其实是在告诉系统：哪些角色应该追求最优，哪些角色应该追求稳定。 这也是它和 Munkres 配合起来真正有威力的地方。

固定车号与自动匹配如何共存¶

SRC 当前代码并不是“所有角色都交给 Munkres”。守门员通常会固定，某些 Test 脚本也会人工指定车号。这里的优先级大致可以这么理解：

Task(..., fixedNumber=...) 里明确指定的编号优先级最高。
Global.defaultRoleNumberStructTable 里预设的固定规则次之。
剩下还没锁死的角色，才进入 Munkres 自动匹配。

这也是为什么你在很多脚本里会看到 G 固定成某个车号，而其他角色继续自动漂移。

把它和代码对应起来¶

如果你想把上面的逻辑和仓库实现一一对上，可以顺着下面这条线看：

State.getTasks() 生成 dict[str, Task]
每个 Task 提供一个 matchPos
State.updateRole() 根据 matchStr 分组
DoMunkresMatch(tasks_to_assign, ourExistVehicles) 计算分配
结果写回 task.num 和 Global.roleNumberStructTable

所以当你觉得“为什么这帧 L 突然换车了”，别先去怪 Skill.py，先回来看：

matchStr 有没有允许它重匹配；
matchPos 这帧有没有变化；
场上有效车号集合有没有变化；
某个角色是不是被 fixedNumber 抢占了。

这样排查通常比盲看现象快得多。