论文部分内容阅读
约束满足问题（Constraint Satisfaction Problem，CSP）作为人工智能研究中多年来一个重要的分支，通常都是NP-hard问题。现实生活中的很多问题，都可以用约束满足问题来建模，如调度中的资源分配，时序推理等等。一般情况下，约束满足问题是由一个有限集的变量组成，其中变量是离散的，并且属于有限值域。求解CSP问题，即为寻找一个不违反任何约束条件的完全赋值。 E-CARGO是由朱海滨教授提出的一类基于角色协同的建模工具，能够有效地应用在一系列的约束问题的求解中。在E-CARGO模型中，一个系统可以被描述为一个九元组∑∷=。该模型在处理现实的赋值指派问题中具有很好的性能，例如足球队的比赛队形问题，医院预约排序问题等。E-CARGO的应用特征不仅表现为对应用系统建模的有效性上，同时能够将系统中各种角色之间的关系清晰地构造出来，并通过群组的概念得以对系统进行优化。利用角色之间的继承，冲突，以及转换等关系，将其应用于RBAC系统当中，从而提出了对RBAC系统改进策略。通过其中群组的概念，对入侵检测系统给予了清晰的描述和定义，并根据角色的转变带动群组的变化，从角色协作的角度对入侵检测进行优化。该模型在拓扑关系的衍生以及预测方面也取得了一定的进展，它从系统环境本身出发，利用角色之间的冲突以及继承等关系，对朋友关系的预测给出了相关意见。 基于角色的协同RBC(Role-Based Collaboration)是一套研究角色及其之间复杂关系的方法、理论及技术。在RBC中，群组角色分配GRA(Group Role Assignment)既是一个关键问题，也是一个难题。已有许多研究探讨了基于Q(Qualification)矩阵来处理GRA问题，但仅利用Q矩阵难于描述问题中的复杂约束关系。 因此，本文将约束集(Constraint)引进E-CARGO模型，提出了带约束的EC-CARGO模型，研究了RBC、GRA、SAT(SATisfaction)和CSP之问的联系，建立了RBC-GRA-SAT-CSP问题求解转换关系。提出从结构特性入手，应用EC-CARGO模型求解经典CSP约束满足问题的方法，进而给出了应用GRA求解CSP约束满足问题的通用框架。并以N皇后和图着色问题为例，验证了通过GRA的约束指派求解CSP问题的有效性。从而证明E-CARGO和CSP在某种程度上具有一定的等价性，并使得E-CARGO在处理工程类问题当中能够有效地使用CSP的各类方法，同时也能够将工程性的解决方案引入CSP当中。