- 1、本文档共81页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
算法设计与分析课件第5章 节 回溯法.ppt
第5章 回溯法;学习要点
理解回溯法的深度优先有哪些信誉好的足球投注网站策略。
掌握用回溯法解题的算法框架
(1)递归回溯
(2)迭代回溯
(3)子集树算法框架
(4)排列树算法框架
;通过应用范例学习回溯法的设计策略。
(1)装载问题;
(2)批处理作业调度;
(3)符号三角形问题
(4)n后问题;
(5)0-1背包问题;
(6)旅行售货员问题
;有许多问题,当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时,往往要使用回溯法。
回溯法的基本做法是有哪些信誉好的足球投注网站,或是一种组织得井井有条的,能避免不必要有哪些信誉好的足球投注网站的穷举式有哪些信誉好的足球投注网站法。;回溯法的直观印象;回溯法:任务描述;回溯法:任务描述;剪枝函数和回溯法 ;使用剪枝函数的深度优先生成状态空间树中结点的求解方法称为回溯法(backtracking);
广度优先生成结点,并使用剪枝函数的方法称为分支限界法(branch-and-bound)。 ;问题的解空间;问题的解空间;生成问题状态的基本方法;生成问题状态的基本方法;生成问题状态的基本方法;有限离散问题总可以用穷举法求得问题的全部解.;设问题解可表为n元组(x1, x2,… xn), xi?si , si为有限集, n元组的子组(x1, x2,… xi) , in ,满足一定约束条件D. 设已有满足D的部分解(x1, x2,… xi), 添加xi+1 ?si+1,若(x1, x2,… xi ,xi+1 )满足D, 则继续添加xi+2 ; 若所有可能的xi+1 ?si+1均不满足D,去掉xi , 回溯到(x1, x2,… xi-1), 添加未考虑过的xi , 反复进行,直到(x1, .., xk) , k?n ,满足所有约束或证明无解. ;问题的解空间:E={ (x1, x2,… xn), xi ?si , si为有限集 };1.子集树:当解向量为不定长n元组时 , 树中从根至每一点的路径集合构成解空间.树的每个结点称为一个解状态,有儿子的结点称为可扩展结点,叶结点称为终止结点, 若结点v对应解状态(x1, x2,… xi),则其儿子对应扩展的解状态(x1, x2,… xi, xi+1 ).
2.排列树:当解向量为定长n元组时, 树中从根至叶结点的路径的集合构成解空间.树的每个叶结点称为一个解状态.;有哪些信誉好的足球投注网站按深度优先策略从根开始, 当有哪些信誉好的足球投注网站到任一结点时,判断该点是否满足约束条件D(剪枝函数),满足则继续向下深度优先有哪些信誉好的足球投注网站,否则跳过该结点以下的子树(剪枝), 向上逐级回溯.;回溯法的复杂性;回溯法的解题步骤;递归回溯;迭代回溯;???集树与排列树;例1 0-1背包问题;例1 0-1背包问题;例1 0-1背包问题;例1 0-1背包问题;例2 旅行售货员问题;装载问题;装载问题;装载问题;装载问题;用排序树表示解空间,则解为n元向量{x1, ... ,xn }, xi?{0, 1}
;cw + r ≤ bestw;例如 n=4, c1=12, w=[8, 6, 2, 3]. bestw初值=0;;template class Type
Type Maxloading(type w[], type c, int n,) //返回最优装载量
{ loading Type X; //初始化X
X. w=w; //集装箱重量数组
X. c=c; //第一艘船载重量
X. n=n;//集装箱数
X. bestw=0; //当前最优载重
X. cw=0;//当前载重量
X. r=0; //剩余集装箱重量
for (int i=1; i=n; i++)
X. r +=w[i]
//计算最优载重量
X.backtrack(1);
return X.bestw; };装载问题;装载问题的运行实例;批处理作业调度;批处理作业调度;批处理作业调度;批处理作业调度;批处理作业调度;批处理作业调度的运行实例;+ + - + - + +
+ - - - - +
- + + + -
- + + -
- + -
- -
+;在一般情况下,符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n,计算有多少个不同的符号三角形,使其所含的“+”和“-”的个数相同。;void Triangle::Backtrack(int t)
{
if ((counthalf)||(t*(t-1)/2-counthalf)) return;
if (tn) sum++;
else
for (
您可能关注的文档
- 第四章 节 种群及其基本特征2013(普通生态学).ppt
- 第四章 节 营销调研.ppt
- 第四章 节 董事会制度(公司治理学课件).ppt
- 第四章 节 财务预测 1.ppt
- 第四章 节 超敏反应.ppt
- 第四章 节 酸碱平衡 PPT课件.ppt
- 第四章 节 酸碱平衡18713 .ppt
- 第四章 节 非瓦尔拉斯均衡学派(西方经济学流派(石家庄经济学院(王志伟教材)) .ppt
- 第四章 节 (mba) .ppt
- 第四章 节 -护士言谈礼仪 .ppt
- 基于人工智能教育平台的移动应用开发,探讨跨平台兼容性影响因素及优化策略教学研究课题报告.docx
- 高中生物实验:城市热岛效应对城市生态系统服务功能的影响机制教学研究课题报告.docx
- 信息技术行业信息安全法律法规研究及政策建议教学研究课题报告.docx
- 人工智能视角下区域教育评价改革:利益相关者互动与政策支持研究教学研究课题报告.docx
- 6 《垃圾填埋场渗滤液处理与土地资源化利用研究》教学研究课题报告.docx
- 小学音乐与美术教师跨学科协作模式构建:人工智能技术助力教学创新教学研究课题报告.docx
- 《航空航天3D打印技术对航空器装配工艺的创新与效率提升》教学研究课题报告.docx
- 教育扶贫精准化策略研究:人工智能技术在区域教育中的应用与创新教学研究课题报告.docx
- 《区块链技术在电子政务电子档案管理中的数据完整性保障与优化》教学研究课题报告.docx
- 《中医护理情志疗法对癌症患者心理状态和生活质量提升的长期追踪研究》教学研究课题报告.docx
文档评论(0)