【算法分析与设计】动态规划(下)(三)

简介: 【算法分析与设计】动态规划(下)

8.1 算法改进

  由m(i,j)的递归式容易证明,在一般情况下,对每一个确定的i(1≤i≤n),函数m(i,j)是关于变量j的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下,函数m(i,j)由其全部跳跃点唯一确定。如图所示。

  对每一个确定的i(1≤i≤n),用一个表p[i]存储函数m(i,j)的全部跳跃点。表p[i]可依计算m(i,j)的递归式递归地由表p[i+1]计算,初始时p[n+1]={(0,0)}。


8.2 一个例子

  n=3,c=6,w={4,3,2},v={5,2,1}。


8.3 算法改进

  函数m(i,j)是由函数m(i+1,j)与函数m(i+1,j-wi)+vi作max运算得到的。因此,函数m(i,j)的全部跳跃点包含于函数m(i+1,j)的跳跃点集p[i+1]与函数m(i+1,j-wi)+vi的跳跃点集q[i+1]的并集中。易知,(s,t)q[i+1]当且仅当wisc且(s-wi,t-vi)p[i+1]。因此,容易由p[i+1]确定跳跃点集q[i+1]如下q[i+1]=p[i+1](wi,vi)={(j+wi,m(i,j)+vi)|(j,m(i,j))p[i+1]}

  另一方面,设(a,b)和(c,d)是p[i+1]q[i+1]中的2个跳跃点,则当ca且d<b时,(c,d)受控于(a,b),从而(c,d)不是p[i]中的跳跃点。除受控跳跃点外,p[i+1]q[i+1]中的其它跳跃点均为p[i]中的跳跃点。

  由此可见,在递归地由表p[i+1]计算表p[i]时,可先由p[i+1]计算出q[i+1],然后合并表p[i+1]和表q[i+1],并清除其中的受控跳跃点得到表p[i]。


8.4 一个例子

  n=5,c=10,w={2,2,6,5,4},v={6,3,5,4,6}。

  初始时p[6]={(0,0)},(w5,v5)=(4,6)。因此,q[6]=p[6](w5,v5)={(4,6)}。p[5]={(0,0),(4,6)}。q[5]=p[5](w4,v4)={(5,4),(9,10)}。

  从跳跃点集p[5]与q[5]的并集p[5]q[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳跃点(5,4)受控于跳跃点(4,6)。将受控跳跃点(5,4)清除后,得到p[4]={(0,0),(4,6),(9,10)}。

  q[4]=p[4](6,5)={(6,5),(10,11)}

  p[3]={(0,0),(4,6),(9,10),(10,11)}

  q[3]=p[3](2,3)={(2,3),(6,9)}

  p[2]={(0,0),(2,3),(4,6),(6,9),(9,10),(10,11)}

  q[2]=p[2](2,6)={(2,6),(4,9),(6,12),(8,15)}

  p[1]={(0,0),(2,6),(4,9),(6,12),(8,15)}

  p[1]的最后的那个跳跃点(8,15)给出所求的最优值为m(1,c)=15。


8.5 算法复杂度分析

  上述算法的主要计算量在于计算跳跃点集pi。由于q[i+1]=p[i+1](wi,vi),故计算q[i+1]需要O(|p[i+1]|)计算时间。合并p[i+1]和q[i+1]并清除受控跳跃点也需要O(|p[i+1]|)计算时间。从跳跃点集p[i]的定义可以看出,p[i]中的跳跃点相应于xi,…,xn的0/1赋值。

  因此,p[i]中跳跃点个数不超过2n-i+1。由此可见,算法计算跳跃点集p[i]所花费的计算时间为

  从而,改进后算法的计算时间复杂性为O(2n)。当所给物品的重量wi(1≤i≤n)是整数时,|p[i]|≤c+1,(1≤i≤n)。在这种情况下,改进后算法的计算时间复杂性为O(min{nc,2n})


九、最优二叉搜索树

9.1 二叉搜索树

  (1)若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值

  (2)若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值

  (3)它的左、右子树也分别为二叉排序树在随机的情况下,二叉查找树的平均查找长度和logn是等数量级的


9.2 二叉搜索树的期望耗费

  搜索成功与不成功的概率:

  二叉搜索树的期望耗费:

  有 个节点的二叉树的个数为:穷举搜索法的时间复杂度为指数级:


9.3 二叉搜索树的期望耗费示例


9.4 最优二叉搜索树

  最优二叉搜索树Tij的平均路长为pij,则所求的最优值为p1,n。由 最优二叉搜索树问题的最优子结构性质 可建立计算pij的递归式如下

  记wi,jpi,j为m(i,j),则m(1,n)=w1,np1,n=p1,n为所求的最优值。计算m(i,j)的递归式为

  注意到,

  可以得到O(n2)的算法。


十、小结

  动态规划算法和分治法的相同点是什么?

  动态规划算法和分治法的不同之处在哪里?

  用“表”记录所有已有子问题的答案!避免重复计算,从而得到多项式时间复杂度

  动态规划通常用来计算“最优”解,不适合计算“合并”解。

目录
打赏
0
0
0
0
7
分享
相关文章
境内深度合成服务算法备案通过名单分析报告
本报告基于《境内深度合成服务算法备案通过名单》,分析了2023年6月至2025年3月公布的10批备案数据,涵盖属地分布、行业应用及产品形式等多个维度。报告显示,深度合成算法主要集中于经济发达地区,如北京、广东、上海等地,涉及教育、医疗、金融、娱乐等多行业。未来趋势显示技术将向多模态融合、行业定制化和安全合规方向发展。建议企业加强技术研发、拓展应用场景、关注政策动态,以在深度合成领域抢占先机。此分析旨在为企业提供参考,助力把握技术发展机遇。
境内深度合成服务算法备案通过名单分析报告
从公布的前十一批其他算法备案通过名单分析
2025年3月12日,国家网信办发布算法备案信息,深度合成算法通过395款,其他算法45款。前10次备案中,深度合成算法累计3234款,其他类别647款。个性化推送类占比49%,涵盖电商、资讯、视频推荐;检索过滤类占31.53%,用于搜索优化和内容安全;调度决策类占9.12%,集中在物流配送等;排序精选类占8.81%,生成合成类占1.55%。应用领域包括电商、社交媒体、物流、金融、医疗等,互联网科技企业主导,技术向垂直行业渗透,内容安全和多模态技术成新增长点。未来大模型检索和多模态生成或成重点。
从公布的前十一批其他算法备案通过名单分析
|
2月前
|
算法系列之动态规划
动态规划(Dynamic Programming,简称DP)是一种用于解决复杂问题的算法设计技术。它通过将问题分解为更小的子问题,并存储这些子问题的解来避免重复计算,从而提高算法的效率。
42 4
算法系列之动态规划
从第十批算法备案通过名单中分析算法的属地占比、行业及应用情况
2025年3月12日,国家网信办公布第十批深度合成算法通过名单,共395款。主要分布在广东、北京、上海、浙江等地,占比超80%,涵盖智能对话、图像生成、文本生成等多行业。典型应用包括医疗、教育、金融等领域,如觅健医疗内容生成算法、匠邦AI智能生成合成算法等。服务角色以面向用户为主,技术趋势为多模态融合与垂直领域专业化。
企业监控软件中 Go 语言哈希表算法的应用研究与分析
在数字化时代,企业监控软件对企业的稳定运营至关重要。哈希表(散列表)作为高效的数据结构,广泛应用于企业监控中,如设备状态管理、数据分类和缓存机制。Go 语言中的 map 实现了哈希表,能快速处理海量监控数据,确保实时准确反映设备状态,提升系统性能,助力企业实现智能化管理。
36 3
从第九批深度合成备案通过公示名单分析算法备案属地、行业及应用领域占比
2024年12月20日,中央网信办公布第九批深度合成算法名单。分析显示,教育、智能对话、医疗健康和图像生成为核心应用领域。文本生成占比最高(57.56%),涵盖智能客服、法律咨询等;图像/视频生成次之(27.32%),应用于广告设计、影视制作等。北京、广东、浙江等地技术集中度高,多模态融合成未来重点。垂直行业如医疗、教育、金融加速引入AI,提升效率与用户体验。
【动态规划篇】穿越算法迷雾:约瑟夫环问题的奇幻密码
【动态规划篇】穿越算法迷雾:约瑟夫环问题的奇幻密码
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
76 5
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等