吳歆韻 彭瑞 熊才權(quán)

［摘要］ 將最小支配集問題轉(zhuǎn)換為一系列判定問題[CD2]k支配集問題，并提出一種禁忌遺傳混合算法對(duì)k-DS問題進(jìn)行求解。此算法將禁忌搜索算法和遺傳算法兩種啟發(fā)式算法結(jié)合起來，互補(bǔ)不足。高效的鄰域結(jié)構(gòu)保證了算法的運(yùn)行效率，禁忌策略防止算法過早陷入局部最優(yōu)陷阱，遺傳算法框架進(jìn)一步增強(qiáng)了算法的疏散性。經(jīng)過與現(xiàn)有求解最小支配集算法的結(jié)果進(jìn)行分析比較，禁忌遺傳混合算法的結(jié)果較其它算法更優(yōu)。

［關(guān)鍵詞］ 最小支配集； NP難問題； 禁忌遺傳混合算法； k支配集

［中圖分類號(hào)］ TP393［文獻(xiàn)標(biāo)識(shí)碼］ A