合作解谜中,不同角色可能只会处理部分机关。按角色顺序分配第一个可用机关很直观,却可能把唯一合适的位置占走。重新安排已有分工有时才能让更多人同时工作。
六名角色与六个机关用零到五编号,每人最多负责一个机关,每个机关最多由一人负责。表内列出角色能够操作的机关,目标只求参与人数最多,不比较移动距离或完成速度。
角色0可操作[2, 5] 角色1可操作[2] 角色2可操作[0, 2, 5] 角色3可操作[0, 1] 角色4可操作[2, 4, 5] 角色5可操作[1, 3, 4]
纳入角色0,能力表[2, 5],允许调整此前分工后,当前[角色,机关]为[[0, 2]],共有1名角色获得位置。
纳入角色1,能力表[2],允许调整此前分工后,当前[角色,机关]为[[0, 5], [1, 2]],共有2名角色获得位置。
纳入角色2,能力表[0, 2, 5],允许调整此前分工后,当前[角色,机关]为[[0, 5], [1, 2], [2, 0]],共有3名角色获得位置。
纳入角色3,能力表[0, 1],允许调整此前分工后,当前[角色,机关]为[[0, 5], [1, 2], [2, 0], [3, 1]],共有4名角色获得位置。
纳入角色4,能力表[2, 4, 5],允许调整此前分工后,当前[角色,机关]为[[0, 5], [1, 2], [2, 0], [3, 1], [4, 4]],共有5名角色获得位置。
纳入角色5,能力表[1, 3, 4],允许调整此前分工后,当前[角色,机关]为[[0, 5], [1, 2], [2, 0], [3, 1], [4, 4], [5, 3]],共有6名角色获得位置。
贪心分配[[0, 2], [2, 0], [3, 1], [4, 4], [5, 3]]共5人,最终匹配[[0, 5], [1, 2], [2, 0], [3, 1], [4, 4], [5, 3]]共六人。六名角色构成参与人数上限,达到六即证明最优;本例不承诺最优分配只有一种。
先记录按编号贪心分配的结果,再寻找可以挪动旧分工的增广路线。用一组互不冲突的完整分配证明可行,并检查没有角色被分到能力表之外的机关。
建议先遮住结果,用本例原始输入独立完成一遍,再逐项对照。若出现差异,先找最早不一致的位置,检查索引从零还是从一开始、边界是否包含,以及比较或更新发生的先后。只比较最后一个数,往往无法分辨规则理解与计算步骤分别出了什么问题。
这是一对一能力匹配模型,不能直接代替有时间窗口、多人协作或互斥工具的排程。若一个机关需要两人同时操作,必须把额外约束明确写进模型,不能让同一角色被重复计算。