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

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

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

• 摘要4-6
• Abstract6-10
• 第1章 緒論10-13
• 1.1 研究背景與現(xiàn)狀10-11
• 1.2 本文工作及結(jié)構(gòu)11-13
• 第2章 約束滿足問題及求解技術(shù)13-25
• 2.1 約束滿足問題13-14
• 2.2 相容性技術(shù)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 實(shí)驗(yàn)結(jié)果及分析44-48
• 第5章 總結(jié)與展望48-50
• 參考文獻(xiàn)50-53
• 作者簡(jiǎn)介53-54
• 致謝54

【相似文獻(xiàn)】

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

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

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

3 谷學(xué)強(qiáng);陳t，

本文編號(hào)：892813