动态规划之矩阵连乘

动态规划算法：

1.找出最优解的性质，并刻画其结构特征

2.递归的定义最优值

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

4.根据计算最优值时得到的信息，构造一个最优解

 1.分解最优解的结构

将矩阵连乘积Ai.....Aji:j]，计算A[1:n]的一个最优次序，设这个计算次序在矩阵Ak和Ak+1之间断开，加括号的方式为((A1A2...Ak)(Ak+1Ak+2....An))，这个问题的关键是一个最优次序所包含的计算矩阵子问题次序夜市最优的。矩阵连乘积计算次序问题的最优解包含着其子问题的最优解，这种性质称为最优子结构性质。

2.建立递归关系

计算A[i][j]所需的最少数乘次数为m[i][j]，则原问题的最优值为m[1][n]。

当i=j时，A[i:j]=A为单一矩阵，无需计算，m[i][i]=0

当i<j时，可是由最优子结构性质来计算，但我们不知道断开点k的位置，所以k未定，但k有j-i个可能位置，k是j-i个位置中使得计算量达到最小的那个位置。

若将对应于m[i][j]的断开位置k记为s[i][j]，在计算最优值m[i][j]后，可递归的由s[i][j]狗做出相应的最优解。

3.计算最优解

用动态规划算法解决此问题，依据其递归式子以自底向上的方式进行计算，在计算过程中，保存已解决的子问题答案，每个子问题只计算一次，在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间算法，处理计算最优值的数组外，还输出记录最优断开位置的数组。 

 4.构造最优解

目前只给出了最优值，没有给出最优解，通过计算，我们只知道要计算所给矩阵连乘积所需的最少数乘次数，还不知道具体应该按照什么次序来做矩阵乘法。s[i][j]中的告诉我们计算矩阵链A[i:j]的最佳方式应该在矩阵Ak和Ak+1，逐层递推就可以确定A[1:n]的最优计算次序。

class Matrix:
    def __init__(self,row_num=0,col_num=0,matrix=None):
        if matrix != None:
            self.row_num = len(matrix)
            self.col_num = len(matrix[0])
        else:
            self.row_num = row_num
            self.col_num = col_num
        self.matrix = matrix

def matrix_chain(matrixs):
    matrix_num = len(matrixs)
    # 生成两个二维数组
    # 存储最优值
    count = [[0 for j in range(matrix_num)] for i in range(matrix_num)]
    # 存储K值
    flag = [[0 for j in range(matrix_num)] for i in range(matrix_num)]
    
    for interval in range(1,matrix_num+1):
        for i in range(matrix_num-interval):
            j = i + interval
            count[i][j] = count[i][i] + count[i+1][j] + matrixs[i].row_num*matrixs[i+1].row_num *matrixs[j].col_num
            # 将断开的位置记在flag中
            flag[i][j] = i
            for k in range(i+1,j):
                temp = count[i][k]+count[k+1][j]+matrixs[i].row_num*matrixs[k+1].row_num*matrixs[j].col_num
                if temp<count[i][j]:
                    count[i][j] = temp
                    flag[i][j] =k
    traceback(0,matrix_num-1,flag)
    return count[0][matrix_num-1]

# 输出最优解
def traceback(i,j,flag):
    if i == j:
        return
    if j-i>1:
        print(str(i+1)+'~'+str(j+1),end=':')
        print(str(i+1)+":"+str(flag[i][j]+1),end=',')
        print(str(flag[i][j]+2)+":"+str(j+1))
    traceback(i,flag[i][j],flag)
    traceback(flag[i][j]+1,j,flag)


matrixs = [Matrix(30,35),Matrix(35,15),Matrix(15,5),Matrix(5,10),Matrix(10,20),Matrix(20,25)]
result = matrix_chain(matrixs)
print(result)

运行结果：
1~6:1:3,4:6
1~3:1:1,2:3
4~6:4:5,6:6
15125

package com.company;

public class Main {
    //求解最优值
    public static int matrixChain(int[] p, int[][] m, int[][] s) {
        int n = p.length - 1;
        for (int i = 1; i <= n; i++)
            //本身为0
            m[i][i] = 0; //初始化二维数组
        for (int r = 2; r <= n; r++) {
            for (int i = 1; i <= n - r + 1; i++) {
                int j = i + r - 1;
                //先以i进行化为
                m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];//求出Ai到Aj的连乘
                s[i][j] = i;//记录划分位置
                for (int k = i + 1; k < j; k++) {
                    //寻找是否有可优化的分割点
                    int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];//公式
                    if (t < m[i][j]) {
                        m[i][j] = t;
                        s[i][j] = k;
                    }
                }

            }
        }
        return m[1][n];

    }

    //输出A[i][j]的最优计算次序
    public static void traceback(int i, int j, int[][] s) {
        //输出A[i:j]的最有计算次序
        if (i == j) {
            //递归出口
            System.out.print("A" + i);
            return;
        } else {
            System.out.print("(");
            //递归的输出左边
            traceback(i, s[i][j], s);
            //递归的输出右边
            traceback(s[i][j] + 1, j, s);
            System.out.print(")");
        }
    }


    public static void main(String[] args) {
        int[] p = new int[]{5, 7, 4, 3, 5};
        int[][] m = new int[p.length][p.length];
        int[][] s = new int[p.length][p.length];
        System.out.println("最优值为： " + matrixChain(p, m, s));
        traceback(1, p.length - 1, s);


    }

}

运行结果：
最优值为： 264
((A1(A2A3))A4)

以上涉及代码是借鉴其他博主滴，自己没有复现出来~