算法设计与分析课件 40 地图着色_第1页
算法设计与分析课件 40 地图着色_第2页
算法设计与分析课件 40 地图着色_第3页
算法设计与分析课件 40 地图着色_第4页
算法设计与分析课件 40 地图着色_第5页
已阅读5页，还剩10页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

算法设计与分析本节要点CONTENTS地图着色地图着色在地图着色中，为了区分边界，相邻区域是不能有相同颜色的。如果有一张没涂色的地图和m种颜色，怎么涂色才能使相邻区域是不同的颜色呢？地图着色如果把地图上的每一个区域退化成一个点，相邻的区域用线连接起来，就变成了一个无向连通图，地图着色就相当于给该无向连通图的每个点着色，要求有连线的点不能有相同颜色。这就是经典的图的着色问题。地图着色给定无向连通图G和m种颜色，找出所有不同的着色方案，使相邻的区域有不同的颜色。每个结点有m种选择，即解空间树中每个结点有m个分支，称为m叉树。地图着色（1）定义问题的解空间定义问题的解空间及其组织结构式很容易的。图的m着色问题的解空间形式为n元组{x1，x2，…，xi，…，xn}，每一个分量的取值为1，2，…，m，即问题的解是一个n元向量。解空间：{x1，x2，…，xi，…，xn}显约束：xi=1，2，…，m（i=1，2，3，…，n）。xi

=2表示图G中第i个结点着色为2号色。地图着色（2）确定解空间的组织结构问题的解空间组织结构是一棵满m叉树，树的深度为n。地图着色（3）搜索解空间· 约束条件假设当前扩展节点处于解空间树的第t层，那么从第1个结点到第t−1个结点的状态（着色的色号）已经确定。接下来沿着扩展结点的第一个分支进行扩展，此时需要判断第t个结点的着色情况。第t个结点的颜色号要与前t−1个结点中与其有边相连的结点颜色不同，如果有颜色相同的，则第t个结点不能用这个色号，换下一个色号尝试。地图着色地图着色· 限界条件只找可行解就可以了，不要求最优解，因此不需要限界条件。· 搜索过程扩展节点沿着第一个分支扩展，判断约束条件，如果满足，则进入深一层继续搜索；如果不满足，则换下一个色号尝试。如果所有的色号都尝试完毕，该结点变成死结点，向上回溯到离其最近的活结点，继续搜索。搜索到叶子节点时，找到一种着色方案。回溯搜索直到全部活结点变成死结点为止。地图着色地图的7个区域转化成的无向连通图。用3种颜色（淡紫，茶色，水绿色）给该地图着色。地图着色多个可行解，其中一个可行解{1，2，3，2，1，2，3}地图着色算法实现地图着色地图着色算法分析时间复杂度：

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论