| 基于遗传和启发式算法的混合顶点着色算法 |
| |
| 引用本文： | 廖辉传.基于遗传和启发式算法的混合顶点着色算法[J].吉首大学学报(自然科学版),2008,29(5):57-60. |
| |
| 作者姓名： | 廖辉传 |
| |
| 作者单位： | （华东交通大学信息工程学院，江西 南昌330013） |
| |
| 基金项目： | 华东交通大学科研基金资助项目 |
| |
| 摘 要： | 图的着色问题是一种典型的NP-完全问题.提出了基于遗传算法和启发式算法的新型混合顶点着色算法，该算法在实现过程中涉及到染色体的编码方法、适应度函数的设计以及遗传算子的选择等.实验仿真结果表明此算法改善了求解的时间复杂度，可以获得问题高质量的解.
|
| 关 键 词： | 图的着色 启发式算法 遗传算法 时间复杂度 |
Vertex Coloring of a Graph Based on Genetic and Heuristics Search Algorithm |
| |
| LIAO Hui-chuan.Vertex Coloring of a Graph Based on Genetic and Heuristics Search Algorithm[J].Journal of Jishou University(Natural Science Edition),2008,29(5):57-60. |
| |
| Authors: | LIAO Hui-chuan |
| |
| Institution: | (School of Information Engineering,East China Jiaotong University,Nanchang 330013,China) |
| |
| Abstract: | 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. |
| |
| Keywords: | graph coloring heuristics search algorithm genetic algorithm time complexity |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《吉首大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《吉首大学学报(自然科学版)》下载免费的PDF全文 |
