如何使用贪心算法求解最小击中集

Question

有一个区间集N，中间有若干段闭区间。有一个点集P（数集合），如果P含有的任意数字包含在一段闭区间内，则称该区间被击中。
最小击中集：如果对于N中的任意一个区间，P中都存在一个点可以击中该集合，且要求P中的点尽可能少。
给出一个算法，求P中最小有多少个点，写出伪代码，并证明其正确性。

Answer 1

引自免费微信小程序：皆我百晓生

要解决这个问题，我们可以设计一个基于贪心策略的算法。贪心算法的核心思想是局部最优选择，希望通过一系列的局部最优选择达到全局最优解。对于求解最小击中集问题，我们可以通过以下步骤实现：

算法步骤

1. 初始化：创建一个空集合作为结果集 P，用于存储最终的点集。
2. 排序：将所有区间按照右端点从小到大进行排序。这是关键一步，因为我们要从最“早结束”的区间开始考虑。
3. 遍历区间：依次遍历排序后的每个区间。
   • 对于当前遍历到的区间，检查它是否已经被先前加入到集合 P 中的点所覆盖。
   • 如果当前区间未被覆盖，那么选择该区间的右端点加入到 P 集合中，保证了局部最优性。
4. 重复步骤3，直到所有区间都被考虑过。

伪代码

def min_hit_set(intervals):
    # Step 1: Initialize the result set P as an empty list
    P = []

    # Step 2: Sort intervals based on their right endpoints
    intervals.sort(key=lambda x: x[1])

    # Step 3: Iterate over each interval
    for interval in intervals:
        start, end = interval
        # Check if the current interval is not covered by any point in P
        if not any(start <= p <= end for p in P):
            # If not covered, add the right endpoint of the current interval to P
            P.append(end)

    return P

正确性证明

• 局部最优性：每次选择都是基于当前信息下的最优决策，即选择未被覆盖的区间中最先结束的区间右端点。
• 全局最优性：由于每次选择都是基于“最早结束”的原则，这保证了我们不会错过任何一个可能的最小击中点。如果有更优的选择，它必定会出现在后续的区间中，但因为后续区间更晚结束，根据贪心策略，它不会被优先选择。

示例

假设我们有以下区间集：

• 区间集 N = [(1, 5), (3, 7), (4, 8), (6, 9)]

调用 min_hit_set(N) 后的结果将会是 [5, 8] 或者 [7, 8]，具体取决于初始排序和算法实现细节。这些点集满足条件，即每个区间至少被一个点覆盖，且点集大小尽可能小。

通过上述算法和伪代码，我们可以有效地找到最小击中集。这种方法不仅直观，而且效率高，适合处理大规模数据集。