算法设计与分析 课件 第六章 回溯法 .ppt

算法设计与分析 课件 第六章 回溯法 .ppt

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

算法改进常用的评估方法为=在不考虑现有饲料余量的情况下,后面的奶牛全部产奶的总和,若cv+bestv,则进入结点A的右分支,否则剪枝处理。c语言实现剪枝函数,评估后面奶牛产奶量的最大极值intbound(inti,intcw,intcv){intbv=cv;for(intj=i;jn;j++)bv+=v[j];returnbv;}//饲料投喂问题(0-1背包问题)的递归回溯函数voidbacktrack(inti,intcw,intcv){if(i==n){if(cvbestvcw=c){ bestv=cv; for(intk=0;kn;k++)bestx[k]=x[k];}return;}if(cw+w[i]=c){cv+=v[i];cw+=w[i];x[i]=1;backtrack(i+1,cw,cv);cv-=v[i];cw-=w[i];//若剪枝需要回溯}if(bound(i+1,cw,cv)bestv){ x[i]=0;backtrack(i+1,cw,cv);}}进入左分支的剪枝约束条件进入右分支的剪枝限界条件与前一节一样进一步优化为了对进入右分支的限界函数进一步优化,考虑现有饲料余量下精准评估的值。可以在问题处理前,我们按单位重量投喂饲料后牛奶产出量的降序,重新将奶牛进行编号。按照这种顺序,只要饲料还够,就进行投喂,并计算其产奶量;当考虑到某头奶牛时,剩下的饲料不足投喂它,则用剩下的饲料对它进行部分投喂,并计算部分投喂可能的产奶量,并将产奶量累计计算结果作为的评估值,相较前面不考虑剩余饲料量的评估会更为精准。进一步优化后的评估限界函数//剪枝限界函数的c语言代码doublebound(inti,intcw,intcv){doublebv=cv;inttw=cw;for(intj=i;jn;j++){if(tw+w[j]=c){bv+=v[j];tw+=w[j];}else{doublerc=c-tw;bv+=(rc*v[j])/w[j];break;}}returnbv;}已产生的价值(产奶量)已消耗的背包容量(饲料量)已消耗的背包容量+当前投喂量总量当前不足投喂,则部分投喂进行计算效率分析采用剪枝函数优化的回溯法求解0-1背包问题(奶牛饲料投喂问题)的算法时间复杂度的上限为O(2n),但由于有进入左分支的约束函数和进入右分支的限界函数,可以极大提高回溯法的效率。计算机算法设计与分析第6章回溯法6.3.1饲料投喂问题饲料投喂问题:某农场有n头奶牛,假设每头奶牛仅有投喂或不投喂饲料两种选择,奶牛i需要投喂wi千克饲料才能产出vi千克牛奶。农场现有饲料总量为C千克,问如何投喂才能使得奶牛产奶量最大化?6.3.1饲料投喂问题农场奶牛饲料投喂问题是一个典型的0-1背包问题,假设农场有n=4头奶牛,农场饲料总量C为10千克,每头奶牛需要的饲料量和能够产出的牛奶量如下,w_i投喂饲料重量,v_i投喂后的产量。牛奶编号w_iv_i12523835144521问题的解向量空间奶牛投喂的解向量空间可以表示为一个四元组X=(x1,x2,x3,x4),xi的值表示第i头奶牛投喂情况。由于每头奶牛仅有投喂或不投喂饲料两种选择,所以xi(i=1,2,3,4,表示奶牛编号)只能取值为0或1,xi=0表示不投喂,xi=1表示进行投喂。解空间树用回溯法求解,需要生成一棵二叉树(子集树)来表示问题的解空间。x4=1,2+3+5+510不可行,回溯?ABx4=0x4=1,5+5≤10x3=1,510x2=0,C=10x1=0,C=10初始状态,饲料总量C=10x1=1,210x2=1,2+310x3=1,2+3+5≤10编号w_i

文档评论(0)

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

精品资料

版权声明书
用户编号:7040145050000060

1亿VIP精品文档

相关文档