集合覆蓋問題不僅僅是運籌學(xué)研究中經(jīng)典的組合優(yōu)化問題,也是計算機(jī)科學(xué)問題中的一個常見問題。作為其擴(kuò)展問題的集合K覆蓋問題,在原問題的基礎(chǔ)上,增加了更多的約束,同樣也增加了問題的難度。集合K覆蓋問題已被證明是一個NP-hard問題且已經(jīng)很好地應(yīng)用于日常生活中的工程設(shè)計問題,比如網(wǎng)絡(luò)安全,資源分配,人員調(diào)動等。本文在該問題的典型求解算法上提出了一些改進(jìn)的策略方法。首先是多層打分啟發(fā)式策略方法（ML）,該策略會對各個子集進(jìn)行打分。接下來,局部搜索算法會通過子集的分值大小來選擇子集加入候選解還是從候選解中移除。另一個改進(jìn)的策略方法是定量格局檢測策略,該策略改進(jìn)了原有的格局檢測策略方法,旨在避免局部搜索算法陷入循環(huán)的同時,不僅改善了整個局部搜索路徑,跳出局部最優(yōu),也提升了解的質(zhì)量。為了更好的結(jié)合多層打分策略和定量格局檢測策略,提出了一個有效的子集選擇策略方法,并且通過整合上述提出的策略方法形成了一個有效的局部搜索算法,名為MLQCC算法。除此之外,針對集合K覆蓋問題的一些特殊情況,提出了一個有效的化簡函數(shù)來化簡集合K覆蓋問題的規(guī)模,從而在一定程度上降低了算法搜索復(fù)雜度。最后一個改進(jìn)的算法是低復(fù)雜度... 

【文章來源】：東北師范大學(xué)吉林省 211工程院校 教育部直屬院校

【文章頁數(shù)】：42 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
Abstract
第一章 緒論
    1.1 研究問題及意義
    1.2 相關(guān)工作
    1.3 本文研究內(nèi)容
    1.4 論文內(nèi)容安排
第二章 基本局部搜索算法
    2.1 基本概念和定義
    2.2 局部搜索算法求解集合K覆蓋問題
        2.2.1 打分策略
        2.2.2 格局檢測策略
    2.3 本章小結(jié)
第三章 基于多層打分和定量格局檢測的局部搜索算法
    3.1 算法框架
    3.2 化簡函數(shù)
    3.3 生成初始化解函數(shù)
    3.4 局部搜索函數(shù)
        3.4.1 多層打分啟發(fā)式
        3.4.2 定量格局檢測策略
        3.4.3 子集選擇策略
        3.4.4 局部搜索函數(shù)
    3.5 大規(guī)模例子的初始化函數(shù)
    3.6 本章小結(jié)
第四章 實驗結(jié)果與分析
    4.1 實例介紹
    4.2 實驗結(jié)果
        4.2.1 小規(guī)模例子的實驗比較
        4.2.2 與LP-MMAS-LS的實驗對比
        4.2.3 在大規(guī)模例子上的實驗結(jié)果
        4.2.4 多層打分啟發(fā)式和定量格局檢測策略的有效性
        4.2.5 MLQCC+LI在大規(guī)模例子上的實驗
第五章 總結(jié)與展望
參考文獻(xiàn)
致謝



本文編號：3497833