摘要
最大团问题是在给定的一个图中寻找一个顶点数最大的顶点子集S,使得S中任意2个顶点都相邻,是一个著名的NP完全问题.提出一种带有局部搜索策略的化学反应算法求解最大团问题.为了提高算法的性能,在化学反应算法的分子碰撞阶段引入分子亲和度,使得碰撞后的分子倾向于得到对应于最大团较大的分子.将不相交的Golomb尺问题转化为最大团问题实例,通过求解最大团问题,得到若干不相交的Golomb尺问题的新结果.
The maximum clique problem consists of finding the largest subset S of the vertices of a graph so that the vertices in S are pairwise adjacent. It is a well-known NP-complete problem. This paper proposes a chemical reaction algorithm with a local search strategy to solve the maximum clique problem. In order to improve the performance of the algorithm, the paper introduces a molecular affinity at the molecular colli- sion stage to obtain comparatively bigger molecules compared with the maximum clique after collision. The paper changes the disjoint Golomb rules into real examples of maximum clique problem. By solving maxi- mum clique problem, the researchers obtain many new resuhs of disjoint Golomb rules.
作者
杨洪
张修军
邵泽辉
YANG Hong ZHANG Xiujun SHAO Zehui(School of Information Science and Engineering, Chengdu University, Chengdu 610106, China Key Laboratory of Pattern Recognition and Intelligent hrformation Processing of Sichuan Province Chengdu University, Chengdu 610106, China)
出处
《成都大学学报（自然科学版）》
2017年第1期43-46,共4页
Journal of Chengdu University（Natural Science Edition）
基金
国家自然科学基金(61309015)资助项目
关键词
最大团问题
局部搜索算法
化学反应优化
启发式算法
maximum clique problem
local search algorithm
chemical reaction optimization
heuristic algorithm
