这个问题的想法是探索无向图的所有节点及其所有邻居。
每个联合都有一个相关的权重。这个想法是用最小的重量进行最大可能的配对。
考虑到一旦结对，就不能再加入了。为了实现这个算法，使用分支定界，我必须找到一个上限和一个下限。
我的想法是有一个解决方案列表和一个部分列表，其中我介绍了所有可能的邻居对。
然后比较成本是否更低，添加到解决方案列表中。
问题是我不知道用来实现这些界限的启发式方法
伪代码有什么想法吗？
真挚地
编辑
对不起，我留下了这么开放的问题。让我用图像来解释问题。
在图像中，观察到三个联合。(1,3), (2,5), (6,4)。
这些是最佳工会。
对于最优解，必须满足一对(x,y)的并集的权重最小且“x”和“y”永远不会再匹配
我认为的一个条件是：返回列表解决方案，如果满足以下条件，则所有匹配项：
len (G.nodes ()) / 2 == len (solutions)
我使用贪心算法做到了这一点。
在所有节点上迭代并加入尚未访问且权重最小的邻居。
但是这样，我不能保证最优性。
正如 Abdallah Sobehy 在给您的评论中所写，这更像是一个公开讨论而不是一个问题，并且可能（以目前的形式）不适合 SE。但是，我会试一试，并在此处发布而不是在评论中发布，因为它很长。
对于这个讨论，让我们将您的完整无向图表示为 G(N, E)，具有节点集和边集 E。我们还假设 G 中的节点数是偶数。
无论如何，在分支定界（BAB）的背景下，你的上限自然是你最好的（最便宜的）现有（迄今为止）可行的解决方案。这样的解决方案可以很容易地在初始化时启发式地构建，例如
i. let G' = G and E'=E
ii. Choose a node, say i, randomly from G'.
iii. With i fixed, pick the edge in (i,j) in E' that minimises cost,
i.e., the cheapest edge from node i to any other node j in G'.
iv. Remove nodes i and j from G', and remove all edges associated
with nodes i and j from E'.
v. Is G' non-empty? Go to ii. Otherwise, terminate.
或者上面的一些更聪明的变化。获得的可行解决方案将是我们的初始上限，例如 UB。
现在，在 BAB 的上下文中，人们通常关注原始问题的松弛，一个可以轻松解决到最优的问题；与一些整数线性程序 (ILP) 的连续松弛进行比较，以获得一个线性程序 (LP)，该线性程序 (LP) 很容易使用单纯形法求解到最优 - 这是 BAB 的常见用途。
出于我们的目的，我们需要指定一种将您的问题放松为易于解决的形式的方法，其中这种放松形式的最优解的成本低于原始问题的成本；因此为后者提供了一个下限，比如 LB。如果我们用数学术语将问题形式化，这将变得容易得多。我们引入二进制变量 x_ij（取值 0 或 1），
x_ij := 1, if pairing between nodes i and j is used, i!=j
0, otherwise
c_ij := cost (or weight) of using edge (i, j), i!=j
其中 i, j = 1, ..., |N|, i!=j。从现在开始，让n 表示|N|，即n=|N|。
有了这个，我们可以陈述以下二进制线性程序，比如（BLP1），
minimize ∑{i = 1 to n} ∑_{j 1 to n, j!= i} (c_ij * x_ij)/2, (a)
subject to ∑{j != i} x_ij = 1, for i = 1, ..., n, (b)
x_ij ∈ {0, 1}. (c)
“/2”考虑到——以目标函数和的形式——每对将与两个非零 x_ij 变量相关联（即，计算两次）；例如，如果节点 1 和 4 是配对的，则 x_(1,4)=x_(4,1)=1。n 个约束 (b) 确保每个节点将与另一个节点完全配对。
可以通过将二元约束 (c) 替换为其连续松弛来放松该程序，即将 (c) 替换为：
x_ij ∈ [0, 1], (c')
产生以下线性程序，比如 (LP1)，到
minimize ∑{i = 1 to n} ∑_{j 1 to n, j!= i} (c_ij * x_ij)/2, (a)
subject to ∑{j != i} x_ij = 1, for i = 1, ..., n, (b)
x_ij ∈ [0, 1]. (c')
(BLP1) 的解空间显然是 (LP1) 的子空间，因此 (LP1) 的最优解产生 (BLP1) 的最优解的下界。由于 (LP1) 是一个线性程序，它可以很容易地通过 Simplex 方法解决，使用您喜欢的任何最喜欢的优化库。
现在，对于 BAB 过程，求解 (LP1) 并在其最优解中，选择一些分数 x_ij，即，一些 x_ij ∈ (0, 1)，我们将---在 (LP1) 的分支子节点中---强制（向上削减）或排除（向下削减）。让我们表示这个变量 x_ab。在这个 x_ab 变量上分支，对于图匹配问题，可以描述为：“在后续子问题中强制使用边 (a,b) 及其全权 (x_ab=1)，或强制完全排除边 (a,b) (x_ab=0) 在后续子问题中”。
x_ab 上的分支产生---来自 (LP1)--- 两个子问题，例如 (LP1down) 和 (LP1up)，具有以下形式
(LP1down)
minimize ∑{i = 1 to n} ∑_{j 1 to n, j!= i} (c_ij * x_ij)/2, (a)
subject to ∑{j != i} x_ij = 1, for i = 1, ..., n, (b)
x_ij ∈ [0, 1], (c')
x_ab = 0, (d1)
(LP1up)
minimize ∑{i = 1 to n} ∑_{j 1 to n, j!= i} (c_ij * x_ij)/2, (a)
subject to ∑{j != i} x_ij = 1, for i = 1, ..., n, (b)
x_ij ∈ [0, 1], (c')
x_ab = 1, (d2)
只需重新解决这些线性规划问题 (LP1down) 和 (LP1up)，然后迭代地重复分支/求解过程，直到可以修剪子问题，方法是：
bound: the optimal (linear programming) solution of some sub-problem
is larger than the UB of the original problem (BLP1). This mean
proceeding along such a branch will never give a better (BLP1)
solution than the best incumbent one.
optimality: optimal (linear programming) solution of some sub-problem
is binary valued -> feasible in (BLP1).
-> update UB with new best incumbent solution.
infeasibility: some sub-problem is infeasible; branching upon it will
still yield an infeasible problem.
如果你一直运行你的 BAB 过程直到终止，你将保证最优性（大问题的问题是相当易处理的）。请注意，如果节点数为奇数，则 (BLP1) 将不可行。
如果您不想诉诸线性规划技术，请尝试构建您自己的方法，将您的原始问题放松为具有以下属性的方法
然后简单地重新使用上面简要介绍的通用 BAB 方法。如果您深入了解 BAB，有几种方法可以通过选择如何选择首先处理哪些子问题（“节点选择”）或哪些变量（在正式处理中）进行分支（“分支规则”）来改进框架。