集合覆蓋問題的數(shù)據(jù)約簡研究
2010-12-31 00:00:00陳韜吳志勇孫樂昌張曼劉京菊
計算機(jī)應(yīng)用研究 2010年9期
摘要：針對當(dāng)前解決大規(guī)模集合覆蓋問題的算法普遍存在著效率不高的問題，提出了一套削減數(shù)據(jù)規(guī)模的約簡方法，并給出了一個能夠與其他所有解決集合覆蓋問題算法相結(jié)合的約簡算法。用Beasley提出的45個測試用例進(jìn)行試驗，結(jié)果顯示貪心算法和遺傳算法在結(jié)合了約簡算法后能夠在更少的時間內(nèi)得到更優(yōu)的解，表明該約簡方法和約簡算法可以有效提高傳統(tǒng)算法和智能算法解決大規(guī)模集合覆蓋問題的效率。
關(guān)鍵詞：集合覆蓋；約簡方法；約簡算法；貪心算法；遺傳算法
中圖分類號：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號：1001－3695(20lO)09－3307－05
