算法作业第三题，集合覆盖问题近似计算

例题：

Sample Input

1 2 3 4 5

4

1 2 3

2 4

3 4

4 5

Sample Output

2

1 4

只测试了样例一组，可能会存在问题，请谨慎参考

import java.util.*;
public class Main {
	public static ArrayList<Integer> Uaggregate = new ArrayList<Integer>();			//存放全集
	public static ArrayList<Integer> tmpAggregate = new ArrayList<Integer>();		//存放临时的集合
	public static ArrayList<Integer> tmpAgNum = new ArrayList<Integer>();			//存放临时的集合是由哪几个子集组成的
	public static ArrayList<Integer> BestAgNum = new ArrayList<Integer>();			//存放临时的集合是由哪几个子集组成的
	public static int num;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String Str = sc.nextLine();
		String[] str = Str.split(" ");
		for(int i=0;i<str.length;i++) {
			Uaggregate.add(Integer.parseInt(str[i]));			//给全集赋值
		}
		int m = sc.nextInt();
		sc.nextLine();
		num = m;
		ArrayList<Integer> subset[] = new ArrayList[m]; 
		for(int i=0;i<m;i++) {
			Str = sc.nextLine();
			str = Str.split(" ");
			subset[i] = new ArrayList<Integer>();
			for(int j=0;j<str.length;j++) {
				subset[i].add(Integer.parseInt(str[j]));		//子集赋值
			}
		}
		Recursion(subset, 0, m);						//递归遍历全部可能
		System.out.println(num);
		//转化成标准输出格式
		int[] bestAgNum = new int[BestAgNum.size()];				//存放最终最优结果的数组
		for(int i=0;i<BestAgNum.size();i++) {
			System.out.print((BestAgNum.get(i)+1)+" ");
		}
	}
	static void Recursion(ArrayList<Integer> subset[], int i, int m) {
		if(i<m-1)								//不加当前集合
			Recursion(subset, i+1, m);
		ArrayList<Integer> tmp = new ArrayList<Integer>();
		tmp = (ArrayList<Integer>) tmpAggregate.clone();
		tmpAggregate.removeAll(subset[i]);					   //加当前集合
		tmpAggregate.addAll(subset[i]);
		tmpAgNum.add(i);
		if(tmpAggregate.size()==Uaggregate.size() && tmpAgNum.size()<num) {
			BestAgNum = (ArrayList<Integer>) tmpAgNum.clone();
			num = tmpAgNum.size();
		}
		else if(tmpAgNum.size()<num && i<m-1){
			Recursion(subset, i+1, m);
		}
		tmpAggregate = (ArrayList<Integer>) tmp.clone();			//加当前集合情况下退栈
		tmpAgNum.remove(tmpAgNum.size()-1);
	}
}

问题描述：

假设你办了个广播节目，要让全美50个洲的听众都能听到，为此，你需要决定在哪些广播台播出，在每个广播台播出都需要支付费用，力图以最少的费用达到覆盖的目的——来自算法图解

 贪婪思路：1：找出所有广播台中覆盖面积最广的（面积指的是未覆盖的面积） 换言之就是寻找覆盖未覆盖面积最广的广播站

2：记录本轮的覆盖区域 更新未覆盖区域（取交集 用到集合set）

3：重复 1 2 直至完全覆盖

 初始信息：state_needed(需要覆盖的州)，stations 字典（每个广播台覆盖的州）fianl_stations(保存最终选择的广播台)

state_needed=set(['mt','wa','or','id','nv','ut','ca','az'])
stations={}
stations['1']=set(['id','nv','ut'])
stations['2']=set(['wa','id','mt'])
stations['3']=set(['or','nv','ca'])
stations['4']=set(['nv','ut'])
stations['5']=set(['ca','az'])
final_stations=set()
def find_covermost():
    ans,res=0,''
    for k,v in stations.items():
        if ans<len(v&state_needed) and k not in final_stations:ans,res=len(v),k#v&state_needed很关键，覆盖面积广指的是覆盖还没覆盖的面积最广
    final_stations.update([res])
    return stations[res]
while state_needed:
    state_needed-=find_covermost()
print(final_stations)
print(state_needed)
##输出{'5', '3', '1', '2'}
#set()

总结：贪婪算法是一种近似算法，通过寻找局部最优解获得全局最优解 

前面学到的BFS与狄克斯特拉算法就包含的贪婪的思想

另外今天学到了集合中的两个操作 并集>>&    添加元素>>set.update([seq])

我是小郑 期待和你一起进步

写这篇主要是想与线性规划求解集合覆盖问题做个性能对比，基于后者的实现方法可参考博文。

本文中数据集X及集族生成规则同上一篇，这里不再介绍。整个贪心算法解决集合覆盖问题的实现代码如下。

# 集合覆盖问题-part1-贪心算法
import time
import random
from itertools import chain
import matplotlib.pyplot as plt

# 生成有限集X
X = set()
iter_ = [100,200, 500]
time_cost = []
for n in iter_:
    start_t = time.clock()
    X = random.sample(range(1, 10000), n)
    print('集合X中元素个数：', len(X))
    print('集合X：', X)

    # 生成子集
    S0 = random.sample(X, 20)
    n1 = random.randint(1, 20)
    x1 = random.randint(1, n1)

    S1 = (random.sample(set(S0), x1))+(random.sample(set(X)-set(S0), n1-x1))
    Sub_set = [S0, S1]

    for item in range(2, n):
        S_item_len = random.randint(1, 20)
        S_last_len = random.randint(1, S_item_len)

        Sub_set_item = list(chain.from_iterable(Sub_set))  # 压平嵌套列表

        if len(set(X) - set(Sub_set_item)) >= S_item_len-S_last_len:
            S_now = (random.sample(set(Sub_set_item), S_last_len))+(random.sample(set(X)-set(Sub_set_item), S_item_len-S_last_len))
            Sub_set.append(S_now)
        else:
            Sub_set.append(list(set(X)-set(Sub_set_item)))
            break
    # print(set(X)-set(list(chain.from_iterable(Sub_set))))  # 检查集合中的元素是否已被子集族全覆盖

    for j in range(n-len(Sub_set)):
        select_num = random.randint(1, 20)
        select_sub = random.sample(X, select_num)
        Sub_set.append(select_sub)
    print('子集族：', Sub_set)

    # 定义函数返回当前子集族中元素个数最多的子集索引
    def max_len_list(sub_list):
        len_sub_list = []
        for i in range(len(sub_list)):
            len_sub_list.append(len(sub_list[i]))
        len_max_list = max(len_sub_list)
        return len_sub_list.index(len_max_list)

    # 贪心算法
    final_set = []
    while len(set(X)) > len(set(list(chain.from_iterable(final_set)))):
        # 返回当前子集族中元素最多的子集，将其加到可行解中
        max_index = max_len_list(Sub_set)
        final_set.append(Sub_set[max_index])

        # 从当前子集族中删掉被加到可行解中的子集
        del Sub_set[max_index]

    print('可行解：', final_set)

    # 记录运行时间
    end_t = time.clock()
    time_iter = end_t-start_t
    print("集合覆盖问题-基于贪心思想运行时间", time_iter)
    time_cost.append(time_iter)
    print('\n')

# 可视化
plt.plot(iter_, time_cost)
plt.show()

程序运行结果如下图

可以看出与线性规划求解该问题相比，基于贪心策略的近似算法在性能上有明显提高。