頂點(diǎn)覆蓋問題

組合優(yōu)化組合優(yōu)化問題優(yōu)化問題可以分為兩類：一類是連續(xù)變量的問題，另一類是離散變量的問題，后者稱為組合優(yōu)化問題。組合優(yōu)化問題的任務(wù)：從一個(gè)有限或可數(shù)無限集里，尋找一個(gè)使得目標(biāo)函數(shù)最優(yōu)的對(duì)象——典型地包括：一組賦值，一個(gè)集合，一個(gè)排列。組合優(yōu)化問題隨處可見，具有很強(qiáng)的工程代表性應(yīng)用。許多組合優(yōu)化問題都是NP難的：最大可滿足性（MaxSAT)問題，最大團(tuán)問題，最小頂點(diǎn)覆蓋問題，旅行商問題。。。組合優(yōu)化組合優(yōu)化問題優(yōu)化問題可以分為兩類：一類是連續(xù)變量的問題，另一類是離散變量的問題，后者稱為組合優(yōu)化問題。組合優(yōu)化問題的任務(wù)：從一個(gè)有限或可數(shù)無限集里，尋找一個(gè)使得目標(biāo)函數(shù)最優(yōu)的對(duì)象——典型地包括：一組賦值，一個(gè)集合，一個(gè)排列。組合優(yōu)化問題隨處可見，具有很強(qiáng)的工程代表性應(yīng)用。許多組合優(yōu)化問題都是NP難的：最大可滿足性（MaxSAT)問題，最大團(tuán)問題，最小頂點(diǎn)覆蓋問題，旅行商問題。。。求解NP難組合優(yōu)化問題分支限界：完備算法（保證解的最優(yōu)性），回溯搜索，遍歷解空間啟發(fā)式搜索（包括局部搜索，演化算法等）：不完備算法，迭代改進(jìn)，采樣解空間局部搜索簡單地說，局部搜索是：先產(chǎn)生一個(gè)（或一群）完整的候選解，然后進(jìn)行迭代改進(jìn)，每一步只修改解的某個(gè)局部（比如一個(gè)基本單元），直到得到一個(gè)令人滿意的解或者達(dá)到某個(gè)資源限制（一般是時(shí)間限制）。局部搜索簡單地說，局部搜索是：先產(chǎn)生一個(gè)（或一群）完整的候選解，然后進(jìn)行迭代改進(jìn)，每一步只修改解的某個(gè)局部（比如一個(gè)基本單元），直到得到一個(gè)令人滿意的解或者達(dá)到某個(gè)資源限制（一般是時(shí)間限制）。形式化一點(diǎn)說，局部搜索定義為：候選解集合（也稱搜索空間）S；目標(biāo)函數(shù)f：S->R(實(shí)數(shù)集)；初始候選解集合I；鄰域關(guān)系N:S->2^S，對(duì)于每個(gè)候選解s，N(s)={s′∈S|N(s,s′)}?S;（一般是基于候選解的海明距離，最常見的是1-海明距離鄰域）跳轉(zhuǎn)函數(shù)（Stepfunction）：定義了如何從當(dāng)前候選解跳轉(zhuǎn)到它的一個(gè)鄰居候選解局部搜索局部搜索的優(yōu)點(diǎn)：簡單；通用；容易實(shí)現(xiàn)；可擴(kuò)展性強(qiáng)；許多NP難問題在求解性能上最好的算法都是基于局部搜索什么時(shí)候使用局部搜索組合爆炸：對(duì)于NP難問題，解空間是問題規(guī)模的指數(shù)級(jí)別時(shí)間限制短，或者時(shí)間資源非常重要關(guān)于問題的領(lǐng)域知識(shí)太少接受近似解一個(gè)局部搜索的例子一個(gè)例子：最大可滿足性問題（MaxSAT）變?cè)簒1,x2,x3,…,xn文字：變?cè)蛘咂浞穸ㄐ问絰1,~x1,…子句：文字的析取x1\/~x2,x1\/x2\/~x4,….CNF公式：子句的合取，可看為一個(gè)子句集合MaxSAT（優(yōu)化問題)：給出一組（布爾）賦值，滿足最多子句。SAT（判定問題）：是否存在一組（布爾）賦值，滿足所有子句。一個(gè)局部搜索的例子一個(gè)例子：最大可滿足性問題（MaxSAT）用局部搜索求解以下MaxSAT（或SAT）實(shí)例{x1\/~x2,x1\/x2,x2\/x3,~x1\/x2\/~x3}變?cè)簒1,x2,x3,…,xn文字：變?cè)蛘咂浞穸ㄐ问絰1,~x1,…子句：文字的析取x1\/~x2,x1\/x2\/~x4,….CNF公式：子句的合取，可看為一個(gè)子句集合MaxSAT（優(yōu)化問題)：給出一組（布爾）賦值，滿足最多子句。SAT（判定問題）：是否存在一組（布爾）賦值，滿足所有子句。賦值不滿足的子句初始000x1\/x2,x2\/x3Step1001x1\/x2Step2101~x1\/x2\/~x3Step3110無（找到最優(yōu)解）局部搜索的循環(huán)問題局部搜索的循環(huán)問題重復(fù)訪問（近期剛訪問過的）候選解花費(fèi)很長時(shí)間在解空間的某個(gè)區(qū)域（比如某個(gè)局部最優(yōu)附近的區(qū)域）搜索導(dǎo)致：容易陷入局部最優(yōu)，花費(fèi)太多時(shí)間在做無效搜索。。。很多局部搜索的文獻(xiàn)其實(shí)都是圍繞如何解決這個(gè)問題循環(huán)問題不可能完全避免這是由局部搜索的無記憶性決定的不可能增加一個(gè)記憶機(jī)制來記住訪問過的候選解，空間時(shí)間要求都太龐大局部搜索的循環(huán)問題局部搜索的循環(huán)問題重復(fù)訪問（近期剛訪問過的）候選解花費(fèi)很長時(shí)間在解空間的某個(gè)區(qū)域（比如某個(gè)局部最優(yōu)附近的區(qū)域）搜索導(dǎo)致：容易陷入局部最優(yōu)，花費(fèi)太多時(shí)間在做無效搜索。。。很多局部搜索的文獻(xiàn)其實(shí)都是圍繞如何解決這個(gè)問題循環(huán)問題不可能完全避免這是由局部搜索的無記憶性決定的不可能增加一個(gè)記憶機(jī)制來記住訪問過的候選解，空間時(shí)間要求都太龐大已有的（通用）方法隨機(jī)游動(dòng)重啟以一定條件（如概率）允許非改進(jìn)步Tabu策略：禁止反轉(zhuǎn)近期內(nèi)（t步內(nèi)）所做的改動(dòng)加權(quán)方法改變能量地圖格局檢測(cè)相關(guān)概念：解的基本單元一般稱為解部件(solutioncomponent)：在最大團(tuán)問題中是一個(gè)點(diǎn)，在可滿足性問題中是一個(gè)變?cè)?。。。解部件的賦值：例如，點(diǎn){選中，沒選中},變?cè)獅true,false}格局檢測(cè)相關(guān)概念：解的基本單元一般稱為解部件(solutioncomponent)：在最大團(tuán)問題中是一個(gè)點(diǎn)，在可滿足性問題中是一個(gè)變?cè)?。。。解部件的賦值：例如，點(diǎn){選中，沒選中},變?cè)獅true,false}格局檢測(cè)（configurationchecking，簡稱CC）的直觀理解：無法記憶整個(gè)解，但可以記憶每個(gè)解部件的環(huán)境及其變化。通過檢測(cè)解部件的環(huán)境，減少解的局部結(jié)構(gòu)上的循環(huán)，以此減少整個(gè)搜索的循環(huán)問題。對(duì)于一個(gè)解部件x，如果從上次x改變賦值之后，x的環(huán)境沒有改變過，那么禁止x變回原來的賦值。格局檢測(cè)是一種從空間（或結(jié)構(gòu)）上考慮的禁忌策略格局檢測(cè)解部件的格局我們把解部件的環(huán)境信息稱為它的格局，可以有不同的定義最常見的是：一個(gè)解部件的格局，是一個(gè)由它的鄰居解部件的賦值構(gòu)成的向量。格局檢測(cè)解部件的格局我們把解部件的環(huán)境信息稱為它的格局，可以有不同的定義最常見的是：一個(gè)例子：CCforSAT鄰居變量：如果兩個(gè)變量出現(xiàn)在同一個(gè)子句中，稱他們是鄰居。變量x的格局：一個(gè)由x的所有鄰居變量的賦值構(gòu)成的向量。一個(gè)解部件的格局，是一個(gè)由它的鄰居解部件的賦值構(gòu)成的向量。格局檢測(cè)用于SAT問題CCforSAT：對(duì)于一個(gè)變量v，如果從上次v改變賦值之后，v的格局沒有改變過，那么禁止v變回原來的賦值。頂點(diǎn)覆蓋問題頂點(diǎn)覆蓋：對(duì)于一個(gè)無向圖，一個(gè)頂點(diǎn)覆蓋是一個(gè)頂點(diǎn)子集，使得每條邊都至少有一個(gè)點(diǎn)屬于該集合。最小頂點(diǎn)覆蓋問題：給定一個(gè)無向圖，找出最小的頂點(diǎn)覆蓋。格局檢測(cè)用于頂點(diǎn)覆蓋問題最小頂點(diǎn)覆蓋問題可以通過迭代解決其判定問題來求解當(dāng)找到一個(gè)規(guī)模為k的頂點(diǎn)覆蓋時(shí)，繼續(xù)尋找一個(gè)規(guī)模為k-1的頂點(diǎn)覆蓋。算法核心：對(duì)一個(gè)整數(shù)k，找一個(gè)規(guī)模為k的頂點(diǎn)集合覆蓋所有的邊。初始的時(shí)候，構(gòu)造一個(gè)規(guī)模為k的頂點(diǎn)集合（候選解）。局部搜索的每一步交換集合中的一點(diǎn)和集合外的一點(diǎn)。格局檢測(cè)用于頂點(diǎn)覆蓋問題最小頂點(diǎn)覆蓋問題可以通過迭代解決其判定問題來求解當(dāng)找到一個(gè)規(guī)模為k的頂點(diǎn)覆蓋時(shí)，繼續(xù)尋找一個(gè)規(guī)模為k-1的頂點(diǎn)覆蓋。算法核心：對(duì)一個(gè)整數(shù)k，找一個(gè)規(guī)模為k的頂點(diǎn)集合覆蓋所有的邊。初始的時(shí)候，構(gòu)造一個(gè)規(guī)模為k的頂點(diǎn)集合（候選解）。局部搜索的每一步交換集合中的一點(diǎn)和集合外的一點(diǎn)。格局檢測(cè)：對(duì)一個(gè)頂點(diǎn)v，如果從上次v被移出候選解之后，v的格局沒有改變過，那么禁止把v重新加入候選解。格局檢測(cè)更一般的說，格局檢測(cè)（CC）是一種思想不同的格局定義

不同的CC策略。比如對(duì)SAT問題，變量的格局還可以定義為：變量的關(guān)聯(lián)子句的狀態(tài)構(gòu)成的向量。不同的檢測(cè)方法

不同的CC策略。比如量化CC，以格局改變的幅度作為選擇解部件的一個(gè)優(yōu)先序法則。不同的格局定義，禁忌強(qiáng)度不同?？梢栽O(shè)計(jì)多層次的CC策略。格局檢測(cè)格局檢測(cè)已經(jīng)被使用于多個(gè)組合優(yōu)化問題SAT，MaxSAT，頂點(diǎn)覆蓋，最大團(tuán)，圖著色，集合覆蓋，支配集，刻度劃分問題等等。從2011年提出到目前已經(jīng)產(chǎn)生20幾篇論文（包括其他團(tuán)隊(duì)）。格局檢測(cè)對(duì)SAT領(lǐng)域產(chǎn)生極大影響2013年SAT比賽隨機(jī)組接近40%的solver使用該技術(shù)；最近三年，共有6個(gè)獲獎(jiǎng)SATsolver使用該技術(shù)，包括2個(gè)第一，2個(gè)第二，2個(gè)第三；最近兩年，非完備算法組獲獎(jiǎng)的MaxSAT

solver大都采用了格局檢測(cè)。AAAI2013年關(guān)于SAT方面的TutorialForum評(píng)價(jià)“Itisoutstanding.Itislikelychangingthegame.”機(jī)遇和挑戰(zhàn)把格局檢測(cè)（CC）用于提高原有局部搜索算法容易實(shí)現(xiàn)，開銷?。ǜ咝?shí)現(xiàn)CC策略參考本人在AIJournal2011和AIJournal2013的兩篇論文）可以普遍用于各種組合優(yōu)化問題嘗試不同的CC策略，總有一款適合你

（比如對(duì)于SAT問題已有4種CC策略：基于鄰居變量的CC，基于關(guān)聯(lián)子句的CC，量化CC，雙層CC）機(jī)遇和挑戰(zhàn)把格局檢測(cè)（CC）用于提高原有局部搜索算法容易實(shí)現(xiàn)，開銷?。ǜ咝?shí)現(xiàn)CC策略參考本人在AIJournal2011和AIJournal2013的兩篇論文）可以普遍用于各種組合優(yōu)化問題嘗試不同的CC策略，總有一款適合你

（比如對(duì)于SAT問題已有4種CC策略：基于鄰居變量的CC，基于關(guān)聯(lián)子句的CC，量化CC，雙層CC）格局檢測(cè)的理論分析目前只得到一個(gè)結(jié)果從理論上證明格局檢測(cè)的有效性？需要理論工作！參考文獻(xiàn)關(guān)于格局檢測(cè)（CC）的更多信息，請(qǐng)參考以下文獻(xiàn)Localsearchwithedgeweightingandconfigurationcheckingheuristicsforminimumvertexcover.Artif.Intell.175(9-10):1672-1696(2011)LocalsearchforBooleanSatisfiabilitywithconfigurationcheckingandsubscore.Artif.Intell.204:75-98(2013)ClauseStatesBasedConfigurat