证明算法是正确的

Question

假设我们有n个卖家和m个买家按升序排序。如果s< b，我们说卖方s和买方b“匹配”。找到由匹配对组成的最大子集A(恰好只有一个买方和卖方可以匹配)。

我的算法是贪婪的，通过选择第一个卖方s1并在位置c找到第一个买方b1，使得s1 < b1并将其添加到A，然后我们移动到第二个卖方s2，并从买方中的c+1迭代，直到我们找到买方b2，使得s2 < b2。我们这样做，直到位置c等于买家列表的大小。

我只是很难证明算法是正确的。我不确定如何形式化该方法，以便很容易地看到总是能找到最优解。当我思考它的时候，它是有意义的，但同样的，正式的验证是我遇到麻烦的地方。

Answer 1

“正式的”证明是一种模糊的描述。我将粗略地勾画一个证明，其详细程度将出现在研究论文中(可能低于算法课程中问题集所需的详细程度)。

贪婪算法清楚地产生了有效的匹配。(由于形式化方法在实践中的困难，这确实是对“清楚”一词的滥用。)

为了证明这种匹配是最大尺寸的，我们通过归纳证明了以下技术声明。对于所有不大于这个大小的k，存在一个最大匹配，其中k个最少的卖家被匹配，就像贪婪匹配一样。

基本情况是k= 0。我们可以采用任何旧的最大匹配，因为语句是空的(0最少是空集)。

归纳的步骤是，对于k > 0，证明k-1的语句包含k-1的语句。存在一个最大匹配M，它符合k-1个最小卖家的贪婪解，但可能不是k-1个最小卖家的贪婪解，我们称之为sk。现在来了一个案例论证。

案例1: sk在M和贪婪解中是匹配的。让bG在贪婪的解中是sk的买家，bM在M中是sk的买家。如果bG = bM，那么我们就完成了。否则，bG < bM，因为贪婪的解决方案在所有买家中选择了最小的合格买家，只排除了s1，...，sk-1的买家(它们在M中以相同的方式匹配)。如果bG在M中可用，则将sk的买家切换为bG。否则，将bG与M中的bM互换；之前从bG购买的卖家得到了更大的买家，因此掉期是有效的。

案例2: sk在M中匹配，但在贪婪的解中不匹配。那么贪婪的解是M的子集。这是不可能的，因为sk在M中的买家在贪婪的解中是可用的(贪婪的解是最大的)。

案例3: sk在M中不匹配；某个更大的卖家匹配；将其替换为sk，然后应用其他案例之一。