找到最佳结果匹配的项目集。动力组优化

Question

我遇到了这个组合问题，我试图找到 2 个项目的匹配组合的子集，从而导致总匹配数最高。 每个项目只能在一场比赛中出现一次。 在下面的示例中，我有 4 个项目。检查所有组合后，我得到的结果最终是正确还是错误。问题是找到匹配次数最多的选项。在本例中选择选项 2。 在我的例子中，项目数量最多为 100 个。我已经使用经过测试的组合的 Powerset 编写了一个强力解决方案，但是对于大量项目而言，它花费的时间太长。我正在查看来自谷歌的 python OR-tools，但不确定如何将我的问题转化为示例之一。这个问题如何称为“我正在尝试解决”？你能指出我正确的方向吗？

谢谢！

[1, 2, 3, 4]

1 - 2 false
1 - 3 true
1 - 4 true
2 - 3 true
2 - 4 false
3 - 4 true

Option 1
1 - 3

Option 2
1 - 4
2 - 3

Option 3
3 - 4

根据下面的答案，我创建了这个工作代码。

import networkx as nx

# List of items
items = [1, 2, 3, 4]

# Create a bipartite graph
G = nx.Graph()

all_matching = [(1, 3), (1, 4), (2, 3), (3, 4)]

# Add nodes for the two partitions (left and right)
G.add_nodes_from(items, bipartite=0)
G.add_nodes_from(items, bipartite=1)

# Add edges connecting items to pairs they belong to
for item, pair in all_matching:
    G.add_edge(item, pair)

# Find the maximum matching
matching = nx.max_weight_matching(G)

print(matching)

Answer 1

您可以将问题表述为最大二分匹配问题。您可以使用 Edmonds-Karp 或 Dinic 算法等网络流算法来查找二分图中的最大匹配。在您的情况下，这些项目可以被视为图中的节点，并且您可以在可以形成有效匹配的项目之间创建边。

以下是如何解决此问题的高级概述：

将问题表示为二部图：

创建一个图表，其中每个项目都表示为一个节点。 连接可以与边形成有效匹配的节点（项）。 为边缘分配容量：

为每个边分配容量 1，因为每个项目只能使用一次。 找到最大匹配：

使用最大流算法寻找二分图中的最大匹配。

如果您正在寻找 python 库，请检查 NetworkX :

查看更多详细信息：GeeksforGeeks

Answer 2

所以使用CP-SAT，

为每个真实匹配创建 1 个布尔变量。

For each value in [1, 2, 3, 4]
  AddAtMostOne(all matching bool vars using that value)

Maximize(sum(Boolean var))