《約束滿足問題的結構特徵和算法分析》是依託北京大學，由劉田擔任負責人的面上項目。
基本介紹
- 中文名：約束滿足問題的結構特徵和算法分析
- 項目負責人：劉田
- 項目類別：面上項目
- 依託單位：北京大學
項目摘要,結題摘要,
項目摘要
在約束滿足問題中要求為一組變數賦值來滿足給定的一組約束條件，這類問題覆蓋了計算機科學、人工智慧、運籌學等很多領域的重要問題。值域可變的約束滿足問題可以更好地描述實際問題，近年來逐漸引起關注，但過去在固定值域條件下取得的結論往往不能直接套用。隨機約束滿足問題通過一個隨機過程產生隨機實例，通過調整隨機過程的控制參數，可以觀察到實例性質的相變現象，包括從有解到無解的可滿足性相變、在可滿足性臨界點附近算法行為的相變等，但目前還沒有建立起可滿足性相變與難解性之間的確切關聯。本項目研究值域可變的隨機約束滿足性問題的結構特徵和算法分析，包括結構參數的取值和解空間的結構變化、各種求解算法的相變點、在算法模型和證明系統下的指數下界、近似算法和精確算法研究等，目標是比較其與固定值域的約束滿足問題的差別，刻畫值域可變的隨機約束滿足問題的難解性，建立起相變現象與難解性之間的確切聯繫，為實際套用打下堅實的理論基礎。
結題摘要
本項目用理論分析和實驗結果來研究約束滿足問題的結構特徵和算法分析，完成了研究計畫。首先，從結構分解的角度研究了隨機約束滿足問題的相變現象與難解性。RB模型是一種值域增長的隨機約束滿足問題，具有精確相變並成功構造出各種難解算例。證明了RB模型的隨機約束超圖在不同結構分解方法下（包括鉸鏈分解、樹分解、最小環割集等）在相變區漸進具有大的結構參數，有關結果在頂級會議IJCAI上口頭報告。利用腔方法研究了RB模型解空間的分簇現象，有關結果發表在重要物理學期刊PRE上。這些結果為RB模型的難解性提供了新的理論證據。此外，對隨機k-SAT、隨機Max-2-SAT、隨機k-CSP、隨機k-d-CSP、隨機#CSP、知識編譯等許多問題，也確定了可滿足性相變點的存在性或改進了參數範圍，有關結果發表在頂級期刊AIJ和SCI期刊IPL和EJC上，並在頂級會議AAAI和SAT牆報展示。其次，從算法分析的角度研究了約束滿足問題的求解效果和難解性與易解性的分類。在RB模型上研究了一致性算法、回溯算法、局部搜尋算法、訊息傳遞算法等基本算法的求解效果。提出了以變元為中心的一致性概念，確定了在RB模型上這種一致性成立的參數範圍，有關結果被SCI期刊MIND錄用。利用這種一致性可給出RB模型無回溯求解的參數範圍。利用改進的局部搜尋算法，在一個RB模型構造的難解算例的求解中取得了當前最好結果，有關結果發表在頂級期刊AIJ和在頂級會議AAAI口頭報告。證明了基於統計物理原理的訊息傳遞算法在RB模型上相變點附近依然有效，有關結果發表在重要的統計物理期刊JSTAT上和中文核心期刊中國科學上。求最小環割集是個經典的NP完全問題，可用來求約束滿足問題的後門變數。在二部圖上擴展了最小環割集問題的難解的子問題類和易解的子問題類，有關結果被重要的計算機理論期刊TCS錄用。指數時間精確算法和多項式時間近似算法是對付難解問題的經典方法。改進了背包問題在一種回溯算法模型下的指數下界，發表在期刊TCS上。把用來證明難近似性結果的UGC推廣到帶負的權值的情形，在會議COCOA上口頭報告。總之，本項目累計發表學術論文24篇（頂級期刊3篇、頂級會議5篇含口頭報告2篇和牆報3篇、SCI和EI檢索各11篇）、編著教材1部、撰寫綜述1篇、組織國內和國際會議各1次、培養或協助培養研究生6人以上。
