| 分组遗传算法用于图的着色 |
| |
| 引用本文： | 霍红卫,许进,保铮.分组遗传算法用于图的着色[J].西北民族学院学报,2000(1). |
| |
| 作者姓名： | 霍红卫 许进 保铮 |
| |
| 作者单位： | 西安电子科技大学电子工程研究所!陕西西安710071 |
| |
| 摘 要： | 图的着色算法是一种典型的NP 完全问题 在系统地讨论了图的正常顶点着色、边着色以及全着色的有关理论的基础上 ,提出了基于分组遗传算法和启发式搜索的图的正常 k 点着色 ,正常k 边着色以及正常k 全着色的新型混合算法 ,提出了评价算法性能的标准 实验仿真结果表明 ,新型混合算法可以获得问题高质量的解 ,即对图进行着色所使用的颜色数接近图的色数
|
| 关 键 词： | 分组遗传算法 图的着色 NP-完全问题 |
Coloring a Graph Using Group Genetic Algotithm |
| |
| HUO Hong wei,XU Jin,BAO Zheng.Coloring a Graph Using Group Genetic Algotithm[J].Journal of Northwest Minorities University(Natural Science ),2000(1). |
| |
| Authors: | HUO Hong wei XU Jin BAO Zheng |
| |
| Abstract: | Graph coloring is a NP Complete problem.By the analyzing some properties of proper k vertex coloring,k edge coloring,and total coloring of a graph,a new algorithm on proper k vertex coloring,k edge coloring,and total coloring of a graph based on group genetic algorithm and heuristics search is given.Experiments show that this new algorithm can obtain solutions of excellent quality. |
| |
| Keywords: | group genetic algorithm graph coloring NP complete problem |
| 本文献已被 CNKI 等数据库收录！ |
|
