《精簡有序二元決策圖的泛化研究》是依託吉林大學，由賴永擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：精簡有序二元決策圖的泛化研究
- 項目類別：青年科學基金項目
- 項目負責人：賴永
- 依託單位：吉林大學
項目摘要,結題摘要,
項目摘要
精簡有序二元決策圖是到目前為止套用最廣的知識編譯語言，其問題在於空間效率較低，很多知識庫被編譯到該語言下時對應結果會發生指數爆炸。近年來隨著知識庫的增大，該問題已成為阻礙精簡有序二元決策圖進一步套用的瓶頸。為了降低指數爆炸發生的可能性，在保持精簡有序二元決策圖已有優勢（具有完備性、規範性和較高時間效率以及存在高效編譯方法）的前提下，擬研究如何對該語言進行泛化得到具有更高空間效率的語言。為此，通過向精簡有序二元決策圖引入三類分解提出新的知識編譯語言；提出新的時間效率評估標準完善目前的評估體系，並在新體系下全面評估新語言的理論性質；為新語言設計自底向上和自頂向下兩種編譯方法；研究基於格局檢測的啟發式策略引導編譯過程提高編譯效率和編譯質量；開發新語言的程式包方便套用領域對語言的使用。本項目的研究成果有望在多個套用領域中取代精簡有序二元決策圖的作用，並對模型計數和機率推理等領域具有重要借鑑作用。
結題摘要
精簡有序二元決策圖是一種具有完備性、規範性和較高時間效率以及存在高效編譯語言，到目前為止套用最為廣泛。精簡有序二元決策圖的問題在於空間效率較低，很多知識庫被編譯到該語言下時對應編譯結果會發生指數爆炸。近年來隨著知識庫的增大，該問題已成為阻礙其進一步套用的瓶頸。 為了降低指數爆炸發生的可能性，在保持精簡有序二元決策圖已有優勢的前提下，研究了如何對該語言引入分解進行泛化得到具有更高空間效率的語言。通過引入有界分解和樹結構分解，提出兩類規範的知識編譯語言；提出了一種新的稱為操作快速性的時間效率評估標準，該標準完善目前的目標語言評估體系；在新體系下全面評估新語言的理論性質；為新語言設計自底向上和自頂向下兩種編譯方法，前者基於合取操作，後者基於DPLL；研究基於格局檢測的啟發式策略引導編譯過程提高編譯效率和編譯質量；開發了新語言的程式包方便套用領域對語言的使用。 項目期間發表論文10篇，其中，SCI期刊和一級學報論文7篇，CCF推薦為A、B類期刊和會議論文3篇。申請國家發明專利2項，授權軟體著作權1項。作為第10完成人獲得中國商業聯合會科學技術獎一等獎1項。本項目的研究成果有望在多個套用領域中取代精簡有序二元決策圖的作用，並對模型計數和機率推理等領域具有重要借鑑作用。
