- 1、本文档共38页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
[社会学]2007动态规划2
ACM暑期集训讲座 动态规划(二) :常见模型 主讲 wangfangbob 自我介绍 wangfangbob 汪方 南开大学数学学院 基础数学专业 描述集合论方向 06级硕士 xiaofangbob@163.com 动态规划的目的 1 重叠子问题: 递归求解时,会出现递归的分枝相互重合,从而造成重复计算,如果计算一次就保存结果就会大量减少计算次数 2 多阶段决策,求解最优值: 求解最优值,往往演变成多个阶段的决策,而决策的数目会随着阶段数量的增长指数增长,利用动态规划的方法可以限制决策数目的增长,提高效率。 一些模型:1.有哪些信誉好的足球投注网站,限制,递推,增维 实例1 给定一个具有N层的数字三角形,从顶至底有多条路径,每一步可沿左斜线向下或沿右斜线向下,路径所经过的数字之和为路径得分,请求出最小路径得分。 典型的多阶段决策 暴力解法: 每一层就是一个决策的阶段,我们遍历有哪些信誉好的足球投注网站所有的方案,然后找出最优解。 第一层只有顶点,决策数1,顺着顶点有两个方向可以选择,决策数2………….. 这样每一层的每一决策到下一层都有2个方向,这样决策数量翻倍,指数增长! 改为递推,用一元组D(X)描述问题,D(X)表示从顶层到达第X层的最小路径得分。因此,此问题就是求出D(N)(若需要,还应求出最优路径)。这是一种很自然的想法和表示方法。但是很可惜: D(x) - D(x+1) 不成立! 于是我们思考,可不可以记录多个值,每个阶段不是一个值,而是多个值,从一个阶段的多个值推出下一个阶段的多个值? 表示法二: 增加一维, 用二元组D(X,y)描述问题,D(X,y)表示从顶层到达第X层第y个位置的最小路径得分。 显然到达y点的路径只能来自于上一层的y-1点或者y点,所以: D(X,y)=min{D(X-1,y),D(X-1,y-1)}+a(X,y) D(1,1)=a(1,1) 我们需要的最终需要的解就是: min{D(N,k)} 1= k = N 。 问题解决! 思考: 从有哪些信誉好的足球投注网站的角度可不可以得到相同的结论呢? 暴力有哪些信誉好的足球投注网站算法的弊端就是指数级别的增长 如果能够找到一个非指数增长的量限制其增长,貌似也是可行的 在某一个阶段,也许决策的数量很多,对于本题就是路径数目,但是路径到达的终点都是本层的点,而本层的点是有限,呈线形增长 而且路径对后面决策的影响都是通过这些点 所以有相同终点的路径我们当然选得分最小的那条,而舍弃其他的路径,实际上对于本题我们不需要记录选择了哪一条路径,只需要记录最小得分即可,如果题目要求输出路径,再记录选择的路径。 回顾刚才的状态转移方程: D(X,y)=min{D(X-1,y),D(X-1,y-1)}+a(X,y) D(1,1)=a(1,1) y就是用来限制决策数量的增长。 如果这个题过于简单,还不能完全表达寻找变量来限制决策数量的增长,那么我们来看下一个例题: nkoj1705: [NKPC3]计算机硬件评分系统 小C听说微软新推出的一款操作系统Windows Vista可以对电脑的配置进行评分,很感兴趣。由于小C对硬件软件方面都很了解,就通过一系列的市场调查与实践,制作了一款自己的计算机硬件评分系统。此系统可以对CPU、内存、硬盘、主板、显卡五部分分别进行评分,分数为不超过100的正整数,并以这五个分数中的最低分作为对计算机的总体评分。 同寝室的小D打算最近购置一台新电脑,他请小C给他当参谋,小C就提供了一些当前的CPU、内存、硬盘、主板、显卡五种硬件的品牌、价格以及每个硬件由他所制作的系统所评价出来的分数。小D准备至多用N元来购买这五种硬件并且他还希望能够得到一台电脑有尽量高的总体评分。 作为寝室长的你主动要写一个程序来帮助小D购买电脑。 N = 50000,每一种硬件有30000种。 此题决策明显是分5个阶段:每个硬件的决策一个阶段。 暴力有哪些信誉好的足球投注网站的复杂度:30000^5! 有什么量可以限制决策数量呢? 我们发现虽然价钱范围不小,硬件数量也很大,但是分数值却只有100个! 无论到哪个阶段相同分数的决策我们肯定选择钱最少的那种决策。 于是每个阶段的决策数都被限制在了100个。 状态表示: D [ i ][ j ]表示决策到第i个硬件得到分数 j 需要的最小钱数。 a[k]表示第k个这种硬件的得分 b[k]表示第k个这种硬件的价钱 对于每一个得分 j , 我们都把它和30000个硬件配一下: If( j a[k] ) D[ i + 1 ][a[k]] ?= D[ i ][ j ] + b[k] else D[ i + 1 ][ j ] ?= D[ i ][ j ] + b[k] 这样每个j都循环30000次,而j有100个变化,会产生100 * 30000个分枝,但是D[
文档评论(0)