解空间树（排列树）.pptVIP
下载本文档
1589
0
约8.83千字
约 37页
2018-01-05 发布于天津
举报
版权申诉
解空间树（排列树）.ppt
下载本文档
关闭预览
下载本文档
收藏
分享赚钱 奖
0
下载提示
文本预览
常见问题
1、原创力文档（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。。
2、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
4、该文档为VIP文档，如果想要下载，成为VIP会员后，下载免费。
5、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。
6、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
7、VIP文档为合作方或网友上传，每下载1次， 网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
解空间树（排列树）
* 复杂度分析： 计算可行性约束需要O(n)时间，在最坏情况下有 O(2n)个结点需要计算可行性约束，故解符号三角形问题的回溯算法所需的计算时间为 O(n2n)。 11-6 符号三角形问题 * 问题描述：略 解表示和解空间：{ (x1,x2,…,xn)|xi∈{0,1}, i=1~n } 解空间树： 11-7 0-1背包问题 * 无限界函数的算法 KnapBacktrack( int i ) { //cw当前背包重量，cv当前背包价值，bestv当前最优价值 if( i n) { //搜索到可行解 bestv = ( bestv cv )? cv : bestv; output( x ); } else{ if ( cw + w[i] =c ) { //走左子树 x[i]= 1; cw+=w[i]; cv += v[i]; KnapBacktrack( i+1); cw -= w[i]; cv -= v[i]; } //以下走右子树 x[i] = 0; KnapBacktrack( i+1); } } 11-7 0-1背包问题 main(float c, int n, float w[], float v[], int x[]) { //主程序 float cw=0.0, cv = 0.0, bestv = 0.0; KnapBacktrack(1); } * 有限界函数的算法 —基本思想： 设r是当前扩展结点z的右子树（或左子树）的价值上界，如果cv+r = bestv时，则可以裁剪掉右子树（或左子树）。 一种简单的确定z的左、右子树最优值上界的方法（设z为第k层结点）： 左子树上界 = i=k∑i=nvi，右子树上界=i=k+1 ∑i=nvi — 求经扩展结点z的可行解价值上界的方法： 计算至扩展结点的当前背包价值 已知xi，i=1~k-1，当前背包价值cv=i=1 ∑ i=k-1vixi 最后， 经z左子树的可行解价值上界=cv + 左子树上界 经z右子树的可行解价值上界= cv + 右子树上界 — 算法（略） 11-7 0-1背包问题 * 问题描述： 给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。 若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。 四色猜想： 在一个平面或球面上的任何地图能够只用4种颜色来着色，使相邻的国家在地图上着不同的颜色。假设每个国家在地图上是单连通区域，两个国家相邻则其边界长度不为0. 11-8 图的m着色问题 右图是一个有5个区域的地图及其相应的平面图。 * 解向量：(x1, x2, …, xn)表示顶点i所着颜色x[i]； 可行性约束函数：顶点i与已经着色的相邻顶点颜色不重复。 11-8 图的m着色问题 void Color::Backtrack(int t) { if (tn) { sum++; for (int i=1; i=n; i++) cout x[i] ; cout endl; } else for (int i=1;i=m;i++) { x[t]=i; if (Ok(t)) Backtrack(t+1); } } bool Color::Ok(int k) { // 检查颜色可用性 for (int j=1;j=n;j++) if ((a[k][j]==1)(x[j]==x[k])) return false; return true; } * 算法复杂度分析： 图m可着色问题的解空间树中内结点个数是 。对于每一个内结点，在最坏情况下，用ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn)。因此，回溯法总的
您可能关注的文档
舒降之、普罗布考、开搏通和祛淤消斑胶囊对食饵性兔动脉粥样硬化.pdf
舒降之、普罗布考和开搏通对颈动脉和股动脉内膜-中国科技论文在线.pdf
舞蹈即兴表演.ppt
舞蹈外伤面面观-cgmhorgtw.pdf
舟状骨骨折误诊案中西医学之交错.pdf
航空燃气轮机原理.ppt
船坞和码头城市的窗户.ppt
船舶修理业造船业.pdf
船院基建项目（工程款）支付审批表-新校区建设-江苏科技大学.doc
良渚文化的聚落级差及城萌芽-中国社会科学网.pdf
解读中国经济成就-胡景北.doc
解释人口、资源.ppt
警察在家庭暴力防治工作中之角色及其应有之策略—兼论运用女性.ppt
詹萍2012115心血管疾病的饮食李翠云-福建省人民医院.ppt
警惕“涨停板”中的陷阱.doc
计算机取证的工具体系thetoolsetofcomputerforensics.pdf
计算方法教学大纲-shouleme.doc
计算机专业（电脑、摄像头、打印机、数码摄像机及光盘刻录等相关软件）.ppt
解放渠东油田微构造精细解释方法应用-塔里木石油与天然气.pdf
计算机科学导论cs10致远学院-上海交通大学.doc
最近下载
2024年琼海市菜篮子市场开发有限责任公司招聘真题 .pdf
VIP
2025海南琼海市菜篮子市场开发有限责任公司招聘10人（第1号）备考练习题库及答案解析.docx
VIP
2025海南琼海市菜篮子市场开发有限责任公司招聘10人（第1号）笔试备考题库及答案解析.docx
VIP
2025海南琼海市菜篮子市场开发有限责任公司招聘10人（第1号）笔试参考题库附答案解析.docx
VIP
GB∕T 39758-2021 无障碍设计 盲文在标志、设备和器具上的应用.pdf
2025海南琼海市菜篮子市场开发有限责任公司招聘10人（第1号）笔试模拟试题及答案解析.docx
VIP
法哲学原理第二讲导论-公开课件.ppt
VIP
法哲学原理课件.pptx
轻型卒中临床诊疗中国专家共识（2024版）.pptx
VIP
广告语言的语用分析.docx
VIP
文档评论（0）
发表评论
zhuwo
+ 关注
实名认证
文档贡献者
该用户很懒，什么也没介绍
咨询Ta
进入空间
1亿VIP精品文档
更多 >
相关文档更多 >