部分最大可滿足性問題（partial maximum satisfiability problem, PMS）是最大可滿足性問題（maximum satisfiability problem, MaxSAT）的泛化問題,在很多領(lǐng)域中得到廣泛應(yīng)用.目前,在工業(yè)診斷實例方面PMS求解仍有待改進(jìn),在對基于隨機(jī)搜索的PMS算法深入研究基礎(chǔ)上,本文首次提出一種結(jié)合結(jié)構(gòu)特征的隨機(jī)搜索方法 （structure characteristics partial MaxSAT, SCPMS）.首先,依據(jù)單元傳播規(guī)則結(jié)合問題結(jié)構(gòu)特征逐步將PMS問題中硬單元子句分成兩部分,從而構(gòu)造出因缺乏部分硬單元子句使得問題可滿足的子問題;提出結(jié)合結(jié)構(gòu)特征的隨機(jī)搜索指導(dǎo)策略,對新的子問題再次利用單元傳播找出原問題中的硬單元子句中硬阻塞變量,再結(jié)合子句特征翻轉(zhuǎn)相應(yīng)軟阻塞變量,從而提高隨機(jī)搜索的求解效率.實驗結(jié)果表明,提出的SCPMS與最新的兩個算法DeciDist和DistUp相比,在基于模型診斷問題（model-based diagnosis, MBD）的工業(yè)實例上, SCPMS求得的不滿足軟子句數(shù)有較大程度的減少. 

【文章來源】：中國科學(xué):信息科學(xué). 2019,49(06)北大核心CSCD

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


本文編號：3389933