算法设计:实验三动态规划法

2024-08-28 23:52

本文主要是介绍算法设计:实验三动态规划法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【实验目的】

应用动态规划算法思想求解矩阵连乘的顺序问题。

【实验要求】         

应用动态规划算法的最优子结构性质和子问题重叠性质求解此问题。分析动态规划算法的基本思想,应用动态规划策略写出算法及相应的程序,求解此题。要读懂读透A[i,j],

A[1,n]=A[1,k] ×A[k+1,n],m[i][j],s[i][j]各式所表达的含义并正确加以应用。m[i][j]的递归定义:

要求完成:⑴算法描述⑵写出程序代码⑶完成调试⑷进行过程与结果分析。

【实验内容】

对于下列所描述的问题,给出相应的算法描述,并完成程序实现与时间复杂度的分析。该问题描述为:一般地,考虑矩阵A1,A2,… ,An的连乘积,它们的维数分别为d0,d1,…,dn,即Ai的维数为di-1×di  (1≤i≤n)。确定这n个矩阵的乘积结合次序,使所需的总乘法次数最少。对应于乘法次数最少的乘积结合次序为这n个矩阵的最优连乘积次序。按给定的一组测试数据对根据算法设计的程序进行调试:6个矩阵连乘积A=A1×A2×A3×A4×A5×A6,各矩阵的维数分别为:A1:10×20,A2:20×25,A3:25×15,A4:15×5,A5:5×10,A6:10×25。完成测试。

【算法思想及处理过程】

动态规划(Dynamic Programming,简称 DP)是一种通过将原问题分解为相互重叠的子问题,并通过对这些子问题的解进行存储和复用,从而避免重复计算,以提高算法效率的方法。其基本思想是利用子问题的最优解构建原问题的最优解,通过填表格或者使用递归加记忆化的方法来实现。

在矩阵连乘最优化问题中,动态规划的基本思想是:

问题拆解:

将原问题拆解为子问题。对于矩阵连乘问题,给定一系列矩阵 A1, A2, ..., An,每个矩阵 Ai 的维度为 di-1 x di,目标是找到一种矩阵相乘的顺序,使得总的乘法次数最少。这个问题可以拆解为子问题:对于任意子链 Ai x ... x Aj,找到其最优的连乘次序。

定义状态:

定义状态 m[i][j],表示矩阵链 Ai x ... x Aj 的最优乘法次数。同时定义 s[i][j],表示最优的分割点,即在哪里将链 Ai x ... x Aj 分割成两部分进行连乘。

递推关系:

通过递推关系式来计算 m[i][j] 的值,即:

其中 d_{i-1} x d_k x d_j 是将两部分子链 Ai x ... x Ak 和 Ak+1 x ... x Aj 连乘的乘法次数。

填表:

使用动态规划的方法填充表格 m[i][j] 和 s[i][j],首先填充长度为 1 的链(单个矩阵的情况),再逐步增加长度,直至填满整个表格。

构造解:

根据填表得到的 s[i][j],通过递归或迭代的方式构造出最优的连乘次序。

综上所述,动态规划解决矩阵连乘最优化问题的基本思路是利用子问题的最优解构建原问题的最优解,通过填表格并使用递推关系来计算最优解的值,最终通过构造解得到最优的矩阵连乘次序。

以下是确定最优解的流程图:

主要思路为计算m时只需要m的左边与下边的数组值,所以可以从下至上,从左至右计算。

以下是打印最优连乘矩阵次序函数流程图:

递归终止条件:

首先,递归函数 printOptimal 需要处理递归的终止条件。当 i == j 时,表示当前子链只有一个矩阵,此时直接打印该矩阵的名称即可,因为不需要再进行连乘,已经是最小单位了。

利用 s 数组确定分割点:

对于子链 Ai x ... x Aj,s[i][j] 记录了使得乘法次数最少的分割点 k。因此,在递归调用中,我们首先根据 s[i][j] 将当前子链分成两部分:

第一部分:从 i 到 s[i][j] 的子链

第二部分:从 s[i][j] + 1 到 j 的子链

这样可以保证递归地构建出最优的连乘次序。

递归调用:

在分割好子链之后,递归地调用 printOptimal 函数:

对于第一部分:调用 printOptimal(matrices, s, i, s[i][j])

对于第二部分:调用 printOptimal(matrices, s, s[i][j] + 1, j)

这样可以递归地将整个矩阵连乘问题拆解为更小规模的子问题,直到达到终止条件为止。

输出格式控制:

在递归调用结束后,根据递归的层级,添加括号和矩阵名称,以构建出最优的连乘次序表达式。

【程序代码】

#include <stdio.h>
#include <limits.h>
#include <string.h>#define MAX_SIZE 100
#define MAX 9999999 typedef struct {char name[20];int rows;int cols;
} Matrix;// 计算最优连乘矩阵次序
void matrixOptimal(Matrix matrices[], int num, int m[MAX_SIZE][MAX_SIZE], int s[MAX_SIZE][MAX_SIZE]) {int i,j,k,l,flag;for (i = 1; i <= num; i++) {m[i][i] = 0;}// 计算子问题的最优解 for(j = 1; j <= num; j++){for(i = j-1;i > 0; i--){m[i][j] = MAX;for (k = i; k < j; k++) {flag = m[i][k] + m[k+1][j] + matrices[i].rows * matrices[k].cols * matrices[j].cols;if (flag < m[i][j]) {m[i][j] = flag;s[i][j] = k;}}}}/*for (l = 2; l <= num; l++) {  // l 为连乘链的长度for (i = 1; i <= num - l + 1; i++) {j = i + l - 1;m[i][j] = MAX;for (k = i; k < j; k++) {flag = m[i][k] + m[k+1][j] + matrices[i].rows * matrices[k].cols * matrices[j].cols;if (flag < m[i][j]) {m[i][j] = flag;s[i][j] = k;}}}}*/
}// 打印最优连乘矩阵次序
void printOptimal(Matrix matrices[], int s[MAX_SIZE][MAX_SIZE], int i, int j) {if (i == j) {printf("%s", matrices[i].name);} else {printf("(");printOptimal(matrices, s, i, s[i][j]);printOptimal(matrices, s, s[i][j] + 1, j);printf(")");}
}int main() {Matrix matrices[MAX_SIZE];int num;int i,j;printf("输入矩阵个数:");scanf("%d", &num);printf("输入每个矩阵的名称和维度:\n");for (i = 1; i <= num; i++) {printf("矩阵 %d名称: ", i);scanf("%s", matrices[i].name);printf("维数: ");scanf("%d %d", &matrices[i].rows, &matrices[i].cols);// 对第一个矩阵不进行维度检查 if (i > 1) {if (matrices[i-1].cols != matrices[i].rows) {printf("错误:矩阵维度不匹配,请重新输入。\n");i--;}}}int m[MAX_SIZE][MAX_SIZE];  // 存储最小乘法次数int s[MAX_SIZE][MAX_SIZE];  // 存储最优分割点matrixOptimal(matrices, num, m, s);printf("------------------------------------");printf("\n数组 m:\n");for (i = 1; i <= num; i++) {for (j = 1; j <= num; j++) {printf("%d\t", m[i][j]);}printf("\n");}printf("\n数组 s:\n");for (i = 1; i <= num; i++) {for (j = 1; j <= num; j++) {printf("%d\t", s[i][j]);}printf("\n");}printf("------------------------------------\n");printf("所需的总乘法次数为:%d\n", m[1][num]);printf("最优连乘积次序为:");printOptimal(matrices, s, 1, num);printf("\n");return 0;
}

【运行结果】

【算法分析】

算法思路:

这个算法利用动态规划的思想解决矩阵连乘最优化问题。首先,通过 matrixOptimal 函数计算出最小乘法次数 m[i][j] 和最优分割点 s[i][j],然后通过 printOptimal 函数根据 s 数组打印出最优的连乘次序。

时间复杂度分析:

计算 m[i][j] 和 s[i][j] 的时间复杂度:

外层循环 for (j = 1; j <= num; j++) 循环次数为 num,内层循环 for (i = j-1; i > 0; i--) 的平均循环次数约为 num/2。内部的循环 for (k = i; k < j; k++) 的循环次数约为 j - i,因此计算 m[i][j] 和 s[i][j] 的时间复杂度大致为 O(num^3)。

打印最优连乘次序的时间复杂度:

printOptimal 函数的时间复杂度主要取决于矩阵链的长度 num,递归调用的次数是 O(num),因此其时间复杂度也是 O(num)。

总体时间复杂度:

综合考虑,整个算法的时间复杂度主要由计算 m[i][j] 和 s[i][j] 的过程决定,即 O(num^3)。其余部分包括输入矩阵信息和打印结果的时间复杂度较小,对总体复杂度影响较小。

因此,该算法的时间复杂度为 O(num^3),其中 num 是矩阵的个数。对于较大的矩阵个数,算法的执行时间会随着 num 的增加而增加。需要注意的是,在实际应用中,可以考虑优化算法以降低时间复杂度,例如通过记忆化搜索等方法减少重复计算,或者使用更高效的算法来解决矩阵连乘问题。

这篇关于算法设计:实验三动态规划法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

springboot如何通过http动态操作xxl-job任务

《springboot如何通过http动态操作xxl-job任务》:本文主要介绍springboot如何通过http动态操作xxl-job任务的问题,具有很好的参考价值,希望对大家有所帮助,如有错... 目录springboot通过http动态操作xxl-job任务一、maven依赖二、配置文件三、xxl-

MyBatis设计SQL返回布尔值(Boolean)的常见方法

《MyBatis设计SQL返回布尔值(Boolean)的常见方法》这篇文章主要为大家详细介绍了MyBatis设计SQL返回布尔值(Boolean)的几种常见方法,文中的示例代码讲解详细,感兴趣的小伙伴... 目录方案一:使用COUNT查询存在性(推荐)方案二:条件表达式直接返回布尔方案三:存在性检查(EXI

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢?今天,我们... 目录方法1:C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1:创建C#类库(.NET

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可

Mybatis嵌套子查询动态SQL编写实践

《Mybatis嵌套子查询动态SQL编写实践》:本文主要介绍Mybatis嵌套子查询动态SQL编写方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、实体类1、主类2、子类二、Mapper三、XML四、详解总结前言MyBATis的xml文件编写动态SQL

SpringBoot实现Kafka动态反序列化的完整代码

《SpringBoot实现Kafka动态反序列化的完整代码》在分布式系统中,Kafka作为高吞吐量的消息队列,常常需要处理来自不同主题(Topic)的异构数据,不同的业务场景可能要求对同一消费者组内的... 目录引言一、问题背景1.1 动态反序列化的需求1.2 常见问题二、动态反序列化的核心方案2.1 ht

golang实现动态路由的项目实践

《golang实现动态路由的项目实践》本文主要介绍了golang实现动态路由项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习... 目录一、动态路由1.结构体(数据库的定义)2.预加载preload3.添加关联的方法一、动态路由1

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.