电子科技大学学报Issue(1)：2-16,15.DOI:10.3969/j.issn.1001-0548.2016.01.001
基于社群联盟的冲突消解原则求解图着色问题
Solving Graph Coloring Problem Based on Conflict Resolution Strategies of Social Community Alliance
摘要
Abstract
This study proposes a computing model based on group cooperation. The data unit of the input is first modeled as group individual, the cooperation rules between individuals are then designed based on the target of the problem. Finally, the problem’s global optimal solution is obtained through the emergence phenomenon of individuals’ cooperation process. By applying group cooperation model to solve graph coloring problem which has NP-complete complexity, it shows that the proposed model works better than several heuristic methods. Experimental results illustrate that: 1) if the algorithm’s dynamics exhibits the edge of chaos phenomenon, the algorithm can solve the problem in linear or sub linear time complexity; 2) if the algorithm’s dynamics is completely random or exhibits strong convergence, the algorithm degenerates into brutal force search.关键词
协作规则/涌现计算/图着色/群体协作/NP-完全/社会计算Key words
cooperation rules/emergent computing/graph coloring/group cooperation/NP-complete/social computing分类
信息技术与安全科学引用本文复制引用
郑皎凌,舒红平,许源平,乔少杰,立玉..基于社群联盟的冲突消解原则求解图着色问题[J].电子科技大学学报,2016,(1):2-16,15.基金项目
国家自然科学基金(61202250,61203172)；四川省教育厅重点项目(ZA150184) （61202250,61203172）
