计算机工程2012，Vol.38Issue(23)：181-184,189,5.DOI:10.3969/j.issn.1000-3428.2012.23.045
图形着色问题的分布式势博弈算法
Distributed Potential Game Method for Graph Coloring Problem
摘要
Abstract
While solving the large-scale graph-coloring problems, the existing distributed algorithms require that the node must be connectable. The growth of the neighbor-nodes brings negative effect on both algorithm efficiency and the solvable scale. So a new algorithm is proposed. The graph-coloring problem is converted to the game problem on the multi-Agent platform. Using the adaptive learning algorithm, each Agent optimizes its own state to maximize system's utility which is the Nash equilibrium. Empirical evaluation shows that the new method has higher efficiency, better immunity to the growth of neighbors and can deal with larger scale problems than existing distributed algorithms.关键词
分布式算法/纳什均衡/图形着色/多代理/自适应学习算法Key words
distributed algorithm/ Nash equilibrium/ graph-coloring/ multi-Agent/ adaptive leaning algorithm分类
信息技术与安全科学引用本文复制引用
杨光,蔚承建,王开,胡恒恺..图形着色问题的分布式势博弈算法[J].计算机工程,2012,38(23):181-184,189,5.基金项目
国家自然科学基金资助项目(60972165) （60972165）
教育部博士点基金资助项目(20100092120012,20090092120012) （20100092120012,20090092120012）
江苏省自然科学基金资助项目(BK2011060,BK2010240) （BK2011060,BK2010240）
南京市政府海外留学基金资助项目(ZBW302001) （ZBW302001）
