algorithm - 在完全二部图中找到第二个最大加权匹配

Question

给定一个带权完全二分图 G=(V, U, E)，最大加权二分匹配问题，即分配问题，旨在找到 G 中边权值之和最大的匹配。我知道有一些方法(例如匈牙利算法)可以解决这个问题。现在，我想解决一个稍微不同的问题:

给定一个带权的完全二分图G=(V, U, E)，我想同时求出G中最大的带权二分匹配和次大的带权二分匹配。任何想法将不胜感激。

Answer 1

有一种称为 Lawler-Murty 的通用算法，可让您在连续调用中找到组合算法(包括匹配)的前 K 个答案。在 https://core.ac.uk/download/pdf/82129717.pdf 中进行了描述在匹配的上下文中。

基本上，在找到最佳答案后，您可以为问题添加约束条件，从而产生许多子问题，从而排除目前找到的答案，但所有其他答案仍会作为以下问题之一的答案出现子问题。第二个最佳答案将成为其中一个子问题的最佳答案。当你反复这样做时，你最终会遇到一大堆需要解决的子问题。对于匹配问题，您可以利用以前问题的一些工作来减少解决子问题所需的时间。