矩阵连乘问题

矩阵连乘

矩阵连乘是一个经典的动态规划问题

算法实现

package com.dwx.passage3;

public class MatrixChain {
    //整数矩阵连乘
    /*
    * p[]: 输入参数
    * m[]:最优值数组
    * s[]:最优断开位置数组
    * r:子链长度
    * n:我们要求的链的长度*/
    private int[] p;
    private int[][] m;
    private int[][] s;
    private int r;
    private int n;

    public int[] getP() {
        return p;
    }

    public void setP(int[] p) {
        this.p = p;
    }

    public int[][] getM() {
        return m;
    }

    public void setM(int[][] m) {
        this.m = m;
    }

    public int[][] getS() {
        return s;
    }

    public void setS(int[][] s) {
        this.s = s;
    }

    public int getR() {
        return r;
    }

    public void setR(int r) {
        this.r = r;
    }

    public int getN() {
        return n;
    }

    public void setN(int n) {
        this.n = n;
    }

    //算法核心
    public void matriChain(){
        //对矩阵进行初始化 将m[][]的对角线全部设置为0
        for (int i=1;i<=n;i++) {
            m[i][i] = 0;
        }
        //对网格图m[][]填写数据
        for (int r = 2;r<=n;r++){
            for (int i=1;i<=n-r+1;i++) {
                int j = i + r - 1;
                m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];
                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;
                    }
                }
            }
        }

    }

    //回溯查找动态规划
   public void traceBack(int i,int j){
        if (i==j)
            System.out.print("A"+i);
        else if (i+1 == j)
            System.out.print(" (A"+i+"*"+" A"+j+") ");
        else {
            System.out.print(" (");
            traceBack(i,s[i][j]);
            traceBack(s[i][j]+1,j);
            System.out.print(") ");
        }
    }
}

其中traceBack方法是用来回溯找到最优解的。

Donate