网站大量收购闲置独家精品文档,联系QQ:2885784924

算法设计与分析 课件 第六章 回溯法6.3.3 花草种植问题.ppt

算法设计与分析 课件 第六章 回溯法6.3.3 花草种植问题.ppt

  1. 1、本文档共10页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多

计算机算法设计与分析第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;jn;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;in;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可着色问题,全部有哪些信誉好的足球投注网站的情况下其解空间树中有个结点。对于每一个结点,在最坏情况下,用isColor检查当前扩展结点的每个子结点的可行性需要的时间为O(nm)。故回溯法求解图的m可着色问题的时间复杂度上界为:*这是一个典型的图的m着色问题,我们将田块种植区域映射为一个图。映射方式,在每块田区取一个点作为图的顶点,两块田间相邻我们将相应的顶点用无向边连接,左边田块区域图就可以映射为右边的一个无向图。**这是一个典型的图的m着色问题,我们将田块种植区域映射为一个图。映射方式,在每块田区取一个点作为图的顶点,两块田间相邻我们将相应的顶点用无向边连接,左边田块区域图就可以映射为右边的一个无向图。*

您可能关注的文档

文档评论(0)

xiaobao + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档