本文關鍵詞：交互約束滿足問題的沖突解釋算法研究

  更多相關文章： 交互約束滿足問題 沖突解釋算法 捆綁

【摘要】：約束滿足問題是人工智能領域的一個重要分支,其表示形式是一個很好的框架,可以用來表示一系列現(xiàn)實問題,例如:配置問題,航班調(diào)度,資源分配等。約束傳播和回溯搜索是約束滿足問題的兩個主要技術。交互約束滿足是一種特殊的約束滿足問題,交互約束滿足問題是指在計算開始時問題模型還沒有被完整定義,但是可以在計算過程中交互的傳遞信息。在交互約束滿足問題求解過程中用戶指定一些約束,這些用戶約束代表著用戶的需求。求解解釋是交互約束滿足問題中的一個研究熱點。解釋可以用于恢復相容性、避免不受歡迎的特性或者恢復一個已經(jīng)排除的特性。目前的求解解釋算法主要分兩類:基于解的解釋算法和基于沖突的解釋算法。基于解的解釋算法是修正用戶約束集合的一個子集,使約束網(wǎng)絡能夠得到一個解;基于沖突的解釋算法是給出導致約束網(wǎng)絡不相容的一個子集,說明沖突產(chǎn)生的原因,通常來說我們要求該子集是一個極小集合。Barry O'Callaghan的Corrective Exp和Junker的QUICKXPLAIN是兩類算法的代表。QUICKXPLAIN算法將問題域劃分為兩部分,運用遞歸的方式分別求解兩個部分的沖突元素。QUICKXPLAIN算法的時間開銷主要是在約束傳播上,若能減少約束傳播的次數(shù)和每次約束傳播的時間,即可提高算法的運行效率。本文基于QUICKPLAIN算法提出了基于捆綁的沖突解釋算法,即將m個約束捆綁為一個約束進行約束傳播,m的取值范圍是1-n,其中n為用戶約束的個數(shù);m取值為1時,即是QUICKXPLAIN算法本身。本文對m=2和m=n/2兩種情況進行了研究:(1)當m=2時,我們采用將兩個約束捆綁為一個的方式進行約束傳播,我們將該算法稱為基于雙值捆綁的沖突解釋算法。該算法可以使兩個用戶約束共用一次約束傳播的過程,這樣使得約束傳播的次數(shù)可變?yōu)樵瓉淼亩种?但是當一次約束傳播導致沖突時,需要做額外的工作來判斷兩個被捆綁的約束中到底哪個是沖突元素(有可能是其中之一,也有可能兩者均是)。(2)當m=n/2時,我們采用將用戶約束集合的二分之一捆綁為一個的方式進行約束傳播,我們將該算法稱為基于折半捆綁的沖突解釋算法。該算法將用戶約束分成兩部分,按照兩個約束的方式來判斷沖突集合所在的位置;然后運用遞歸的方式分別在兩個子問題中求解沖突集合,直到子問題中只包含一個約束時即為沖突集合中的元素。通過這種方式可以將問題域減小為原來的二分之一,并且多個約束同時傳播,可在一定程度上減少每次約束傳播的時間。理論上,根據(jù)用戶約束集合和沖突約束集合的大小不同,我們不能保證哪一算法在所有情況下都是最優(yōu)的。但是實驗結(jié)果顯示,在實際問題中,我們提出的兩種算法效率均高于QUICKXPLAIN算法,其中大多數(shù)情況下基于折半捆綁的沖突解釋算法的效率高于基于雙值捆綁的沖突解釋算法。
【關鍵詞】：交互約束滿足問題 沖突解釋算法 捆綁
【學位授予單位】：吉林大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：TP18
【目錄】：

• 摘要4-6
• Abstract6-10
• 第1章 緒論10-13
• 1.1 研究背景與現(xiàn)狀10-11
• 1.2 本文工作及結(jié)構11-13
• 第2章 約束滿足問題及求解技術13-25
• 2.1 約束滿足問題13-14
• 2.2 相容性技術14-22
• 2.2.1 弧相容算法15-17
• 2.2.2 路徑相容算法17-18
• 2.2.3 限定路徑相容算法18-21
• 2.2.4 單弧相容21-22
• 2.3 MAC算法22-25
• 第3章 交互約束滿足問題及解釋算法25-34
• 3.1 交互約束滿足問題及其解釋25-28
• 3.2 QUICKXPLAIN算法28-34
• 第4章 基于捆綁的沖突解釋算法34-48
• 4.1 基于雙值捆綁的沖突解釋算法35-40
• 4.2 基于折半捆綁的沖突解釋算法40-44
• 4.3 實驗結(jié)果及分析44-48
• 第5章 總結(jié)與展望48-50
• 參考文獻50-53
• 作者簡介53-54
• 致謝54

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 郭冬芬;李鐵克;;基于約束滿足的煉鋼批量計劃的制定方法[J];微計算機信息;2007年12期

2 湯萍萍;王紅兵;;基于層次約束滿足的產(chǎn)品選擇算法[J];現(xiàn)代計算機(專業(yè)版);2007年08期

3 谷學強;陳t，

本文編號：892813