吉林大学学报(工学版)
吉林大學學報(工學版)
길림대학학보(공학판)
JOURNAL OF JILIN UNIERSITY(ENGINEERING AND TECHNOLOGY EDITION)
2007年
2期
429-432
,共4页
姚国辉%朱大铭%马绍汉%冯富宝
姚國輝%硃大銘%馬紹漢%馮富寶
요국휘%주대명%마소한%풍부보
计算机应用%随机算法%近似算法%集合覆盖
計算機應用%隨機算法%近似算法%集閤覆蓋
계산궤응용%수궤산법%근사산법%집합복개
给出了集合覆盖问题的一种随机近似算法.给定E={e1,e2,…,en)的子集的集合S和S中每个子集的权值,带权的集合覆盖问题是从S中选择费用和最小的子集使得其并集覆盖E.对E中每一个未被覆盖的元素,以某一精心设计的概率分布选择包含该元素的子集,直到E中所有元素均被覆盖,算法结束.该算法求出的覆盖的费用的期望值不超过B·opt,其中opt为最优覆盖的费用,B=max(e∈E){| L(e)|),L(e)={S |e∈s,s∈S}.算法时间复杂度为O(n),其中n为E的元素数目.
給齣瞭集閤覆蓋問題的一種隨機近似算法.給定E={e1,e2,…,en)的子集的集閤S和S中每箇子集的權值,帶權的集閤覆蓋問題是從S中選擇費用和最小的子集使得其併集覆蓋E.對E中每一箇未被覆蓋的元素,以某一精心設計的概率分佈選擇包含該元素的子集,直到E中所有元素均被覆蓋,算法結束.該算法求齣的覆蓋的費用的期望值不超過B·opt,其中opt為最優覆蓋的費用,B=max(e∈E){| L(e)|),L(e)={S |e∈s,s∈S}.算法時間複雜度為O(n),其中n為E的元素數目.
급출료집합복개문제적일충수궤근사산법.급정E={e1,e2,…,en)적자집적집합S화S중매개자집적권치,대권적집합복개문제시종S중선택비용화최소적자집사득기병집복개E.대E중매일개미피복개적원소,이모일정심설계적개솔분포선택포함해원소적자집,직도E중소유원소균피복개,산법결속.해산법구출적복개적비용적기망치불초과B·opt,기중opt위최우복개적비용,B=max(e∈E){| L(e)|),L(e)={S |e∈s,s∈S}.산법시간복잡도위O(n),기중n위E적원소수목.
