- 1、本文档共44页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[]动态规划算法分析
第6章 动态规划
贪心策略的每一步选择当前最优,并没有考虑
将来能否达到全局最优解。
动态规划:对于具有n个输入的最优解问题,
解题分成若干个阶段,每个阶段的决策以来与
前一阶段的状态,决策的结果造成状态的转移,
成为下一阶段的决策依据。
6.1 动态规划的思想方法
例:货郎担问题
一个推销员从城市A 出发,跑遍其他三个城市
B、C和D,然后回到城市A 。要求不重复走任
何一段路,而且用的代价(路费)最少。
由于路线都是从A开始,到A结束,所以任
何一条路线都是B、C、D的一个排列。所有可
能的排列有3 !种。每个排列的代价要计算4次
加法,共计算4·3! =24次加法,然后比较3 !
=6次,取出其中最小的一个。
6.1 动态规划的思想方法(续)
一般地说,n个城市需要计
算n·(n-1)!次加法和作(n-1)! 3
比较。 A 5 B
显然,如果两条不同的 6 3
路径有部分路段相同,那 7 3 2 4
么许多次加法实际上是重 7
复计算的。因此,我们可 5
D C
以设计新的算法来避免这 2
种不必要的重复和比较。
例:货郎担问题算法设计思想
A
3 7 3
6 A B
B C D 5
3
6
7 3 2 4
7
5
D C
2
例:货郎担问题算法设计思想(续)
A
3 7 3
6 A B
B C D 5
2 3 4 2 7
您可能关注的文档
最近下载
- 2024年北京市公安局顺义分局勤务辅警、流动人口管理员招聘考试题库(含答案).pdf VIP
- GB_T 9441—2021《球墨铸铁金相检验》标准解读.pdf VIP
- 精编人教版五年级上册数学第一单元试卷(含解析).docx VIP
- 英语时态专项练习.doc
- Pierce交联磁珠式免疫沉淀免疫共沉淀试剂盒.PDF
- (11)免疫调节——2024年九省联考+2023年四省联考+2021年八省联考生物专项精编.docx VIP
- GB/T 19812.6-2022塑料节水灌溉器材 第6部分:输水用聚乙烯(PE)管材.pdf
- 低空经济装备制造产业园项目可行性报告(模板范文).docx
- 2023年成人本科学位英语考前真题及答案.docx
- 2018年新国家开放大学报名登记表系统表.pdf VIP
文档评论(0)