算法设计与分析 课件 第六章 回溯法6.3.3 花草种植问题_第1页
算法设计与分析 课件 第六章 回溯法6.3.3 花草种植问题_第2页
算法设计与分析 课件 第六章 回溯法6.3.3 花草种植问题_第3页
算法设计与分析 课件 第六章 回溯法6.3.3 花草种植问题_第4页
算法设计与分析 课件 第六章 回溯法6.3.3 花草种植问题_第5页
已阅读5页，还剩5页未读， 继续免费阅读

付费下载

下载本文档

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

文档简介

计算机算法设计与分析第6章回溯法6.3.3花草种植问题在一大片农田中有多个花草的种植区域，这些种植区域通过田埂连接，如下图所示。现需要将每个种植区域种上一种颜色的花草，但相邻区域不能种植同一种颜色的花草。我们的目标是找到一种最优的花草种植方案，使得各个种植区域使用最少的花草颜色区分开来。图的着色问题12345图的着色问题假设给定无向连通图G=(V,E)和m种不同的颜色，其中V表示结点集合，E表示边集合，用这些颜色为图G的各顶点着色，每个顶点着一种颜色。若一个图最少需要m种颜色才能使图中每条边连接的两个顶点着不同颜色，则称m为该图的着色数。求一个图的着色数m的问题称为图的m可着色优化问题。第一步，定义解向量设图G=(V,E),|V|=n,颜色数=m,图G用邻接矩阵g存储表示，用整数1,2…m来表示m种不同的颜色。顶点i所着的颜色用x[i]表示。则可用一个n元组x[1],x[2],...x[n]表示花草种植问题的解，其中x[i]表第i块区域种植花草的颜色种类，x[i]∈[1,m]。第二步，确定搜索结构：子集树1-红2-绿3-蓝×××××x1=2x2=mx3=3x3=2x3=1x2=2x1=mx1=1x2=1x4=1x5=3x5=2x5=1............2345151234第三步确定：约束条件解空间树为子集树,是一棵n+1层的完全m叉树，在解空间树中做深度优先搜索，约束条件:如果g[i][j]=1，x[i]≠x[j]，j∈[1,n]。剪枝函数代码//剪枝函数intisColorValid(inti,intcolor){ for(intj=0;j<n;j++){ if(g[i][j]&&x[j]==color){ return0;//颜色冲突 } } return1;//颜色有效}i和j有边相邻，且i顶点着的颜色color与j顶点的颜色x[j]相同图的m着色问题递归回溯代码intbacktrack(inti){

if(i==n){ for(inti=0;i<n;i++){

printf("结点%d:颜色%d\n",i+1,x[i]); } return1;//所有结点都已着色 } for(intcolor=1;color<=m;color++){

x[i]=color;

if(isColorValid(i,color)){backtrack(i+1);return1;} } return0;//未找到有效的着色方案}考虑到叶子结点后，一个可行解出现，输出结果对第i顶点着色color=1~m一一尝试若满足约束条件，则递归考虑下一个顶点时间复杂度分析花草种植问题即图的m可着色问题，全部搜索的情况下其解空间树中有

个结点。对于每一个结点，

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

温馨提示

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

最新文档

评论

0/150

提交评论