放牧代码和思想
专注自然语言处理、机器学习算法

《算法导论》矩阵链乘法Java实现

目录

算法导论.jpg

问题

有A1A2…An共n个矩阵,第i个矩阵的大小为pi-1*pi,计算代价由标量乘法决定,求最小代价及运算顺序。

比如:屏幕快照 2016-02-21 上午12.10.10.png

对应的答案是:

屏幕快照 2016-02-21 上午12.14.33.png 15125次乘法

思路

设m[i,j]表示从i到j的矩阵链的最小计算代价,s[i,j]=k表示在i和j中间的矩阵k后面加一个括号,则m的递推方法是:

 矩阵链.jpg

第一项是前半部分,第二项是后半部分,第三项是前后两部分组合的计算代价。最终m[1,n]就是最小代价。由于是ijk三重遍历,所以复杂度是O(n3)。这只是粗略估计,据《算法导论》介绍,准确的复杂度是屏幕快照 2016-02-21 下午1.10.38.png

在递推的同时,记录最小的k即可。那如何利用s[i,j]来得到最终的的运算顺序呢?递归往下打括号就行了:

矩阵链顺序.jpg

Java实现

import java.util.Scanner;

public class MatrixChainOrder
{
    private static int n;
    private static int[][] m = new int[100][100];
    private static int[][] s = new int[100][100];
    private static int[] p = new int[105];
    private static final int MAX = Integer.MAX_VALUE;

    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        for (int i = 0; i <= n; i++)
        {
            p[i] = scan.nextInt();
            m[i][i] = 0;
        }

        for (int l = 2; l <= n; l++)
        {
            for (int i = 1; i <= n - l + 1; i++)
            {
                int j = i + l - 1;
                m[i][j] = MAX;
                for (int k = i; k <= j - 1; k++)
                {
                    int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                    if (q < m[i][j])
                    {
                        m[i][j] = q;
                        s[i][j] = k;
                    }
                }
            }
        }
        print(1, n);
        System.out.printf(" %d\n", m[1][n]);
    }

    public static void print(int i, int j)
    {
        if (i == j)
            System.out.print("A" + i);
        else
        {
            System.out.print("(");
            print(i, s[i][j]);
            print(s[i][j] + 1, j);
            System.out.print(")");
        }
    }
}

输入

6
30
35
15
5
10
20
25

输出

((A1(A2A3))((A4A5)A6)) 15125

Reference

http://blog.sina.com.cn/s/blog_9075354e0101o4w4.html

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » 《算法导论》矩阵链乘法Java实现

分享到:更多 ()

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    膜拜一下

    李阳博客1年前 (2016-07-08)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机