图着色.docVIP

算法设计课程设计 题 目 图着色问题 姓 名 学 号 专业年级 指导教师 职 称 2014年 12月 4日 图的m着色问题 1 摘要 3 2 图的着色问题 4 2.1 图的着色问题的来源 4 2.2 图的着色问题的描述 4 3算法的基本思想 4 3.1 求极小覆盖法----布尔代数法 4 3.2 穷举法－Welch Powell着色法 4 3.3 回溯法 4 3.4 贪心法 4 3.5 蚁群算法 5 4算法步骤 5 4.1 求极小覆盖法----布尔代数法 4 4.2 穷举法－Welch Powell着色法 4 4.3 回溯法 4 4.4 贪心法 4 4.5 蚁群法 4 5 理论分析（复杂度比较）、实验性能比较 7 5.1 复杂度分析 4 5.2 实验性能比较 4 6 心得体会 8 7参考文献 8 8 附录 8 摘要 图论是近年来发展迅速而又应用广泛的一门新兴学科，已广泛应用于运筹学、网络理论、信息论、控制论、博奕论以及计算机科学等各个领域。 一般说来，图的着色问题最早起源于著名的“四色问题”，染色问题不但有着重要的理论价值，而且，它和很多实际问题有着密切联系，例如通讯系统的频道分配问题，更有着广泛的应用背景. 本文首先讨论了人工智能的状态有哪些信誉好的足球投注网站方法在图着色中的具体应用，并用可视化方法展示了低维的着色空间和约束的具体意义。 采用四种颜色着色的美国地图： 2.2图的着色问题的描述 图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。 通常所说的着色问题是指下述两类问题： 1．给定无环图G=(V,E)，用m种颜色为图中的每条边着色，要求每条边着一种颜色，并使相邻两条边有着不同的颜色，这个问题称为图的边着色问题。 2．给定无向图G=(V,E)，用m种颜色为图中的每个顶点着色，要求每个顶点着一种颜色，并使相邻两顶点之间有着不同的颜色，这个问题称为图的顶着色问题。 问题处理：如果把每一个区域收缩为一个顶点，把相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图。 例如，图12-1（a）所示的区域图可抽象为12-1（b）所表示的平面图。19世纪50年代，英国学者提出了任何地图都可以4中颜色来着色的4色猜想问题。过了100多年，这个问题才由美国学者在计算机上予以证明，这就是著名的四色定理。例如，在图12-1中，区域用城市名表示，颜色用数字表示，则图中表示了不同区域的不同着色问题 。 （在本文中主要讨论顶点着色） 3、算法的基本思想 目前求图着色问题主要有以下几种方法 3.1求极小覆盖法----布尔代数法 采用代数的方法来解决顶点着色问题 3.2穷举法－Welch Powell着色法 采用穷举一切的方法来找出所有的解 3.3回溯法 回溯法的基本思想是，在确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式有哪些信誉好的足球投注网站整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，有哪些信誉好的足球投注网站向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中有哪些信誉好的足球投注网站，直至找到所要求的解或解空间中已没有活结点时为止。 3.4贪心法 贪心算法： 贪心策略：选择一种颜色，以任意顶点作为开始顶点，依次考察图中的未被着色的每个顶点，如果一个顶点可以用颜色1着色，换言之，该顶点的邻接点都还未被着色，则用颜色1为该顶点着色，当没有顶点能以这种颜色着色时，选择颜色2和一个未被着色的顶点作为开始顶点，用第二种颜色为尽可能多的顶点着色，如果还有未着色的顶点，则选取颜色3并为尽可能多的顶点着色，依此类推。 3.5蚁群算法 4、算法步骤 4.1 求极小覆盖法----布尔代数法 例1：求图12-2G的顶色数 解： Step1：求极大独立集