基于社群联盟的冲突消解原则求解图着色问题
Solving Graph Coloring Problem Based on Conflict Resolution Strategies of Social Community Alliance
-
摘要: 该文提出了一种基于群体协作的计算模型。该模型首先将输入的数据单元建模成微观个体,然后基于求解目标设计个体间的协作规则,最后通过个体在协作过程中涌现出的宏观现象来得到全局最优解。通过运用群体协作模型求解具有NP-完全复杂度的最优图着色问题,结果表明该模型的性能优于若干启发式方法,并且得到如下结论:1) 如果算法的动力学特征类似于混沌边缘现象,则算法能够在线性或亚线性时间复杂度求解问题。2) 如果算法的动力学特征呈现出完全随机性或强收敛性,则算法将退化成蛮力搜索。