約束滿足及其分布式求解和應(yīng)用研究.pdf

1、約束滿足可以很好地描述組合求解問(wèn)題，在人工智能和計(jì)算機(jī)其他領(lǐng)域都有著廣泛的應(yīng)用，因而成為人工智能中成功的問(wèn)題求解范例之一。近來(lái)，計(jì)算機(jī)網(wǎng)絡(luò)和分布式計(jì)算環(huán)境在各領(lǐng)域的快速發(fā)展，使得很多現(xiàn)實(shí)世界中的組合求解問(wèn)題都具有了分布式的特點(diǎn)。在這一趨勢(shì)下，傳統(tǒng)的約束滿足求解方法已經(jīng)不能適應(yīng)分布式的組合問(wèn)題求解，特別是對(duì)自治Agent間需要協(xié)商求解的多Agent系統(tǒng)更是無(wú)法應(yīng)用。隨著多Agent系統(tǒng)研究的深入開(kāi)展，分布式約束滿足問(wèn)題被正式提出后，其模型

2、、求解方法、隱私保護(hù)和求解效率等理論問(wèn)題已引起人們的廣泛關(guān)注。 本文基于約束滿足求解策略，提出了一種針對(duì)網(wǎng)絡(luò)環(huán)境下半結(jié)構(gòu)化數(shù)據(jù)模式變化檢測(cè)的快速方法：此外，在對(duì)分布式約束滿足問(wèn)題及其求解方法的系統(tǒng)研究和分析基礎(chǔ)上，針對(duì)應(yīng)用中新出現(xiàn)的隱私安全需求，提出了高效的、真正分布式的隱私安全分布式約束滿足求解方法；最后，我們用該方法對(duì)基于多Agent虛擬企業(yè)中的隱私安全協(xié)商的求解問(wèn)題進(jìn)行了有益的探討。論文的主要貢獻(xiàn)和創(chuàng)新有： 1．提

3、出了一種快速的基于約束滿足求解的半結(jié)構(gòu)化數(shù)據(jù)模式變化檢測(cè)方法。 在約束滿足求解基礎(chǔ)上，以XML文檔為研究對(duì)象，為了有效地對(duì)XML數(shù)據(jù)進(jìn)行模式變化檢測(cè)，提出了一種快速的半結(jié)構(gòu)化數(shù)據(jù)模式變化檢測(cè)方法。該方法使用了有向標(biāo)記無(wú)序樹(shù)來(lái)表示XML文檔，從中抽取出頻繁子樹(shù)作為模式，并用樹(shù)型模式來(lái)描述它。在此基礎(chǔ)上，把XML數(shù)據(jù)模式變化檢測(cè)問(wèn)題轉(zhuǎn)化為約束滿足求解問(wèn)題，不僅針對(duì)該問(wèn)題提出了一種較高效的求解算法，而且克服了一般方法要求在有序樹(shù)上進(jìn)行

4、的限制。 2．提出了一種基于權(quán)值加密的隱私安全分布式約束滿足問(wèn)題的求解算法。 針對(duì)分布式約束滿足問(wèn)題中的隱私安全保護(hù)，從求解效率角度考慮，提出了一種基于權(quán)值加密的隱私安全分布式約束滿足問(wèn)題的求解算法。該算法通過(guò)對(duì)Agent內(nèi)和Agent間不同的約束關(guān)系進(jìn)行隱私安全性分析，在加密求解過(guò)程中使用不同的處理方式來(lái)獲得更高的求解效率，利用Agent自身的計(jì)算和交互特點(diǎn)，不再引入額外的控制器來(lái)參與求解，真正實(shí)現(xiàn)分布式的安全策略，進(jìn)

5、一步減少了可能的信息泄漏，因而可以在確保隱私安全的前提下引入更好的啟發(fā)式搜索策略。 3．提出一種基于隱私安全分布式約束滿足求解的多Agent虛擬企業(yè)合作伙伴選擇協(xié)商模型。 以基于多Agent的虛擬企業(yè)中各候選企業(yè)的隱私安全為出發(fā)點(diǎn)，提出一種利用隱私安全分布式約束滿足求解的多Agent虛擬企業(yè)合作伙伴選擇協(xié)商模型。在該模型中，將市場(chǎng)各部分需求或服務(wù)建模為Agent，將需求或服務(wù)之間的關(guān)系建模為各個(gè)Agent內(nèi)部或Agent

6、之間的約束，Agent之間通過(guò)隱私安全分布式約束滿足求解方法來(lái)實(shí)現(xiàn)彼此間隱私安全的協(xié)商，進(jìn)而完成滿足需求的合作伙伴選擇任務(wù)。 分布式問(wèn)題求解的應(yīng)用將依賴于分布式約束滿足問(wèn)題中的求解效率、隱私安全等關(guān)鍵問(wèn)題的有效解決，因而這些問(wèn)題的研究具有重要的理論意義和應(yīng)用價(jià)值。本文針對(duì)其中的一些問(wèn)題展開(kāi)了研究和探討，如何進(jìn)一步研究適應(yīng)分布性從而減少通信需求和開(kāi)銷(xiāo)的分布式約束滿足方法；如何平衡隱私安全性和算法效率，在兩者間取得最佳折衷等，將為分