防晒证明严谨证明

贪心算法的严谨证明：区间与点配对问题

在算法问题中，我们经常遇到需要在数轴上将一组区间与一组点进行配对，以实现配对数量最大化的场景。一个直观的贪心策略是：优先考虑那些“限制性”更强的区间。本文将详细阐述并证明一个经典的贪心算法：将所有区间按右端点升序排序，然后依次为每个区间选择其范围内最靠左的可用点进行配对。我们将使用交换论证（Exchange Argument）方法，一步步揭示该策略为何能够导出全局最优解。

问题描述

给定数轴上的一组区间集合 $I = \{i_1, i_2, \dots, i_m\}$ 和一组点集合 $P = \{p_1, p_2, \dots, p_n\}$。

• 每个区间 $i_k$ 表示为 $[l_k, r_k]$。
• 一个区间 $i_k$ 和一个点 $p_j$ 可以配对，当且仅当 $l_k \le p_j \le r_k$。

目标是找到一个规模最大的配对集合 $M \subseteq I \times P$，满足以下条件：

1. 集合 $M$ 中的每个区间至多被使用一次。
2. 集合 $M$ 中的每个点至多被使用一次。
3. 对于 $M$ 中的任一配对 $(i_k, p_j)$，必须满足 $p_j \in [l_k, r_k]$。

贪心策略

我们提出以下贪心策略来解决此问题：

1. 排序区间： 将所有区间 $i_k \in I$ 按照其右端点 $r_k$ 从小到大进行升序排序。
2. 迭代配对： 依次遍历排序后的区间。对于当前区间 $i = [l, r]$，从所有它能覆盖且尚未被配对的点中，选择位置最靠左（坐标值最小）的点 $p^*$ 与之配对。
3. 更新状态： 如果找到了这样的点 $p^*$，则记录配对 $(i, p^*)$，并将点 $p^*$ 标记为“已配对”。处理下一个区间，直到所有区间都被考察完毕。

策略核心思想： 按右端点排序，意味着我们优先处理那些“即将结束”的区间。为这些区间选择最左边的点，是为了将“更靠右”的点资源留给那些右端点更大的区间，因为后者有更大的灵活性去覆盖靠右的点。

正确性证明：交换论证

我们将使用经典的交换论证 (Exchange Argument) 来证明上述贪心策略的正确性。证明的核心是表明，贪心算法做出的每一步选择，都可以被包含在某个最优解中。

设 $S_G$ 是由我们的贪心策略产生的配对集合。 设 $S_{OPT}$ 是任意一个最优解（即规模最大的配对集合）。

我们的目标是证明 $|S_G| = |S_{OPT}|$。

核心引理：贪心选择性质 (Greedy Choice Property)

贪心策略的第一步选择是“安全”的，即它存在于某个最优解中。

证明： 令贪心策略做出的第一个选择为 $g_1 = (i_1, p_1)$，其中：

• $i_1$ 是所有区间中右端点 $r_1$ 最小的区间。
• $p_1$ 是 $i_1$ 所能覆盖的、所有可用点中最靠左的点。

现在，我们来分析最优解 $S_{OPT}$：

情况 1：$S_{OPT}$ 包含了贪心选择 $g_1$ 如果 $(i_1, p_1) \in S_{OPT}$，那么贪心选择已经是该最优解的一部分，引理成立。

情况 2：$S_{OPT}$ 不包含贪心选择 $g_1$ 如果 $(i_1, p_1) \notin S_{OPT}$，则必然存在以下两种子情况之一：

子情况 2a：$i_1$ 在 $S_{OPT}$ 中未被配对 由于 $S_{OPT}$ 是最优解，如果点 $p_1$ 也未被配对，我们可以直接将 $(i_1, p_1)$ 加入 $S_{OPT}$，得到一个规模更大的解，这与 $S_{OPT}$ 的最优性矛盾。因此，$p_1$ 必然在 $S_{OPT}$ 中与另一个区间 $i'_1$ 配对，即 $(i'_1, p_1) \in S_{OPT}$。

我们可以构造一个新的解 $S'_{OPT}$：

在这个新解中，我们将 $p_1$ 的配对对象从 $i'_1$ 换成了 $i_1$。由于 $p_1 \in i_1$，新配对 $(i_1, p_1)$ 是合法的。$S'_{OPT}$ 的规模与 $S_{OPT}$ 相同，因此它也是一个最优解，并且它包含了贪心选择 $g_1$。

子情况 2b：$i_1$ 在 $S_{OPT}$ 中与另一个点 $p'_1$ 配对 即 $(i_1, p'_1) \in S_{OPT}$，且 $p'_1 \ne p_1$。 同时，由于 $p_1$ 是一个必须考虑的点（否则可加入 $(i_1, p_1)$ 提升解），它必然在 $S_{OPT}$ 中与另一个区间 $i'_1$ 配对，即 $(i'_1, p_1) \in S_{OPT}$。

我们已知：

1. 根据贪心选择，$p_1$ 是 $i_1$ 覆盖的最左点，所以 $p_1 < p'_1$。
2. 根据贪心选择，$i_1$ 是右端点最小的区间，所以 $r_{i_1} \le r_{i'_1}$。

现在，我们执行一次交换操作，构造新解 $S'_{OPT}$：

这个操作的本质是：让 $i_1$ 与 $p_1$ 配对（满足贪心选择），让 $i'_1$ 与 $p'_1$ 配对。

新解 $S'_{OPT}$ 的规模与 $S_{OPT}$ 相同。我们只需验证新的配对 $(i'_1, p'_1)$ 是否合法，即 $p'_1$ 是否在区间 $i'_1 = [l_{i'_1}, r_{i'_1}]$ 内。

• 验证左边界：

  • 因为 $(i'_1, p_1) \in S_{OPT}$ 是合法配对，所以 $l_{i'_1} \le p_1$。
  • 我们已知 $p_1 < p'_1$。
  • 因此，$l_{i'_1} \le p_1 < p'_1$，左边界条件 $l_{i'_1} \le p'_1$ 成立。

• 验证右边界：

  • 因为 $(i_1, p'_1) \in S_{OPT}$ 是合法配对，所以 $p'_1 \le r_{i_1}$。
  • 我们已知 $r_{i_1} \le r_{i'_1}$。
  • 因此，$p'_1 \le r_{i_1} \le r_{i'_1}$，右边界条件 $p'_1 \le r_{i'_1}$ 成立。

两个边界条件均成立，证明新配对 $(i'_1, p'_1)$ 是合法的。 我们成功地将任意一个不含 $g_1$ 的最优解 $S_{OPT}$ 转化为了一个包含 $g_1$ 的、规模相同的新最优解 $S'_{OPT}$。

综上所述，贪心选择 $g_1$ 是一个安全选择。

最优子结构与归纳

证明了第一个贪心选择是安全的之后，我们实际上将原问题转化为了一个规模更小的子问题。 将 $i_1$ 和 $p_1$ 从各自的集合中移除，剩下的问题是在 $I \setminus \{i_1\}$ 和 $P \setminus \{p_1\}$ 中寻找最大配对。我们已经证明，存在一个最优解，其剩余部分 $S'_{OPT} \setminus \{g_1\}$ 正是这个子问题的最优解。

由于原问题具有最优子结构 (Optimal Substructure)，并且我们证明了每一步的贪心选择都是安全的，通过数学归纳法可以得出，将此贪心策略执行到底，所得到的解 $S_G$ 的规模必然与最优解 $S_{OPT}$ 的规模相等。

结论

通过严谨的交换论证，我们证明了“按右端点排序，为每个区间选择最左边的可用点”这一贪心策略的正确性。它确保了在每一步决策时，都为后续的区间留下尽可能多的选择空间，从而导出全局最优解。这个例子是理解贪心算法设计和证明的经典范例。