《計數約束滿足問題的相變現象研究》是依託東北師範大學，由殷明浩擔任項目負責人的面上項目。
基本介紹
- 中文名：計數約束滿足問題的相變現象研究
- 項目類別：面上項目
- 項目負責人：殷明浩
- 依託單位：東北師範大學
項目摘要,結題摘要,
項目摘要
近年來隨著計數約束滿足問題在智慧型規劃、航空航天、軟體工程等套用領域的廣泛套用，研究人員對其的關注提高到前所未有的高度。2010年圖靈獎獲得者哈佛大學的Valiant教授曾多次指出計數約束滿足等#P難問題將成為計算機科學領域未來最重要的研究論題之一。儘管對約束滿足問題的相變現象的研究已經取得了令人矚目的成功，但是對計數約束滿足問題的相變現象的研究尚屬起步階段。本項目將圍繞計數約束滿足問題的相變現象這一核心內容開展研究：研究不同隨機模型的計數約束滿足問題的相變規律，確定計數約束滿足問題相變點位置；在此基礎上，生成計數約束滿足問題的難解實例作為算法測試集；研究技術約束滿足問題的結構特徵與相變現象之間的關係，為難解性提供理論證據；有針對性的設計高效的計數約束滿足問題的求解算法。
結題摘要
計數約束滿足問題是是最早被證明為#P完全 (#P-complete)的問題，也是#P複雜類中的核心問題之一，在智慧型規劃、機率推理、航空航天、軟體工程等領域有著廣泛的套用。對計數約束滿足問題相變現象的研究不僅有助於揭示問題難解的本質，而且有助於設計高效的問題求解算法。本項目圍繞計數約束滿足問題的相變現象這一核心內容展開，包括如下幾方面內容： （1）在相變點確定方面，研究了計數約束滿足問題、約束最佳化問題、NAE k-SAT(b)問題等難解問題的相變規律，從理論和實驗角度驗證了這些問題均存在easy-hard-easy模式和相變現象，同時研究和分析了問題相變點所在區域的上界和下界。（2）在問題結構特徵與相變現象關係方面，項目組在OBDD語言的基礎上提出了多個知識編譯目標語言，分析了知識編譯目標語言和計數約束滿足問題相變現象之間的關係。此外，項目組還研究了約束圖中的超樹寬度、環割集、聯通支配集等結構特徵與相變現象和問題求解之間的難度關係，為計數約束滿足問題的難解性提供了理論證據。（3）通過研究算法在相變區失效的原因，項目組設計了求解較大規模#SMT 實例的求解算法、求解#XSAT問題的高效問題求解算法、以及求解模型計數問題的近似求解算法，此外，項目組通過研究支配集、最大加權團等問題的相變現象，設計了多個高效的問題求解器。總體來說，本項研究確定了問題相變區和難解區的上下界，是計數約束滿足問題研究領域難解性刻畫中的重要一環。另一方面，對相變現象的研究，還有助於我們設計高效的問題求解算法。
