量化約束滿足問題相變現象研究

《量化約束滿足問題相變現象研究》是依託東北師範大學，由王佳男擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：量化約束滿足問題相變現象研究
• 項目類別：青年科學基金項目
• 項目負責人：王佳男
• 依託單位：東北師範大學

項目摘要

儘管對經典約束滿足問題相變現象的研究已經取得了令人矚目的成績，但迄今為止，對量化約束滿足問題相變現象的研究尚存在瓶頸。對於一般的隨機量化約束滿足問題模型（如RB模型等），尚未確定其相變點位置，也未能建立問題結構與相變現象、難解性之間的關聯，目前缺乏針對一般的量化約束滿足問題相變區的有效求解算法。因此本項目將圍繞量化約束滿足問題的相變現象這一核心內容開展研究：證明量化約束滿足問題中相變現象的存在，並確定其相變點位置；研究問題結構特徵與相變現象之間的關係，為量化約束滿足問題的難解性提供理論證據，並從中確定影響量化約束滿足問題相變現象的結構特徵；通過對算法在相變臨界區失效的原因進行分析，有針對性的設計高效的量化約束滿足問題求解算法。

結題摘要

本項目圍繞量化約束滿足問題等難解問題的相變現象這一核心內容開展研究：證明這些問題相變現象的存在，並確定其相變點位置；研究問題結構特徵與相變現象之間的關係，為這些問題的難解性提供理論證據，並從中確定影響相變現象的結構特徵；通過對算法在相變臨界區失效的原因進行分析，有針對性的設計高效的難解問題求解算法。項目組在AAAI、IJCAI等國際權威會議、《Science China Information Sciences》、《Information Science》等國內外權威期刊發表學術論文13篇，包括中國計算機學會推薦A類會議論文4篇，中國計算機學會推薦B類期刊論文3篇，SCI期刊檢索論文8篇。