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

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

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

圖2.1含有6個(gè)頂點(diǎn)的簡單無向圖

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

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

圖4.2一個(gè)簡單的非完美圖

本文編號(hào)：3883769