论文部分内容阅读
约束满足问题(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当中。