四色问题的相关文献,可用。

第16卷第4期

1999年 11月贵州大学学报(自然科学版)JournalofGuizhouUniversity(NaturalScience)Vol.16.No.4Nov.1999

平面图着色的遗传算法

洪 斌

(贵州虹山轴承(集团)有限公司,安顺 561000)

摘 要 基于遗传算法的思想,建立了一个用四种不同颜色对平面图结点进行

着色的快速算法.

…… 此处隐藏0字 ……

关键词 平面图,图着色,快速算法

中图分类号 T301.6

1 引言

1976年,美国数学家阿佩尔(K.Appel)和哈肯(W.Haken)与计算机科学家科赫(J.Koch)合作,用计算机证明了著名 四色猜想 ,曾经轰动一时.但是,在当时的计算条件下,这个证明的计算用时达1260小时,其正确性人工无法验证,即 四色猜想 至今尚未找到一个严格的数学证明.尽管如此,人们似乎已经默人这一著名猜想是对的.即任意一个平图都可以用至多四种不同颜色对其平面区域进行正常着色.由图论知识知道,该结论可以转化为任意一个平图都可以至多四种不同颜色对其结点进行正常着色(相邻结点不能着相同颜色).

我们现在所考虑的问题不是 四色猜想 本身,而是对于任意一个平面图,如何给出一个用四种不同颜色对其结点进行正常着色的着色方案.如果用通常的逐步搜索方法进行着色,对于具有n个结点的平面图,我们可以用构造一棵高度为n的完满四叉树来表示整个搜索过程,并可求出所有着色方案,其中一个着色方案对应着该四叉树上一条从根结点到叶结点的路径.不难看出:找到一个着色方案的最坏时间是指数时间.可以证明,寻求一个平面图的四色着色方案是一3个NPC问题.

近年来迅速发展起来的遗传算法,是一种全局优化方法,该方法依照生物学中的 优胜劣汰,适者生存 的原理,提供了一种强大的快速搜索能力,能够快速搜索到问题的最优解或近似最优解.从理论上讲,对于我们所考虑的问题,其最优解是存在的.问题是:如何快速地确定出最优解.这是本文的主要目的和结果.

2 遗传算法的基本原理

遗传算法的思想是,将一组初始方案(如所有可能解)人工模拟为一组群体,一种方案对应一个个体.通常采用二进制编码将一个方案描述一个0、1字符串.假定不同个体