集合覆盖近似解问题

[复制链接]
查看11 | 回复6 | 2021-1-27 06:48:00 | 显示全部楼层 |阅读模式
一个有穷集X合一个X的子集族F,且X的每一个元素都属于F中的至少一个子集。原问题是要找一个最小规模子集C包含于F使其覆盖X的所有成员。注意C和F都是X的子集的集合。下面是该问题近似解的伪代码。
GREEDY-SET-COVER(X,F)
U←X
C←空集
whileU!=空集
doselectanS∈Fthatmaximizes|S∩U|
U←U-S
C←C∪{S}
returnC
|?|表示结合的元素个数
书上说该问题存在一个运行时间为O(∑|S|)的实现,这里求和是对所有S∈F进行
想了很久没想出来,谁来帮帮忙
分 -->
回复

使用道具 举报

千问 | 2021-1-27 06:48:00 | 显示全部楼层
我也想知道
回复

使用道具 举报

千问 | 2021-1-27 06:48:00 | 显示全部楼层
分成两步来做:
1.首先进行预处理,构造数组E
E--所有包含集合X中第i个元素的S[j]的集合,1引用2楼ThirstyCrow的回复:分成两步来做:
1.首先进行预处理,构造数组E
E--所有包含集合X中第i个元素的S[j]的集合,1
貌似我也想到过这个方法。
第二步,我觉得在第一次选择了集合S[t]以后,所有其他集合中的和S[t]重合的元素就要删掉(否则每次选取最大是不对的)。这样每选择了一个集合以后,其他集合大小就变了,也就是下一次选的时候要重新遍历所有集合。这样得到的复杂度为O(∑|S|+|C|(2|F|-|C|+1)/2)
复杂度的后半截是因为,每次选择模最大的集合S都要遍历剩余的所有集合,总的时间付出为|F|+|F|-1+...+|F|-|C|+1
下面举个特例,X={1,2,...,n},F={{1},{2},...,{n}}
这样|C|(2|F|-|C|+1)/2=n(n-1)/2,而∑|S|=n
回复

使用道具 举报

千问 | 2021-1-27 06:48:00 | 显示全部楼层
当然每个F中集合以集合中元素大小为关键字建立斐波那契堆,每次选最小的可在O(1)时间内搞定,但是每次减少集合大小需要O(lg|F|)的时间,这样总共的时间复杂度还是要O((∑|S|)*lg|F|)
回复

使用道具 举报

千问 | 2021-1-27 06:48:00 | 显示全部楼层
dffsdddddddddddddddddddddd
回复

使用道具 举报

千问 | 2021-1-27 06:48:00 | 显示全部楼层
貌似我也想到过这个方法。
第二步,我觉得在第一次选择了集合S[t]以后,所有其他集合中的和S[t]重合的元素就要删掉(否则每次选取最大是不对的)。这样每选择了一个集合以后,其他集合大小就变了,也就是下一次选的时候要重新遍历所有集合。这样得到的复杂度为O(∑|S|+|C|(2|F|-|C|+1)/2)
复杂度的后半截是因为,每次选择模最大的集合S都要遍历剩余的所有集合,总的时间付出为|F|+|F|-1+...+|F|-|C|+1
下面举个特例,X={1,2,...,n},F={{1},{2},...,{n}}
这样|C|(2|F|-|C|+1)/2=n(n-1)/2,而∑|S|=n
回复

使用道具 举报

千问 | 2021-1-27 06:48:00 | 显示全部楼层
mark
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

主题

0

回帖

4882万

积分

论坛元老

Rank: 8Rank: 8

积分
48824836
热门排行