本文介绍如何在 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 算法工程复杂度高，对于中等规模数据（< 1000 人），推荐采用 DFS 增广路算法（Hungarian-style），时间复杂度 O(V·E)，简洁高效：
立即学习“Java免费学习笔记（深入）”；
// 构建邻接表：agentIndex -> list of indices of available agents from other teams
List<List<Integer>> graph = new ArrayList<>();
Map<String, List<Integer>> teamToIndices = new HashMap<>(); // team -> list of available agent indices
// 预处理：收集所有 available agent 的索引，并按 team 分组
for (int i = 0; i < agents.size(); i++) {
Agent a = agents.get(i);
if (Boolean.TRUE.equals(a.isAvailable())) {
graph.add(new ArrayList<>());
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 < agents.size(); i++) {
if (!Boolean.TRUE.equals(agents.get(i).isAvailable())) continue;
String iTeam = agents.get(i).getTeam();
teamToIndices.forEach((team, indices) -> {
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 < agents.size(); u++) {
if (!Boolean.TRUE.equals(agents.get(u).isAvailable())) continue;
boolean[] visited = new boolean[agents.size()];
if (dfs(u, visited, match, graph)) result++;
}
// 辅助 DFS 函数
boolean dfs(int u, boolean[] visited, int[] match, List<List<Integer>> 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, Agent>> pairs = new ArrayList<>();
Set<Integer> paired = new HashSet<>();
for (int i = 0; i < match.length; i++) {
if (match[i] != -1 && !paired.contains(i) && !paired.contains(match[i])) {
pairs.add(new Pair<>(agents.get(i), agents.get(match[i])));
paired.add(i);
paired.add(match[i]);
}
}
List<Agent> unpaired = new ArrayList<>();
for (int i = 0; i < agents.size(); i++) {
if (Boolean.TRUE.equals(agents.get(i).isAvailable()) && !paired.contains(i)) {
unpaired.add(agents.get(i));
}
}关键注意事项
- 去重与对称性：match[u] = v 与 match[v] = u 是同一对，遍历时需用 paired 集合避免重复添加；
- JSON 解析健壮性：使用 Jackson 时，确保 Boolean available 字段能正确反序列化 true/false/null（建议用 @JsonInclude(Include.NON_NULL) + Boolean 而非 boolean）；
- 性能边界：若 Agent 总数超 5000，建议改用 Hopcroft-Karp（O(√V·E)）或引入团队间队列轮询的近似贪心（如优先匹配稀缺团队）；
- 业务扩展性：后续如需支持“偏好权重”“禁止配对名单”，可平滑过渡至带权二分图匹配（Kuhn-Munkres 算法）。
最终，该方案不仅能输出最大数量的有效配对（如示例中可得 3 对），还能清晰列出所有落单的可用人员（如某团队只剩 1 人且其余团队无可配者），真正实现“匹配最大化 + 透明化未匹配原因”。
