集合覆盖问题(Set Covering)

假设某个广播节目在播出时要尽可能覆盖每个地方, 现有一些广播电台, 每个电台能在某几个地方播出, 电台播出范围有重合, 在怎么选择使用最少的电台覆盖到最多的地方

一种方法是使用贪婪算法, 但有可能不是最佳解, 近似最佳解

贪婪算法每次的选择都尽可能覆盖到最多的地方, 重复这个直到全部地方被覆盖完

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
state_needed = set(['mt', 'wa', 'or', 'id', 'nv', 'ut', 'ca', 'az'])
# 各个电台广播可以覆盖到的地方
stations = {
    'kone': set(['id', 'nv', 'ut']),
    'ktwo': set(['wa', 'id', 'mt']),
    'kthree': set(['or', 'nv', 'ca']),
    'kfour': set(['nv', 'ut']),
    'kfive': set(['ca', 'az'])
}


def greedy_set_covery(covering, covered):
    # 最后选出的集合
    final_covered_set = set()
    needed_covered = covered
    all_covering = covering

    while needed_covered:
        most_covered_numbers = 0
        for item in all_covering:
            intersection = all_covering[item] & needed_covered
            if len(intersection) > most_covered_numbers:
                best_covered = item
                most_covered_numbers = len(intersection)
                print(best_covered)
        # 如果有某个点无法覆盖时, 返回 None
        if most_covered_numbers == 0:
            return None
        final_covered_set.add(best_covered)
        needed_covered -= covering[best_covered]
        covering.pop(best_covered)
    return final_covered_set

covered_set = greedy_set_covery(stations, state_needed)
print(covered_set)