本文介绍如何在 java 中为一组 agent 对象构建满足“同可用性、跨团队”条件的最大配对方案，并输出所有成功配对及剩余未配对人员，兼顾算法合理性与工程实用性。
本文介绍如何在 java 中为一组 agent 对象构建满足“同可用性、跨团队”条件的最大配对方案，并输出所有成功配对及剩余未配对人员，兼顾算法合理性与工程实用性。
要实现“最大化配对”，核心在于将问题建模为二分图最大匹配（Maximum Bipartite Matching）——这是组合优化中的经典场景。虽然原始需求看似简单（遍历+贪心匹配），但贪心策略（如按顺序找第一个可配对象）无法保证全局最优，尤其当团队规模严重失衡时（例如 NW 有 5 名可用成员，而 W 和 SW 合计仅 2 名），极易导致大量人员闲置。
✅ 正确建模方式如下：
- 节点划分：所有 available == true 的 Agent 构成左部节点集；
- 边定义：左部节点 a 与右部节点 b 之间存在边 ⇔ a.team != b.team（注意：无需区分左右部是否“可用”——因为仅 available == true 的人才参与配对，故右部也应严格限定为 available == true 的 Agent）；
- 目标：在该无向二分图中寻找边数最多的匹配（即互不共享顶点的边集合）。
⚠️ 常见误区纠正：答案中提及“Node set 1 = available, Node set 2 = unavailable”是错误的——不可用人员（available == false）根本不能参与配对，不应纳入图中。正确做法是：全图仅含可用人员，边仅存在于不同团队的可用人员之间，形成一个“跨团队可用人员”的无向图，再求其最大匹配（非二分图亦可，但二分图更易处理）。
推荐实现路径（轻量级、可落地）
由于 Hopcroft-Karp 或 Blossom 算法工程复杂度高，对于中等规模数据（DFS 增广路算法（Hungarian-style），时间复杂度 O(V·E)，简洁高效：
// 构建邻接表：agentIndex -> list of indices of available agents from other teams
List<list>> graph = new ArrayList();
Map<string list>> teamToIndices = new HashMap(); // team -> list of available agent indices
// 预处理：收集所有 available agent 的索引，并按 team 分组
for (int i = 0; i ());
teamToIndices.computeIfAbsent(a.getTeam(), k -> new ArrayList()).add(i);
} else {
graph.add(Collections.emptyList()); // 不可用者不参与
}
}
// 构建图：对每个可用 agent i，连接所有 team ≠ i.team 的可用 agent j
for (int i = 0; i {
if (!team.equals(iTeam)) {
graph.get(i).addAll(indices);
}
});
}
// DFS 增广路（标准最大匹配模板）
int[] match = new int[agents.size()]; // match[j] = i 表示 j 匹配到 i
Arrays.fill(match, -1);
int result = 0;
for (int u = 0; u > graph) {
for (int v : graph.get(u)) {
if (visited[v]) continue;
visited[v] = true;
if (match[v] == -1 || dfs(match[v], visited, match, graph)) {
match[v] = u;
match[u] = v; // 双向记录便于输出
return true;
}
}
return false;
}
// 输出结果
List<pair agent>> pairs = new ArrayList();
Set<integer> paired = new HashSet();
for (int i = 0; i (agents.get(i), agents.get(match[i])));
paired.add(i);
paired.add(match[i]);
}
}
List<agent> unpaired = new ArrayList();
for (int i = 0; i <h3>关键注意事项</h3>
<ul>
<li>
<strong>去重与对称性</strong>：match[u] = v 与 match[v] = u 是同一对，遍历时需用 paired 集合避免重复添加； </li>
<li>
<strong>JSON 解析健壮性</strong>：使用 Jackson 时，确保 Boolean available 字段能正确反序列化 true/false/null（建议用 @JsonInclude(Include.NON_NULL) + Boolean 而非 boolean）； </li>
<li>
<strong>性能边界</strong>：若 Agent 总数超 5000，建议改用 Hopcroft-Karp（O(√V·E)）或引入团队间队列轮询的近似贪心（如优先匹配稀缺团队）； </li>
<li>
<strong>业务扩展性</strong>：后续如需支持“偏好权重”“禁止配对名单”，可平滑过渡至带权二分图匹配（Kuhn-Munkres 算法）。</li>
</ul>
<p>最终，该方案不仅能输出最大数量的有效配对（如示例中可得 3 对），还能清晰列出所有落单的可用人员（如某团队只剩 1 人且其余团队无可配者），真正实现“匹配最大化 + 透明化未匹配原因”。</p></agent></integer></pair></string></list>Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
