算法笔记_003:矩阵相乘问题【分治法】

目录

1 问题描述 

1.1实验题目

1.2实验目的

1.3实验要求

2 解决方案

2.1 分治法原理简述

2.2 分治法求解矩阵相乘原理

2.3 具体实现源码

2.4 运算结果截图


1 问题描述

1.1实验题目

设M1和M2是两个n×n的矩阵,设计算法计算M1×M2 的乘积。

1.2实验目的

(1)提高应用蛮力法设计算法的技能;

(2)深刻理解并掌握分治法的设计思想;

(3)理解这样一个观点:用蛮力法设计的算法,一般来说,经过适度的努力后,都可以对其进行改进,以提高算法的效率。

1.3实验要求

(1)设计并实现用BF(Brute-Force,即蛮力法)方法求解矩阵相乘问题的算法;

(2)设计并实现用DAC(Divide-And-Conquer,即分治法)方法求解矩阵相乘问题的算法;

(3)以上两种算法的输入既可以手动输入,也可以自动生成;

(4)对上述两个算法进行时间复杂性分析,并设计实验程序验证分析结果;

(5)设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。


2 解决方案

2.1 分治法原理简述

分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

如果原问题可分割成k个子问题,1<k≤n ,且这些子问题都可解并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。

分治法所能解决的问题一般具有以下几个特征:

1) 该问题的规模缩小到一定的程度就可以容易地解决

2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。

3) 利用该问题分解出的子问题的解可以合并为该问题的解;

4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。

2.2 分治法求解矩阵相乘原理

首先了解一下传统计算矩阵相乘的原理:

其次,看一下优化后的矩阵相乘法原理:

最后,看一下本文利用分治法求解矩阵相乘的原理(PS:本文求解其效率不是最高,主要是体验一下分治法,重点在于分治法):

注意:使用分治法求解两个nxn阶矩阵相乘,其中n值为2的幂值,否则只能使用蛮力法计算。

本文具体源码主要根据以上分块矩阵方法,先分块(即使用分治法),然后递归求解。

2.3 具体实现源码

package com.liuzhen.dac;

public class Matrix {

    //初始化一个随机nxn阶矩阵
    public static int[][] initializationMatrix(int n){
        int[][] result = new int[n][n];
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                result[i][j] = (int)(Math.random()*10); //采用随机函数随机生成1~10之间的数
            }
        }
        return result;
    }

    //蛮力法求解两个nxn和nxn阶矩阵相乘
    public static int[][] BruteForce(int[][] p,int[][] q,int n){
        int[][] result = new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                result[i][j] = 0;
                for(int k=0;k<n;k++){
                    result[i][j] += p[i][k]*q[k][j];
                }
            }
        }
        return result;
    }

    //分治法求解两个nxn和nxn阶矩阵相乘
    public static int[][] DivideAndConquer(int[][] p,int[][] q,int n){
        int[][] result = new int[n][n];
        //当n为2时,返回矩阵相乘结果
        if(n == 2){
            result = BruteForce(p,q,n);
            return result;
        }

        //当n大于3时,采用采用分治法,递归求最终结果
        if(n > 2){
            int m = n/2;

            int[][] p1 = QuarterMatrix(p,n,1);
            int[][] p2 = QuarterMatrix(p,n,2);
            int[][] p3 = QuarterMatrix(p,n,3);
            int[][] p4 = QuarterMatrix(p,n,4);
//            System.out.println();
//            System.out.print("矩阵p1值为:");
//            PrintfMatrix(p1,m);
//            System.out.println();
//            System.out.print("矩阵p2值为:");
//            PrintfMatrix(p2,m);
//            System.out.println();
//            System.out.print("矩阵p3值为:");
//            PrintfMatrix(p3,m);
//            System.out.println();
//            System.out.print("矩阵p4值为:");
//            PrintfMatrix(p4,m);

            int[][] q1 = QuarterMatrix(q,n,1);
            int[][] q2 = QuarterMatrix(q,n,2);
            int[][] q3 = QuarterMatrix(q,n,3);
            int[][] q4 = QuarterMatrix(q,n,4);

            int[][] result1 = QuarterMatrix(result,n,1);
            int[][] result2 = QuarterMatrix(result,n,2);
            int[][] result3 = QuarterMatrix(result,n,3);
            int[][] result4 = QuarterMatrix(result,n,4);

            result1 = AddMatrix(DivideAndConquer(p1,q1,m),DivideAndConquer(p2,q3,m),m);
            result2 = AddMatrix(DivideAndConquer(p1,q2,m),DivideAndConquer(p2,q4,m),m);
            result3 = AddMatrix(DivideAndConquer(p3,q1,m),DivideAndConquer(p4,q3,m),m);
            result4 = AddMatrix(DivideAndConquer(p3,q2,m),DivideAndConquer(p4,q4,m),m);

            result = TogetherMatrix(result1,result2,result3,result4,m);
        }
        return result;
    }

    //获取矩阵的四分之一,并决定返回哪一个四分之一
    public static int[][] QuarterMatrix(int[][] p,int n,int number){
        int rows = n/2;   //行数减半
        int cols = n/2;   //列数减半
        int[][] result = new int[rows][cols];
        switch(number){
           case 1 :
           {
              // result = new int[rows][cols];
               for(int i=0;i<rows;i++){
                   for(int j=0;j<cols;j++){
                       result[i][j] = p[i][j];
                   }
               }
               break;
           }

           case 2 :
           {
              // result = new int[rows][n-cols];
               for(int i=0;i<rows;i++){
                   for(int j=0;j<n-cols;j++){
                       result[i][j] = p[i][j+cols];
                   }
               }
               break;
           }

           case 3 :
           {
              // result = new int[n-rows][cols];
               for(int i=0;i<n-rows;i++){
                   for(int j=0;j<cols;j++){
                       result[i][j] = p[i+rows][j];
                   }
               }
               break;
           }

           case 4 :
           {
              // result = new int[n-rows][n-cols];
               for(int i=0;i<n-rows;i++){
                   for(int j=0;j<n-cols;j++){
                       result[i][j] = p[i+rows][j+cols];
                   }
               }
               break;
           }

           default:
               break;
        }

        return result;
     }

    //把均分为四分之一的矩阵,聚合成一个矩阵,其中矩阵a,b,c,d分别对应原完整矩阵的四分中1、2、3、4
    public static int[][] TogetherMatrix(int[][] a,int[][] b,int[][] c,int[][] d,int n){
        int[][] result = new int[2*n][2*n];
        for(int i=0;i<2*n;i++){
            for(int j=0;j<2*n;j++){
                if(i<n){
                    if(j<n){
                        result[i][j] = a[i][j];
                    }
                    else
                        result[i][j] = b[i][j-n];
                }
                else{
                    if(j<n){
                        result[i][j] = c[i-n][j];
                    }
                    else{
                        result[i][j] = d[i-n][j-n];
                    }
                }
            }
        }

        return result;
    }

    //求两个矩阵相加结果
    public static int[][] AddMatrix(int[][] p,int[][] q,int n){
        int[][] result = new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                result[i][j] = p[i][j]+q[i][j];
            }
        }
        return result;
    }

    //控制台输出矩阵
    public static void PrintfMatrix(int[][] matrix,int n){
        for(int i=0;i<n;i++){
            System.out.println();
            for(int j=0;j<n;j++){
                System.out.print("\t");
                System.out.print(matrix[i][j]);
            }
        }

    }

    public static void main(String args[]){
        int[][] p = initializationMatrix(8);
        int[][] q = initializationMatrix(8);
        System.out.print("矩阵p初始化值为:");
        PrintfMatrix(p,8);
        System.out.println();
        System.out.print("矩阵q初始化值为:");
        PrintfMatrix(q,8);

        int[][] bf_result = BruteForce(p,q,8);
        System.out.println();
        System.out.print("蛮力法计算矩阵p*q结果为:");
        PrintfMatrix(bf_result,8);

        int[][] dac_result = DivideAndConquer(p,q,8);
        System.out.println();
        System.out.print("分治法计算矩阵p*q结果为:");
        PrintfMatrix(dac_result,8);
    }

}

2.4 运算结果截图

参考资料:

    1、009-矩阵乘法-分治法-《算法设计技巧与分析》M.H.A学习笔记

 2、 Strassen矩阵乘法(分治法续)

时间: 11-30

算法笔记_003:矩阵相乘问题【分治法】的相关文章

算法实验:分治法合并排序(C++)

这篇文章分两部分来写,第一部分写代码的实现过程,第二部分把实验报告从头到尾呈现出来. 我习惯调试使用的编译器是DEV C++,不是vs系列的,可能头文件上有点区别.但是下面的报告是我放到vs里面测试过的,可以直接用,不影响. 第一部分:(解析) 题目:随机产生一个整型数组,然后用合并排序将该数组做升序排列,要求输出排序前和排序后的数组. 题目分析: 需要随机产生一个整数数组: 采用的算法是合并排序,也就是用归并排序: 输出排序后的数组. 随机产生一个整数数组:这个问题首先想到的是用rand()函

算法笔记_065:分治法求逆序对(Java)

目录 1 问题描述 2 解决方案 2.1 蛮力法 2.2 分治法(归并排序)   1 问题描述 给定一个随机数数组,求取这个数组中的逆序对总个数.要求时间效率尽可能高. 那么,何为逆序对? 引用自百度百科: 设 A 为一个有 n 个数字的有序集 (n>1),其中所有数字各不相同. 如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j],则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对,也称作逆序数. 例如,数组(3,1,4,5,

分治法、动态规划、回溯法、分支界限法、贪心算法

转:http://blog.csdn.net/lcj_cjfykx/article/details/41691787 分治算法一.基本概念 在计算机科学中,分治法是一种很重要的算法.字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并.这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)…… 任何一个可以用计算机求解的问题所需的计算时

C语言 &#183; 矩阵相乘 &#183; 算法提高

算法提高 矩阵相乘 时间限制:1.0s   内存限制:256.0MB 问题描述 小明最近在为线性代数而头疼,线性代数确实很抽象(也很无聊),可惜他的老师正在讲这矩阵乘法这一段内容. 当然,小明上课打瞌睡也没问题,但线性代数的习题可是很可怕的. 小明希望你来帮他完成这个任务. 现在给你一个ai行aj列的矩阵和一个bi行bj列的矩阵, 要你求出他们相乘的积(当然也是矩阵). (输入数据保证aj=bi,不需要判断) 输入格式 输入文件共有ai+bi+2行,并且输入的所有数为整数(long long范围

稀疏矩阵的三元组顺序表存储及矩阵相乘算法小结

稀疏矩阵的三元组顺序表存储及矩阵相乘算法小结 巧若拙(欢迎转载,但请注明出处:http://blog.csdn.net/qiaoruozhuo) 一:稀疏矩阵的三元组顺序表数据结构 typedef int ElemType; typedef struct { intx, y;  //该非零元素的行下标和列下标 ElemTypee; //该非零元素的值 } Triple; typedef struct { Tripledata[MAXSIZE]; //非零元素三元组顺序表 intmu, nu, t

动态规划和分治法,贪心算法以及递归的再一次深刻理解和体会

每次体会算法都有新的感觉,刷题越多,对算法的理解感觉也就越深刻. 下面我们来重新体会下分治法,动态规划,贪心法,递归的理解. 1.分治法: 将问题分成单独的阶段,每个阶段互相不干扰很独立,如10米长的木棍,切成10段,每段去解决每一段的问题.(阶段没有关系) 2.贪心法 站在全局的角度,也是将问题堪称分为多个阶段,只不过阶段和阶段之间有一定的递进关系,如从5毛,1元,2毛,1毛,2元中,去找最少的钱币构成10块钱.首先是站在全局的角度,先从中取其最大值,为第一阶段,然后在从剩余的当中在找最大值,

算法(二)--------分治法

分治法的适?条件: • 该问题的规模缩?到?定程度就可以容易地解决.• 该问题可以分解为若?个规模较?的相同问题:递归思想的应?• 该问题所分解出的各个?问题是相互独?的,即?问题之间不包含公共的?问题.• 利?该问题分解出的?问题的解可以合并为该问题的解. 案例---快排: (1)过程 • Divide (Partition) – 对元素进?重排以得到这样?个划分 • 在某个位置s前?的所有元素都?于等于A[s] • 在位置s后?的所有元素都?于等于A[s]• Conquer: ?个划分确定后

算法---分治法

1.分治法的思想: 将一个输入规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同,然后递归的求解这些子问题,最后用适当的方法将各子问题的解合并成原问题的解. 2.分治法的步骤: 分(divide) 二分为主 治(conquer) 递归调用,当规模足够小时直接处理 组(combine) 3.抽象化控制 procedure DANDC(p,q) global n, A(1:n); integer m, p, q; //1≤p≤q≤n// if SMALL(p,q) //判断输

算法设计《分治法》归并排序(三)实例分析之逆序对数

问题定义: 假设A[1...n]是一个有n个不同数的数组.若i<j且A[i]>A[j]则称(A[i], A[j])为数组A的一个逆序对. 例如数组<2, 3, 8, 6, 1>有(2, 1),(3, 1),(8, 6),(8, 1)和(6,1)5个逆序对. 对于这个问题,直观上进行求解的话,使用暴力求解的方式的话,对于每个数num,都遍历数组中num后的所有数的话,则时间复杂度为O(n^2). 实现代码如下: 另一种方式,便是使用分治法,首先将整个数组分成两部分,然后,分别求解两个