最大可滿足性(Maximum Satisfiability,MaxSAT)問題、最大團(tuán)(Maximum Clique,MC)問題、最大公共子圖(Maximum Common induced Subgraph,MCS)問題是計算機科學(xué)中經(jīng)典的NP難問題,也是人工智能、運籌學(xué)等領(lǐng)域的經(jīng)典組合優(yōu)化問題。三個問題是解決實際問題的有效模型,其高效的完備算法的設(shè)計具有重要的理論意義和實踐意義。MaxSAT、MC和MCS的優(yōu)化目標(biāo)不同,但是都可歸約為如何解決沖突問題。沖突是指不存在合理的方案滿足給定的約束條件。MaxSAT的沖突是指在任何真值指派下均存在不滿足子句;MC的沖突是不相鄰的頂點不能同時構(gòu)建團(tuán);MCS的沖突是頂點匹配不滿足邊約束條件,構(gòu)成公共子圖的頂點匹配數(shù)降低。MaxSAT子句沖突檢測的技術(shù)可以發(fā)現(xiàn)MC、MCS問題中頂點之間隱藏的沖突關(guān)系。找到的沖突越多,分支限界算法的界的質(zhì)量越高,搜索分支越少。基于找到更多沖突、有效改進(jìn)界的思路,深入研究了以上三個代表性的NP難問題,設(shè)計了基于分支限界的高效完備算法。(1)對MaxSAT問題,提出了三個優(yōu)化沖突集的策略,有效地改進(jìn)了MaxSAT算法的下...

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

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

圖2.1含有6個頂點的簡單無向圖

圖2.2一個簡單的加權(quán)無向圖

圖2.4關(guān)聯(lián)圖的生成實例

圖4.2一個簡單的非完美圖

本文編號：3883769