上海理工大学学报
上海理工大學學報
상해리공대학학보
2012年
4期
389-393
,共5页
集合覆盖问题%降阶算法%上界%下界
集閤覆蓋問題%降階算法%上界%下界
집합복개문제%강계산법%상계%하계
集合覆盖问题是运筹学与计算机科学中的一个NP难题.首先将该问题转化为一个等价的二分图,给出该问题的上下界算法；接着给出该问题的数学性质,这些数学性质能降低问题的规模,加快算法的求解速度；然后将数学性质和上下界方法结合起来形成一个降阶算法,并给出了算法的时间复杂度分析.该算法不仅可以单独使用,还可以与其它算法结合起来使用达到更好的效果.最后通过多个示例进一步说明算法的原理及应用情况.
集閤覆蓋問題是運籌學與計算機科學中的一箇NP難題.首先將該問題轉化為一箇等價的二分圖,給齣該問題的上下界算法；接著給齣該問題的數學性質,這些數學性質能降低問題的規模,加快算法的求解速度；然後將數學性質和上下界方法結閤起來形成一箇降階算法,併給齣瞭算法的時間複雜度分析.該算法不僅可以單獨使用,還可以與其它算法結閤起來使用達到更好的效果.最後通過多箇示例進一步說明算法的原理及應用情況.
집합복개문제시운주학여계산궤과학중적일개NP난제.수선장해문제전화위일개등개적이분도,급출해문제적상하계산법；접착급출해문제적수학성질,저사수학성질능강저문제적규모,가쾌산법적구해속도；연후장수학성질화상하계방법결합기래형성일개강계산법,병급출료산법적시간복잡도분석.해산법불부가이단독사용,환가이여기타산법결합기래사용체도경호적효과.최후통과다개시례진일보설명산법적원리급응용정황.
