计算机应用与软件
計算機應用與軟件
계산궤응용여연건
COMPUTER APPLICATIONS AND SOFTWARE
2009年
3期
128-130,133
,共4页
最小k-击中集%贪心算法%随机算法
最小k-擊中集%貪心算法%隨機算法
최소k-격중집%탐심산법%수궤산법
Franco等给出一个基于平均度数的最小3-击中集问题的贪心算法,并给出算法返回击中集规模的上界.首先将其算法推广成为求解最小k-击中集问题的贪心算法HGREEDY1(A,C),并类似地给出算法返回击中集规模的上界;然后给出基于最大度数的贪心算法HGREEDY2(A,C),并证明算法HGREEDY2(A,C)在给定条件下返回的击中集规模上界优于算法HGREEDY1(A,C);另外设计了用于求解最小k-击中集的随机算法RH(A,C),并对其性能进行平均分析;在此基础上设计一个求解最小k-击中集的随机近似算法并讨论其性质.
Franco等給齣一箇基于平均度數的最小3-擊中集問題的貪心算法,併給齣算法返迴擊中集規模的上界.首先將其算法推廣成為求解最小k-擊中集問題的貪心算法HGREEDY1(A,C),併類似地給齣算法返迴擊中集規模的上界;然後給齣基于最大度數的貪心算法HGREEDY2(A,C),併證明算法HGREEDY2(A,C)在給定條件下返迴的擊中集規模上界優于算法HGREEDY1(A,C);另外設計瞭用于求解最小k-擊中集的隨機算法RH(A,C),併對其性能進行平均分析;在此基礎上設計一箇求解最小k-擊中集的隨機近似算法併討論其性質.
Franco등급출일개기우평균도수적최소3-격중집문제적탐심산법,병급출산법반회격중집규모적상계.수선장기산법추엄성위구해최소k-격중집문제적탐심산법HGREEDY1(A,C),병유사지급출산법반회격중집규모적상계;연후급출기우최대도수적탐심산법HGREEDY2(A,C),병증명산법HGREEDY2(A,C)재급정조건하반회적격중집규모상계우우산법HGREEDY1(A,C);령외설계료용우구해최소k-격중집적수궤산법RH(A,C),병대기성능진행평균분석;재차기출상설계일개구해최소k-격중집적수궤근사산법병토론기성질.
