Ruby实现的矩阵连乘算法_Ruby

Ruby实现的矩阵连乘算法

2020-04-30 11:16脚本之家 Ruby

这篇文章主要介绍了Ruby实现的矩阵连乘算法,本文直接给出实现代码,需要的朋友可以参考下

动态规划解决矩阵连乘问题，随机产生矩阵序列，输出形如((A1(A2A3))(A4A5))的结果。

代码：

				?

									#encoding: utf-8

									=begin

									author: xu jin, 4100213

									date: Oct 28, 2012

									MatrixChain

									to find an optimum order by using MatrixChain algorithm

									example output:

									The given array is:[30, 35, 15, 5, 10, 20, 25]

									The optimum order is:((A1(A2A3))((A4A5)A6))

									The total number of multiplications is: 15125

									The random array is：[5, 8, 8, 2, 5, 9]

									The optimum order is:((A1(A2A3))(A4A5))

									The total number of multiplications is: 388

									=end

									INFINTIY = 1 / 0.0

									p = [30, 35, 15, 5, 10, 20, 25]

									m, s = Array.new(p.size){Array.new(p.size)}, Array.new(p.size){Array.new(p.size)}

									def matrix_chain_order(p, m, s)

									   n = p.size - 1

									   (1..n).each{|i| m[i][i] = 0} 

									   for r in (2..n) do

									     for i in (1..n - r + 1) do

									       j = r + i - 1

									       m[i][j] = INFINTIY

									       for k in (i...j) do

									         q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]                  

									         m[i][j], s[i][j] = q, k if(q < m[i][j]) 

									       end

									     end

									   end

									end

									def print_optimal_parens(s, i, j)

									   if(i == j) then

									    print "A" + i.to_s

									   else

									    print "("

									    print_optimal_parens(s, i, s[i][j])

									    print_optimal_parens(s, s[i][j] + 1, j)

									    print ")"

									   end

									end

									def process(p, m, s)

									   matrix_chain_order(p, m, s)

									   print "The optimum order is:"

									   print_optimal_parens(s, 1, p.size - 1)

									   printf("\nThe total number of multiplications is: %d\n\n", m[1][p.size - 1])

									end

									puts "The given array is:" + p.to_s

									process(p, m, s)

									#produce a random array

									p = Array.new

									x = rand(10)

									(0..x).each{|index| p[index] = rand(10) + 1}

									puts "The random array is：" + p.to_s

									m, s = Array.new(p.size){Array.new(p.size)}, Array.new(p.size){Array.new(p.size)}

									process(p, m, s)