当前位置: 首页 > news >正文

动态规划(用空间换时间的算法)原理逻辑代码超详细!参考自《算法导论》

动态规划(用空间换时间的算法)-实例说明和用法详解

  • 动态规划(DP)思想
  • 实例说明
    • 钢条切割问题
    • 矩阵链乘法问题
  • 应用满足的条件和场景

本篇博客以《算法导论》第15章动态规划算法为本背景,大量引用书中内容和实例,并根据书中伪代码给出python代码复现,详解算法的核心逻辑和实现过程。

动态规划(DP)思想

动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为重叠的子问题进行解决,从而一步步获取最优解的处理算法。

动态规划与分治方法相似,都是通过组合子问题的解来求解原问题(在这里“programming”指的是一种表格法,并非编写计算机序)。但是分治方法将问题划分为互不相交的子问题,递归地求解子问题,再将它们的解组合起来,求出原问题的解。与之相反,动态规划应用于子问题重叠的情况,即不同的子问题具有公共的子问题(子问题的求解是递归进行的,将其划分为更小的子子问题)。

在这种情况下,分治算法会做许多不必要的工作,它会反复地求解那些公共子子问题。而动态规划算法对每个子子问题只求解一次,将其解保存在一个表格中,从而无需每次求解一个子子问题时都重新计算,避免了这种不必要的计算工作。

实例说明

动态规划方法常用来求解最优化问题,下面分别给出二个例子来说明:第一个是将钢条割成短钢条,使得总价值最高;第二个是解决如何用最少的标量乘法操作完成一个矩阵链相乘的运算

钢条切割问题

下面是钢条切割问题的背景:

问题背景说明
比如,下图给出长度为4英寸钢条所有可能的切割方案:
切割方案
其中,钢条上方的数字为每段钢条对应的价格。不同的切割方案对应不同的价格,我们发现,将一段长度为4英寸的钢条切为两段各长2英寸的钢条,将产生 P 2 P_2 P2+ P 2 P_2 P2=5+5=10的收益,为最优解,即对应上图中的方案C。

下面我们逐步分析出钢条切割问题的最优收益的递推公式:
在这里插入图片描述
更为一般的收益公式,长度为n的钢条切割后的最大收益 r n r_n rn表示如下:
在这里插入图片描述
一种更简单的递归方法:
在这里插入图片描述
其中,(15.2)式中的 p i p_i pi指长度为i的钢条对应的价格,直接查表得到,不用再进行切割。

如果用传统的递归方法求解,一旦n的规模稍微变大,程序运行的时间会变得相当长,因为这种方法反复用相同的参数值对自身进行递归调用,即它反复求解相同的子问题。时间呈指数级增长。下图给出n=4时,递归树的调用过程:
在这里插入图片描述
动态规划方法的运行时间是多项式阶的。
在这里插入图片描述
动态规划有两种等价的实现方法:
在这里插入图片描述
下面给出自底向上法的代码实现过程:
在这里插入图片描述
在上面的伪代码中,输入为两个变量,价格表数组和长度n;输出长度为n的钢条得到的最优收益。

下面计算长度为9时,钢条切割的最大收益:

import numpy as npdef Bottom_Up_Cut_Rod(p, n):r = []r.insert(0, 0)for j in range(1, n + 1):q = float('-inf')for i in range(1, j + 1):q = max(q, p[i - 1] + r[j - i])r.insert(j, q)return r[n]if __name__ == '__main__':# 出售长度为i(i=1,2,3,,,10)的钢条所对应的价格样表p = [1, 5, 8, 9, 10, 17, 17, 20, 24, 30]n = 9result = Bottom_Up_Cut_Rod(p, n)print("长度为{}时,".format(n))print("对应的最优收益值为{}。".format(result))

在这里插入图片描述
下图是长度为1、2、3…,对应的最优切割方案和收益。
在这里插入图片描述

思想:为了求解规模为 n 的原问题,我们先求解形式完全一样,但规模更小的子问题。即当完成首次切割后,我们将两段钢条看成两个独立的钢条切割问题实例。我们通过组合两个相关子问题的最优解,并在所有可能的两段切割方案中选取组合收益最大者,构成原问题的最优解。

我们称钢条切割问题满足最优子结构性质:问题的最优解由相关子问题的最优解组合而成,而这些子问题可以独立求解。

矩阵链乘法问题

矩阵链乘法问题即是多个矩阵相乘,找出最快计算次序的问题。

在这里插入图片描述
在这里插入图片描述

对矩阵链加括号的方式会对乘积运算的代价产生巨大影响,下面举例来说明:

在这里插入图片描述
因此,如果A是pXq的矩阵,B是qXr的矩阵,那么乘积 C是pXr的矩阵。计算 C所需时间由标量乘法的次数决定,即 pqr。下面我们将用标量乘法的次数来表示计算代价

在这里插入图片描述

传统方法:穷举所有可能的括号化方案不会是一个高效的算法,因为它的运行时间仍然是指数级增长的。

下面定义矩阵链问题的计算代价公式,令m[i,j]表示计算矩阵 A i , . . . , j A_{i,...,j} Ai,...,j所需标量乘法次数的最小值。

在这里插入图片描述在这里插入图片描述
在这里插入图片描述
假设最优分割点k是未知的,则递归求解公式变为:
在这里插入图片描述
下面用一个例子来说明:
在这里插入图片描述
上图是我手写的一个例子,为了帮助理解。其中, A 1 A_1 A1:2 × \times × 3 ,表示 A 1 A_1 A1的维度为2行3列,P列表存放的是四个矩阵的维度,其中前一个矩阵的列数等于后一个矩阵的行数。要求出 A 1 A_1 A1 A 2 A_2 A2 A 3 A_3 A3 A 4 A_4 A4的计算代价,假设分割点k=2,则计算顺序为 ( ( A 1 A 2 ) ( A 3 A 4 ) ) ((A_1A_2)(A_3A_4)) ((A1A2)(A3A4))。其中, ( A 1 A 2 ) (A_1A_2) (A1A2)的计算代价对应上图中的矩阵C, ( A 3 A 4 ) (A_3A_4) (A3A4)的计算代价对应上图中的矩阵D,最后再令C与D相乘,算的最后的计算代价(总次数)为48。

下面给出的过程 MATRIX-CHAIN-ORDER实现了自底向上表格法:
各输入变量的含义如下:
在这里插入图片描述
在这里插入图片描述
输出变量为最优代价矩阵m和最优分割点矩阵k。

下面给出代码的计算过程帮助理解。假设n=4, p = [ p 0 , p 1 , p 2 , p 3 , p 4 ] p = [p_0,p_1,p_2,p_3,p_4] p=[p0,p1,p2,p3,p4],求 A 1 A 2 A 3 A 4 A_1A_2A_3A_4 A1A2A3A4的最优代价,即求m[1,4]。计算过程如下:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

左边是最优代价矩阵,右边是最优分割点矩阵

以图15-5的数据为例,python代码如下:

import numpy as npdef MATRIX_CHAIN_ORDER(p):n = len(p) - 1# 定义计算代价矩阵mm = np.zeros((n, n))# 定义最优分割点矩阵ss = np.zeros((n, n))for l in range(2, n + 1):for i in range(1, n - l + 2):j = i + l - 1m[i - 1, j - 1] = float('inf')for k in range(i, j):q = m[i - 1, k - 1] + m[k, j - 1] + p[i - 1] * p[k] * p[j]if q < m[i - 1, j - 1]:m[i - 1, j - 1] = qs[i - 1, j - 1] = kprint(m)  # 每个元素对应长度为j-i+1的矩阵所需要最小计算代价print(s)  # 对应长度为j-i+1的矩阵最优分割点return m, sif __name__ == '__main__':p = [30, 35, 15, 5, 10, 20, 25]MATRIX_CHAIN_ORDER(p)

运行结果如下:

在这里插入图片描述
能够看出,跑出的结果与书上的两个矩阵完全相同。(只不过书中对矩阵沿主对角线方向进行了旋转)

思路:一个非平凡的矩阵链乘法问题实例的任何解都需要划分链,而任何最优解都是由子问题实例的最优解构成的。因此,为了构造一个矩阵链乘法问题实例的最优解,我们可以将问题划分为两个子问题( A i A i + 1 ⋅ ⋅ ⋅ A k A_iA_{i+1}···A_k AiAi+1⋅⋅⋅Ak A k + 1 ⋅ ⋅ ⋅ A j A_{k+1}···A_j Ak+1⋅⋅⋅Aj)子题实例的最优解,然后将子问题的最优解组合起来。我们必须保证在确定分割点时,已经考察了所有可能的划分点,这样就可以保证不会遗漏最优解。

应用满足的条件和场景

应用动态规划方法求解的最优化问题应该具备的两个要素:最优子结构子问题重叠

在这里插入图片描述
在这里插入图片描述

动态规划算法可以用来求解最优化问题,除了本文给出的两个例子外,常用的场景包括求解斐波那契数列,求解最长公共子序列、01背包问题和最优二叉搜索树等。想要深入了解该算法的原理和应用场景,具体可以阅读《算法导论》,我有电子版的,需要的兄弟姐妹可以私信我取。

综上所述,满足最优子结构和子问题重叠性质的问题可以利用动态规划思想建模,这种方法会开辟内存,存储以往的运算结果,再下次遇到时直接调用而不再重复计算,因此大大节省了时间,是一种经典的用空间换时间的算法,而大多数情况下,项目对时间的要求往往更严格,相比对内存的占用情况就宽松很多了。

相关文章:

动态规划(用空间换时间的算法)原理逻辑代码超详细!参考自《算法导论》

动态规划&#xff08;用空间换时间的算法&#xff09;-实例说明和用法详解 动态规划&#xff08;DP&#xff09;思想实例说明钢条切割问题矩阵链乘法问题 应用满足的条件和场景 本篇博客以《算法导论》第15章动态规划算法为本背景&#xff0c;大量引用书中内容和实例&#xff0…...

Jmeter添加cookie的两种方式

jmeter中添加cookie可以通过配置HTTP Cookie Manager&#xff0c;也可以通过HTTP Header Manager&#xff0c;因为cookie是放在头文件里发送的。 实例&#xff1a;博客园点击添加新随笔 https://i.cnblogs.com/EditPosts.aspx?opt1 如果未登录&#xff0c;跳转登录页&#xf…...

【ArcGIS Pro二次开发】(58):数据的本地化存储

在做村规工具的过程中&#xff0c;需要设置一些参数&#xff0c;比如说导图的DPI&#xff0c;需要导出的图名等等。 每次导图前都需要设置参数&#xff0c;虽然有默认值&#xff0c;但还是需要不时的修改。 在使用的过程中&#xff0c;可能会有一些常用的参数&#xff0c;希望…...

React配置代理服务器的5种方法

五种方法的介绍 以下是五种在React项目中配置代理服务器的方法的使用场景和优缺点&#xff1a; 1. 使用 http-proxy-middleware 中间件&#xff1a; 使用场景&#xff1a;适用于大多数React项目&#xff0c;简单易用。优点&#xff1a;配置简单&#xff0c;易于理解和维护。…...

树莓派:5.jar程序自启运行

搞了好长时间才搞定&#xff0c;普通的jar文件好启动。神奇的在于在ssh里启动GPIO可以操作&#xff0c;但是自启动GPIO不能控制。第二天才想明白估计是GPIO的操作权限比较高&#xff0c;一试果然如此&#xff0c;特此记录。 1、copy程序文件和sh文件在Public下 piraspberrypi…...

Vivado中SmartConnect和InterConnect的区别

前言&#xff1a;本文章为FPGA问答系列&#xff0c;我们会定期整理FPGA交流群&#xff08;包括其他FPGA博主的群&#xff09;里面有价值的问题&#xff0c;并汇总成文章&#xff0c;如果问题多的话就每周整理一期&#xff0c;如果问题少就每两周整理一期&#xff0c;一方面是希…...

了解HTTP代理日志:解读请求流量和响应信息

嗨&#xff0c;爬虫程序员们&#xff01;你们是否在了解爬虫发送的请求流量和接收的响应信息上有过困扰&#xff1f;今天&#xff0c;我们一起来了解一下。 首先&#xff0c;我们需要理解HTTP代理日志的基本结构和内容。HTTP代理日志是对爬虫发送的请求和接收的响应进行记录的文…...

排序-堆排序

给你一个整数数组 nums&#xff0c;请你将该数组升序排列。 输入&#xff1a;nums [5,2,3,1] 输出&#xff1a;[1,2,3,5] 输入&#xff1a;nums [5,1,1,2,0,0] 输出&#xff1a;[0,0,1,1,2,5] 思路直接看我录制的视频吧 算法-堆排序_哔哩哔哩_bilibili 实现代码如下所示&…...

挑战Open AI!!!马斯克宣布成立xAI.

北京时间7月13日凌晨&#xff0c;马斯克在Twitter上宣布&#xff1a;“xAI正式成立&#xff0c;去了解现实。”马斯克表示&#xff0c;推出xAI的原因是想要“了解宇宙的真实本质”。Ghat GPT横空出世已有半年&#xff0c;国内外“百模大战”愈演愈烈&#xff0c;AI大模型的现状…...

HTTP协议学习笔记1

初识HTTP 输入网址进入网页过程发生了什么&#xff1f; DNS解析&#xff1a;浏览器会向本地DNS服务器发出域名解析请求&#xff0c;如果本地DNS服务器中没有对应的IP地址&#xff0c;则会向上级DNS服务器继续发出请求&#xff0c;直到找到正确的IP地址为止。 建立TCP连接&…...

【网络基础实战之路】基于OSPF协议建立两个MGRE网络的实验详解

系列文章传送门&#xff1a; 【网络基础实战之路】设计网络划分的实战详解 【网络基础实战之路】一文弄懂TCP的三次握手与四次断开 【网络基础实战之路】基于MGRE多点协议的实战详解 【网络基础实战之路】基于OSPF协议建立两个MGRE网络的实验详解 PS&#xff1a;本要求基于…...

【学习日志】2023.Aug.6,支持向量机的实现

2023.Aug.6&#xff0c;支持向量机的实现 参考了大佬的代码&#xff0c;但有些地方似乎还有改进的空间&#xff0c;我加了注释 #codingutf-8 #Author:Dodo #Date:2018-12-03 #Email:lvtengchaopku.edu.cn #Blog:www.pkudodo.com数据集&#xff1a;Mnist 训练集数量&#xff1…...

LeetCode_动态规划_中等_1749.任意子数组和的绝对值的最大值

目录 1.题目2.思路3.代码实现&#xff08;Java&#xff09; 1.题目 给你一个整数数组 nums 。一个子数组 [numsl, numsl1, …, numsr-1, numsr] 的 和的绝对值 为 abs(numsl numsl1 … numsr-1 numsr) 。请你找出 nums 中和的绝对值 最大的任意子数组&#xff08;可能为空…...

无涯教程-Perl - 环境配置

在开始编写Perl程序之前&#xff0c;让我们了解如何设置我们的Perl环境。 您的系统更有可能安装了perl。只需尝试在$提示符下给出以下命令- $perl -v 如果您的计算机上安装了perl&#xff0c;那么您将收到以下消息: This is perl 5, version 16, subversion 2 (v5.16.2) b…...

QT显示加载动画

文章目录 一、前言二、使用1.FormLoading.h2.FormLoading.cpp 一、前言 项目中在下发指令时&#xff0c;结果异步返回&#xff0c;可能需要一段时间&#xff0c;因此需要用到加载动画。 用的比较简单&#xff0c;就是新建Widget子窗口&#xff0c;放一个Label&#xff0c;使用…...

原型模式(C++)

定义 使用原型实例指定创建对象的种类&#xff0c;然后通过拷贝这些原型来创建新的对象。 应用场景 在软件系统中&#xff0c;经常面临着“某些结构复杂的对象”的创建工作;由于需求的变化&#xff0c;这些对象经常面临着剧烈的变化&#xff0c;但是它们却拥有比较稳定一致的…...

web浏览器打开本地exe应用

一、如何使web浏览器打开本地exe应用&#xff1f; 浏览器打开本地exe程序我们可以使用ActiveXObject方法&#xff0c;但是只支持IE&#xff0c;谷歌、火狐等浏览器并不支持此操作。 那问题来了&#xff0c;我们又该如何操作&#xff1f; 经过本博主的不断学习探索终于找到了一…...

微信小程序如何配置并使用less?

1&#xff0c;检查微信开发者工具&#xff08;工具版本1.03&#xff09;————这步很重要不然后面按步骤实行后会发现急死你也还是不管用&#xff0c;我之前死在过这一步&#xff0c;所以大家不要再次踩坑了 ~ ~ 。。。 2&#xff0c;在VScode中下载Less插件 3&#xff0c;…...

【Spring】反射动态修改Bean实例的私有属性值

Cannot cast org.springframework.http.client.InterceptingClientHttpRequestFactory to org.springframework.http.client.OkHttp3ClientHttpRequestFactory 由于RestTemplate在自定义初始化时顺序比较早&#xff0c;想在启动后跟进yum或者注解配置修改初始化的值时&#xff…...

MySQL DDL 数据定义

文章目录 1.创建数据库2.删除数据库3.查看所有数据库4.查看当前数据库5.选择数据库6.创建数据表7.查看 MySQL 支持的存储引擎和默认的存储引擎8.删除数据表9.查看数据库的数据表10.查看表结构11.查看建表语句12.重命名数据表13.增加、删除和修改字段自增长14.增加、删除和修改数…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)

引言 工欲善其事&#xff0c;必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后&#xff0c;我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集&#xff0c;就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...

认识CMake并使用CMake构建自己的第一个项目

1.CMake的作用和优势 跨平台支持&#xff1a;CMake支持多种操作系统和编译器&#xff0c;使用同一份构建配置可以在不同的环境中使用 简化配置&#xff1a;通过CMakeLists.txt文件&#xff0c;用户可以定义项目结构、依赖项、编译选项等&#xff0c;无需手动编写复杂的构建脚本…...