基于e-CARGO的若干CSP問題及群組優(yōu)化研究.pdf

1、約束滿足問題（Constraint Satisfaction Problem，CSP）作為人工智能研究中多年來一個(gè)重要的分支，通常都是NP-hard問題。現(xiàn)實(shí)生活中的很多問題，都可以用約束滿足問題來建模，如調(diào)度中的資源分配，時(shí)序推理等等。一般情況下，約束滿足問題是由一個(gè)有限集的變量組成，其中變量是離散的，并且屬于有限值域。求解CSP問題，即為尋找一個(gè)不違反任何約束條件的完全賦值。
　　E-CARGO是由朱海濱教授提出的一類基于角色

2、協(xié)同的建模工具，能夠有效地應(yīng)用在一系列的約束問題的求解中。在E-CARGO模型中，一個(gè)系統(tǒng)可以被描述為一個(gè)九元組∑∷=。該模型在處理現(xiàn)實(shí)的賦值指派問題中具有很好的性能，例如足球隊(duì)的比賽隊(duì)形問題，醫(yī)院預(yù)約排序問題等。E-CARGO的應(yīng)用特征不僅表現(xiàn)為對(duì)應(yīng)用系統(tǒng)建模的有效性上，同時(shí)能夠?qū)⑾到y(tǒng)中各種角色之間的關(guān)系清晰地構(gòu)造出來，并通過群組的概念得以對(duì)系統(tǒng)進(jìn)行優(yōu)化。利用角色之間的繼承，沖突，以及轉(zhuǎn)換等關(guān)

3、系，將其應(yīng)用于RBAC系統(tǒng)當(dāng)中，從而提出了對(duì)RBAC系統(tǒng)改進(jìn)策略。通過其中群組的概念，對(duì)入侵檢測(cè)系統(tǒng)給予了清晰的描述和定義，并根據(jù)角色的轉(zhuǎn)變帶動(dòng)群組的變化，從角色協(xié)作的角度對(duì)入侵檢測(cè)進(jìn)行優(yōu)化。該模型在拓?fù)潢P(guān)系的衍生以及預(yù)測(cè)方面也取得了一定的進(jìn)展，它從系統(tǒng)環(huán)境本身出發(fā)，利用角色之間的沖突以及繼承等關(guān)系，對(duì)朋友關(guān)系的預(yù)測(cè)給出了相關(guān)意見。
　　基于角色的協(xié)同RBC(Role-Based Collaboration)是一套研究角色及其之間

4、復(fù)雜關(guān)系的方法、理論及技術(shù)。在RBC中，群組角色分配GRA(Group Role Assignment)既是一個(gè)關(guān)鍵問題，也是一個(gè)難題。已有許多研究探討了基于Q(Qualification)矩陣來處理GRA問題，但僅利用Q矩陣難于描述問題中的復(fù)雜約束關(guān)系。
　　因此，本文將約束集(Constraint)引進(jìn)E-CARGO模型，提出了帶約束的EC-CARGO模型，研究了RBC、GRA、SAT(SATisfaction)和CSP之問的

5、聯(lián)系，建立了RBC-GRA-SAT-CSP問題求解轉(zhuǎn)換關(guān)系。提出從結(jié)構(gòu)特性入手，應(yīng)用EC-CARGO模型求解經(jīng)典CSP約束滿足問題的方法，進(jìn)而給出了應(yīng)用GRA求解CSP約束滿足問題的通用框架。并以N皇后和圖著色問題為例，驗(yàn)證了通過GRA的約束指派求解CSP問題的有效性。從而證明E-CARGO和CSP在某種程度上具有一定的等價(jià)性，并使得E-CARGO在處理工程類問題當(dāng)中能夠有效地使用CSP的各類方法，同時(shí)也能夠?qū)⒐こ绦缘慕鉀Q方案引入CSP