約束滿足及其分布式求解和應用研究.pdf

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

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

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

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

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

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