矩阵连乘(动态规划)

简介: 题目描述:给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。

题目描述:给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。例如:

  A1={30x35} ; A2={35x15} ;A3={15x5} ;A4={5x10} ;A5={10x20} ;A6={20x25} ;

最后的结果为:((A1(A2A3))((A4A5)A6)) 最小的乘次为15125。

思路:动态规划算法解此问题,可依据其递归式以自底向上的方式进行计算(即先从最小的开始计算)。在计算过程中,保存已解决的子问题答案。每个子问题只计算一次,而在后面需要时只要简单查一下,从而避免大量的重复计算,最终得到多项式时间的算法。

这里写图片描述


public class Test {
    private static final int  count = 6;
    /**
     * 存储的是i+1到j+1的最小乘次,因为是从0开始
     */
    static int[][] min_part = new int[count][count];

    /**
     * 计算矩阵最小乘次数
     * @param p 保存矩阵行列的数组
     * @param n 矩阵的个数
     * @param min_part 保存最小乘次数
     * @return
     */
    public static int function(int[] p, int n, int[][]min_part) {
        int j = 0;

        for (int i = 0; i < n; i++) {
            min_part[i][i] = 0;
        }

        //r为连乘矩阵的个数
        for (int r = 2; r <= n; r++) {
            //i表示连乘矩阵的第一个,从连乘矩阵个数为2开始计算 需要算n-r个
            for (int i = 0; i <= n - r; i++) {
                //j表示连乘矩阵中的最后一个
                j = i + r - 1;
                min_part[i][j] = Integer.MAX_VALUE;

                for (int k = i; k <= j-1; k++) {
                    //在第一个与最后一个之间寻找最合适的断开点
                    int tmp = min_part[i][k] + min_part[k+1][j] + p[i]*p[k+1]*p[j+1];

                    if (tmp < min_part[i][j]) {
                        min_part[i][j] = tmp;
                    }
                }
            }
        }
        return min_part[0][n-1];
    }

    public static void main(String[] args) {
        int[] p = new int[count+1];
        p[0] = 30;
        p[1] = 35;
        p[2] = 15;
        p[3] = 5;
        p[4] = 10;
        p[5] = 20;
        p[6] = 25;

        int ans = function(p,count,min_part);
        System.out.println(ans);
    }
}

从2个矩阵开始计算: m[0][1] m[1][2] m[2][3] m[3][4] m[4][5] //m[0][1]表示第一个矩阵与第二个矩阵的最小乘次数、

以此类推 3个矩阵计算m[0][2] m[1][3] m[2][4] m[3][5]
。。。
一直到6个矩阵计算 m[0][5]即为结果

每次计算均取到上一矩阵计算保存的结果

目录
相关文章
|
存储 人工智能 算法
秒懂算法 | 矩阵连乘问题
给定n个矩阵{A1,A2,A3,…,An},其中Ai与Ai+1(i=1,2,3,…,n-1)是可乘的。用加括号的方法表示矩阵连乘的次序,不同加括号的方法所对应的计算次序是不同的。
1872 0
秒懂算法 | 矩阵连乘问题
|
9月前
|
人工智能 自然语言处理 安全
2026年部署OpenClaw Skills实战记录:零基础用户从零打造远程服务器巡检技能
在AIOps领域飞速发展的今天,Agent Skills凭借轻量化、高定制性的优势,逐渐替代传统MCP方案,成为智能运维的核心工具。而OpenClaw作为开源AI助手的佼佼者,不仅支持多平台对接与本地部署,更提供了极简的Skills定制能力——无需复杂编码,通过自然语言交互即可生成专属功能模块。本文以企业高频需求的“远程Linux服务器巡检”为例,详细拆解OpenClaw Skills的开发全流程,涵盖需求定义、交互配置、文件解析、测试优化等核心环节,搭配可直接复用的代码模板与阿里云快速部署方案,确保零基础用户也能快速上手,全程不改变原意,不含无关平台信息。
1998 1
|
5月前
|
自然语言处理 Java API
阿里云机器翻译对接使用完全指南:从开通服务到生产级部署
本文提供了一份完整的阿里云机器翻译对接使用指南。首先需登录控制台开通机器翻译服务,新用户享有每月100万字符免费额度。阿里云机器翻译提供通用版、专业版和定制版三类引擎,分别适用于日常翻译、垂直领域精准翻译和专属模型定制场景。对接方式支持控制台快速测试、SDK编程调用(Java、Python、Go、PHP、.NET等)以及原生HTTP API调用。API采用RPC风格签名机制,调用TranslateGeneral接口即可实现文本翻译,支持text和html两种输入格式。此外还提供批量翻译、异步长文本翻译、图片翻译和文档翻译等多种能力。安全管理方面建议使用RAM子账号和最小权限原则,避免主账号Ac
|
11月前
|
机器学习/深度学习 人工智能 自然语言处理
构建AI智能体:六十七、超参数如何影响大模型?通俗讲解原理、作用与实战示例
超参数是机器学习模型训练前需要人工设定的参数,它们控制着模型的学习过程而非直接通过学习获得。文章通过生动的类比(如自行车调整、烹饪配方)解释了超参数的概念,并详细介绍了其调优流程、常见类型(学习率、批量大小等)及对模型的影响。通过实际代码示例,展示了不同超参数设置如何影响模型训练效果,强调合理调优对提升模型性能、防止过拟合和优化资源使用的重要性。文章指出,超参数调优是模型成功的关键,初学者可从默认值开始逐步实验,借助网格搜索等工具实现高效调参。
924 105
|
10月前
|
人工智能 数据可视化 算法
构建AI智能体:八十七、KM与Chinchilla法则:AI模型发展的两种训练法则完全解析
摘要: 大模型训练中,如何在有限计算预算(C≈6ND)下最优分配模型参数量(N)与训练数据量(D)是关键挑战。KM扩展法则主张“模型优先”,认为增大N的收益高于D(α=0.076<β=0.103),推荐N∝C^0.73、D∝C^0.27。Chinchilla法则则通过实验发现大模型普遍训练不足,提出平衡策略(α=β≈0.38),推荐N∝D∝C^0.5,即在相同预算下减小模型规模并大幅增加数据量,可提升性能。
998 11
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
1841 1
|
机器学习/深度学习 人工智能 运维
|
机器学习/深度学习 数据采集 自然语言处理
99_监督微调:Alpaca数据集格式与实现
在大语言模型(LLM)的开发和应用中,微调是将通用预训练模型转化为特定任务专家的关键步骤。监督微调(Supervised Fine-Tuning, SFT)作为微调的一种重要范式,通过人工标注的高质量数据集指导模型学习特定任务的输入输出模式,从而显著提升模型在目标任务上的性能。
1792 0
|
机器学习/深度学习 存储 人工智能
【AI系统】为什么 GPU 适用于 AI
本文探讨了GPU在AI计算中的应用,从卷积计算的基本原理入手,解析了GPU线程分级与AI计算模式的关系,以及矩阵乘法如何通过GPU编程提升算力利用率。文章还介绍了计算强度的概念,分析了不同数据结构对计算强度的影响,以及GPU中Tensor Core的作用,强调了在不同存储位置下,找到计算强度与矩阵大小的最佳平衡点对AI计算系统优化的重要性。
1487 2

热门文章

最新文章