【数据结构】动态规划(Dynamic Programming)

一.动态规划(DP)的定义:

求解决策过程(decision process)最优化的数学方法。

将多阶段决策过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解。

二.动态规划的基本思想:

与分治法类似,将待求解问题分解成若干个子问题

但是经分解得到的子问题往往不是相互独立的。

如果使用分治法求解问题,有些子问题被重复计算了多次。

而“如何减少子问题的重复计算”是动态规划算法的关键思想。

问题:如何减少子问题的重复计算呢?

解决方案:保存已解决的子问题的答案,在需要的时候找出已经求得的答案。

三.动态规划的基本步骤

1.找出最优解的性质,并刻划其结构特征。即:寻找最优解的子问题结构。

2.递归地定义最优解。即:根据子问题的结构建立问题的递归解式,求解最优值。

3.以自底向上的方式计算出最优值。

4.根据计算最优值时得到的信息,构造最优解。

四.例题分析——多个矩阵连乘模块设计

问题描述:

实现多个矩阵连乘功能

关键问题计算:

给定n个矩阵{$A_1,A_2,......,A_n$},其中$A_i$$A_{i+1}$是可乘的,考察这n个矩阵的连乘积

$A_1A_2A_3...A_n$

由于矩阵乘法满足结合律,所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。

若一个矩阵连乘积的计算次序完全确定,也就是说该矩阵已完全加括号,则可以依此次序反复调用3个矩阵相乘的标准算法计算出矩阵连乘积。

完全加括号的矩阵连乘积:

设有四个矩阵 A,B,C,D 维数分别为:

50*10;10*40;40*30;30*5

则总共有五种完全加括号的方式:

1)

(A((BC)D))

2)

(A(B(CD)))

3)

((AB)(CD))

4)

(((AB)C)D)

5)

((A(BC))D)

对于两个矩阵A(p*q)*B(q*r)(标准乘法计算):

void matrixMultiply(int *a,int *b,int *c,int ra,int ca,int rb,int cb){if(ca!=rb){cout<<"矩阵不可乘!"<<endl;}else{int i,j,k,n,sum=0;for(i=0;i<ra;i++){for(j=0;j<cb;j++){for(k=0;k<ca;k++){sum+=a[i*ca+k]*b[k*cb+j];}c[i*ra+j]=sum;sum=0;}}}
}

需要进行p*q*r次乘法计算!

矩阵连乘问题转化为:

确定矩阵连乘的计算次序,使得按照该次序计算矩阵连乘需要的数乘次数最少。

1.穷举法求解思路:

        列举出所有可能的计算次序,并计算出每一种次序相应需要的数乘次数,从中找出一种数乘次数最少的计算次序。

算法复杂度分析:

对于n个矩阵的连乘积,设其不同的计算次序为P(n)

由于每种加括号方式都可以分解为两个子矩阵的加括号的问题

2.动态规划求解:

最优解结构分析:

将矩阵连乘积$A_iA_{i+1}...A_j$简记为:A[i:j],这里i<=j。

设这个计算次序在$A_k$A_{k+1}之间将矩阵断开,i<=k<j,则其相应的完全加括号的方式为:

$A_iA_{i+1}...A_k$)($A_{k+1}...A_j$)

总计算量=A[i:k]的计算量加上A[k+1:j]的计算量,再加上A[i:k]和A[k+1:j]相乘的计算量。

特征:计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。

最优子结构性质:最优解包含其子问题的最优解。

建立递归关系:(m[i,j]表示最小连乘次数)

当i=j时,A[i:j]=$A_i$,m[i,j]=0

当i<j时,m[i,j]=$min_k${m[i,k]+m[k+1,j]+$p_{i-1}p_kp_j$}

则有:

(k的位置只有j-i种可能) 

注:由于矩阵乘法中$A_i$的列数和$A_{i+1}$的行数相等,则可以只用列数来化简表达式,这里的$p_{i-1},p_k,p_j$均表示第i-1,k,j个矩阵的列数。n个矩阵的信息,只需要一个长度为n+1的数组来表示即可。

对于m[i][j]数组,只需要填入上三角中的元素即可(因为i<=j)。

五.代码实现

#include <iostream>
using namespace std;
int BestValue(int row[],int col[], int n);
int main(int argc, const char * argv[]) {int row[]={3,4,6};int col[]={4,6,11};cout<<BestValue(row, col, 3);return 0;
}
int BestValue(int row[],int col[], int n){if(n<=0){cout<<"error";return 0;}int m[40][40];int i,j,k,r,sum;for(i=0;i<n-1;i++){if(col[i]!=row[i+1]){cout<<"error"<<endl;return 0;}}for(i=0;i<n;i++){m[i][i]=0;}for(r=1;r<n;r++){for(j=r;j<n;j++){i=j-r;sum=m[i][i]+m[i+1][j]+row[i]*col[i]*col[j];for(k=i;k<j;k++){if(sum>m[i][k]+m[k+1][j]+row[i]*col[k]*col[j]){sum=m[i][k]+m[k+1][j]+row[i]*col[k]*col[j];}}m[i][j]=sum;}}return m[0][n-1];
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/211648.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【CentOS8】使用 Tomcat 部署 Java Web 项目(使用 sdkman)

文章目录 配置 Tomcat将 Tomcat 启动命令设置为 Linux 自定义服务给 Tomcat 设置管理员账号密码IDEA 打包 Java web 项目 我是使用 sdkman 下载的 jdk 和 tomcat&#xff0c;所以接下来的部署配置都是在 sdkman 构建的环境的。想要知道如何下载 sdkman 可以看看这篇文章 —…

【开源】基于Vue+SpringBoot的用户画像活动推荐系统

项目编号&#xff1a; S 061 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S061&#xff0c;文末获取源码。} 项目编号&#xff1a;S061&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 兴趣标签模块2.3 活…

Docker-多容器应用

一、概述 到目前为止&#xff0c;你一直在使用单个容器应用。但是&#xff0c;现在您将 MySQL 添加到 应用程序堆栈。经常会出现以下问题 - “MySQL将在哪里运行&#xff1f;将其安装在同一个 容器还是单独运行&#xff1f;一般来说&#xff0c;每个容器都应该做一件事&#x…

Vite4、Vue3、Axios 针对请求模块化封装搭配自动化导入(简单易用)

针对请求模块化封装搭配自动化导入&#xff08;简单易用&#xff09; 目标目录目标代码前提步入正题src / utils / index.jssrc /api / index.jssrc /api / request.jssrc /api / service.jssrc /api / utils.jssrc /api / modules / demo.js 自动化配置vite.config.jseslint 校…

AWS 日志分析工具

当您的网络资源托管在 AWS 中时&#xff0c;需要定期监控您的 AWS CloudTrail 日志、Amazon S3 服务器日志和 AWS ELB 日志等云日志&#xff0c;以降低任何潜在的安全风险、识别严重错误并确保满足所有合规性法规。 什么是 Amazon S3 Amazon Simple Storage Service&#xff…

德迅猎鹰(云蜜罐)有什么用

蜜罐&#xff08;Honeypot&#xff09;是一种安全技术&#xff0c;用于吸引和欺骗攻击者&#xff0c;以便收集关于攻击行为的信息和情报。它模拟了一个脆弱的系统、服务或网络资源&#xff0c;看起来对攻击者具有吸引力&#xff0c;但实际上是为了引诱攻击者暴露其攻击手法和意…

Flink Flink数据写入Kafka

一、环境准备 flink 1.14写入Kafka&#xff0c;首先在pom.xml文件中导入相关依赖 <properties><project.build.sourceEncoding>UTF-8</project.build.sourceEncoding><flink.version>1.14.6</flink.version><spark.version>2.4.3</spa…

案例052:用于日语词汇学习的微信小程序

文末获取源码 开发语言&#xff1a;Java 框架&#xff1a;SSM JDK版本&#xff1a;JDK1.8 数据库&#xff1a;mysql 5.7 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&#xff1a;Maven3.5.4 小程序框架&#xff1a;uniapp 小程序开发软件&#xff1a;HBuilder X 小程序…

AWS基于x86 vs Graviton(ARM)的RDS MySQL性能对比

概述 这是一个系列。在前面&#xff0c;我们测试了阿里云经济版&#xff08;“ARM”&#xff09;与标准版的性能/价格对比&#xff1b;华为云x86规格与ARM&#xff08;鲲鹏增强&#xff09;版的性能/价格对比。现在&#xff0c;再来看看AWS的ARM版本的RDS情况 在2018年&#…

第3章:知识表示:概述、符号知识表示、向量知识表示

&#x1f497;&#x1f497;&#x1f497;欢迎来到我的博客&#xff0c;你将找到有关如何使用技术解决问题的文章&#xff0c;也会找到某个技术的学习路线。无论你是何种职业&#xff0c;我都希望我的博客对你有所帮助。最后不要忘记订阅我的博客以获取最新文章&#xff0c;也欢…

有什么可视化数据管理工具?

有什么可视化数据管理工具&#xff1f; 相信大家对数据分析并不陌生。数据可视化不仅可以使得数据更加直观、易于理解&#xff0c;而且可以帮助用户发现数据中的潜在规律和趋势。 但是&#xff0c;对于不熟悉编程的用户来说&#xff0c;如何将枯燥的大数据转化为可视化的图和…

springboot——自动装配

自动装配 Condition: Condition内置方法&#xff1a;boolean matches(ConditionContext context, AnnotatedTypeMetadata metadata)&#xff0c;返回值为布尔型 重写matches方法的类&#xff1a;SpringBootCondition等 SpringBootCondition&#xff1a;springboot自带的实现类…

windows如何解决端口冲突(实用篇)

在项目设计中&#xff0c;环境配置成功点击运行瞬间&#xff0c;一大堆红爆出&#xff0c;8080端口占用&#xff0c;这个是很烦人的。。。 解决方式&#xff1a; 笨方法&#xff1a;一、查看所有端口实用情况&#xff08;挨个扫&#xff09; 按住【WINR】快捷键打开运行输入…

同旺科技 USB TO RS-485 定制款适配器--- 拆解(三)

内附链接 1、USB TO RS-485 定制款适配器 ● 支持USB 2.0/3.0接口&#xff0c;并兼容USB 1.1接口&#xff1b; ● 支持USB总线供电&#xff1b; ● 支持Windows系统驱动&#xff0c;包含WIN10 / WIN11系统32 / 64位&#xff1b; ● 支持Windows RT、Linux、Mac OS X、Windo…

同旺科技 USB TO RS-485 定制款适配器--- 拆解(二)

内附链接 1、USB TO RS-485 定制款适配器 ● 支持USB 2.0/3.0接口&#xff0c;并兼容USB 1.1接口&#xff1b; ● 支持USB总线供电&#xff1b; ● 支持Windows系统驱动&#xff0c;包含WIN10 / WIN11系统32 / 64位&#xff1b; ● 支持Windows RT、Linux、Mac OS X、Windo…

TA-Lib学习研究笔记(九)——Pattern Recognition (3)

TA-Lib学习研究笔记&#xff08;九&#xff09;——Pattern Recognition &#xff08;3&#xff09; 最全面的形态识别的函数的应用&#xff0c;通过使用A股实际的数据&#xff0c;验证形态识别函数&#xff0c;用K线显示出现标志的形态走势&#xff0c;由于入口参数基本上是o…

ROS-ROS通信机制-参数服务器

文章目录 一、基础理论知识二、C实现三、Python实现 一、基础理论知识 参数服务器在ROS中主要用于实现不同节点之间的数据共享。参数服务器相当于是独立于所有节点的一个公共容器&#xff0c;可以将数据存储在该容器中&#xff0c;被不同的节点调用&#xff0c;当然不同的节点…

安卓开发APP应用程序和苹果iOS开发APP应用程序有什么区别?

随着智能手机和平板电脑在全球的普及&#xff0c;APP移动应用已成为日常生活中不可或缺的组成部分。从社交网络到电子商务平台&#xff0c;从个人理财到游戏娱乐&#xff0c;APP几乎渗透了人们所有的活动领域。在开发APP时&#xff0c;开发者通常要面对两大主流平台&#xff1a…

Docker+jenkins+gitlab实现持续集成

1.安装环境 服务器ip虚拟机版本192.168.5.132centos7.6192.168.5.152centos7.6 2. 安装docker 安装必要的一些系统工具 yum install -y yum-utils device-mapper-persistent-data lvm2添加软件源信息&#xff0c;要确保centos7能上外网 yum-config-manager --add-repo http:…

西工大计算机学院计算机系统基础实验一(函数编写1~10)

还是那句话&#xff0c;千万不要慌&#xff0c;千万不要着急&#xff0c;耐下性子慢慢来&#xff0c;一步一个脚印&#xff0c;把基础打的牢牢的&#xff0c;一样不比那些人差。回到实验本身&#xff0c;自从​​​​​​按照西工大计算机学院计算机系统基础实验一&#xff08;…