摘要
图的着色问题是一种典型的NP-完全问题.提出了基于遗传算法和启发式算法的新型混合顶点着色算法,该算法在实现过程中涉及到染色体的编码方法、适应度函数的设计以及遗传算子的选择等.实验仿真结果表明此算法改善了求解的时间复杂度,可以获得问题高质量的解.
Graph coloring is a typical NP-completely problem. This paper puts forward a new method of vertex coloring of a graph based on genetic algorithm and heuristics search algorithm. This algorithm involves the coding methods of chromosome,the design of fitness function and the selection operators. Experiments show that this new algorithm can improve time complexity and obtain solutions of excellent quality.
出处
《吉首大学学报（自然科学版）》
CAS
2008年第5期57-60,共4页
Journal of Jishou University(Natural Sciences Edition)
基金
华东交通大学科研基金资助项目(07XX01)
关键词
图的着色
启发式算法
遗传算法
时间复杂度
graph coloring
heuristics search algorithm genetic algorithm time comolexity
