计算机科学 ›› 2015, Vol. 42 ›› Issue (2): 241-246.doi: 10.11896/j.issn.1002-137X.2015.02.050

• 人工智能 • 上一篇    下一篇

E-CARGO模型在CSP问题中的描述

滕少华,张红,刘冬宁,朱海滨,张巍,梁路   

  1. 广东工业大学计算机学院 广州510006,广东工业大学计算机学院 广州510006,广东工业大学计算机学院 广州510006,广东工业大学计算机学院 广州510006,广东工业大学计算机学院 广州510006,广东工业大学计算机学院 广州510006
  • 出版日期:2018-11-14 发布日期:2018-11-14
  • 基金资助:
    本文受教育部重点实验室基金(110411),国家自然科学基金(61272067,61104156,61370229,61402118),广东省科技计划项目(2012B091000173,2013B090200017),广州市科技计划项目(2012J5100054,2013J4500028),韶关市科技计划项目(2010CXY/C05)资助

Constrainted E-CARGO Model Applying in CSP Problem

TENG Shao-hua, ZHANG Hong, LIU Dong-ning, ZHU Hai-bin, ZHANG Wei and LIANG Lu   

  • Online:2018-11-14 Published:2018-11-14

摘要: 基于角色的协同RBC (Role-Based Collaboration)是一套研究角色及它们之间复杂关系的方法、理论和技术。在RBC中,群组角色分配GRA (Group Role Assignment) 既是一个关键问题,也是一个难题。已有许多研究探讨了基于Q(Qualification)矩阵来处理GRA问题,但仅利用Q矩阵难以描述问题中的复杂约束关系。因此,将约束集(Constraint)引进E-CARGO模型,提出了带约束的EC-CARGO模型,研究了RBC、GRA、SAT(SATisfaction)和CSP(Constraint Satisfaction Problem)之间的联系,建立了RBC-GRA-SAT-CSP问题求解转换关系;提出应用EC-CARGO模型求解经典CSP约束满足问题的方法,进而描述了应用GRA求解CSP约束满足问题的通用框架。最后以N皇后问题为例,验证了通过GRA的约束指派求解CSP问题的有效性。

关键词: 基于角色的协同,群组角色指派,约束满足问题,EC-CARGO模型,N皇后

Abstract: Role-based collaboration is a set of method,theory and technology which is used to explore the role and the complex relationship among them.In the RBC,group role assignment is a key problem and difficult problem.Many researchers solve GRA problems based on a qualification matrix,but it is difficult to describe the complex constraint relationships of the problems with only one matrix.Therefore, after adding a constraint set to the E-CARGO model,we put forward the Ec-CARGO model with constraints.We also deeply studied the intrinsic relationships among the RBC,GRA,SAT,and CSP,and then produced the transformation relation of RBC-GRA-SAT-CSP.We proposed a method of solving typical CSP constraint satisfaction problems based on Ec-CARGO,and designed a common framework of solving CSP problems with the constraint assignment of GRA.Finally,the N-queen problem was used to verify the validity of our method .

Key words: Role-based collaboration,Group role assignment,Constraint satisfaction problem,EC-CARGO model,N-queen problem

[1] Zhu Hai-bin,Zhou Meng-chu.M-M Role-Transfer Problems andTheir Solutions[J].IEEE Transaction on Systems,Man and Cybernetics,Part A:Systems and Humans,2009,39(2):448-459
[2] Liu Lin-yuan,Zhu Hai-bin.Role and Transition Mechanisms in Collaborative Systems[J].Computer Engineering, 2006,32(19):103-104,107
[3] Zhu Hai-bin,Alkins R.Group Role Assignment[C]∥2009 International Symposium On Collaborative Technologies and Systems(CTS 2009).2009:431-439
[4] Zhu Hai-bin,Hou M,Wang C,et al.An Efficient Outpatient Scheduling Approach[J].IEEE Transactions on Automation Science and Engineering,2012,9(4):701-709
[5] Huang Zhou,Zhang Jiang.Generating SAT Instances fromFirst-Order Formulas[J].Journal of Software,2005,6(3):327-335
[6] CHEN Yuan,SHI Zhong-Zhi.The Comparison and Analysis of Solving Approachs to Constrain Satisfaction Problems[J].Computer Science,1998,25(1):8-12
[7] Wang Teng-fei,Xu Xhou-bo,Gu Tian-long.Symbolic ADD Algorithms for Arc Consistency and Application in Constraint Sa-tisfaction Problem Solving[J].Computer Science,2013,0(12):243-247
[8] Li Hong-bo,Li Zhan-shan,Wang Tao.Improving Coarse-Grained Arc Consistency Algorithms in Solving Constraint Sa-tisfaction Problems[J].Journal of Software,2012,23(7):1816-1823
[9] Zhu Hai-bin.Role Mechanisms in Collaborative Systems[J].In-ternational Journal of Production Research,2006,44(1):181-193
[10] Zhu Hai-bin,Zhou Meng-chu.Efficient Role Transfer Based on Kuhn-Munkres Algorithm[J].IEEE Transactions on Systems,Man and Cybernetics,Part A:Systems and Humans,2012,42(2):491-496
[11] Zhu Hai-bin,Zhou Meng-chu,Alknis R.Group Role Assignmentvia a Kuhn-Munkres Algorithm-based Solution[J].IEEE Transactions on Systems,Man and Cybernetics,Part A:Systems and Humans,2012,2(3):739-750
[12] Huang Da-feng.The construction and equivalence analysis of thesolutions to the N-Queens Problem[D].Guangzhou:Graduate School of Sun Yat-Sen University,2008
[13] Wang Zi-wen,Li Zhan-shan,Ai Yang,et al.Algorithm for solving constraint satisfaction problems based on dynamic value ordering heuristic[J].Computer Integrated Manufacturing Systems,2011,17(4):832-837
[14] Abramson B,Yung M.Construction Through Decomposition:A Divide-and-Conquer Algorithm for the N-Queens Problem[C]∥Proceedings of the 1986 Fall Joint Computer Conference.1986:620-628
[15] Sun Ji-gui,Zhu Xing-jun,Zhang Yong-gang,et al.An Approach of Solving Constraint Satisfaction Problem Based on Preproces-sing[J].Chinese Journal of Computers,2008,31(6):919-926
[16] Zhu Hai-bin.Fundamental Issues in the Design of a Role Engine[C]∥Proceedings of the 6th International Symposium on Collaborative Technologies and Systems.Irvine,CA,USA,2008:399-407

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!