Question

15.2-1 -- Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is (5, 10, 3, 12, 5, 50, 6).

5. -- Implement Matrix-ChainMultiply(A,s,i,j) using algorithm Matrix-Chain-Order and Matrix-Multiply, where Matrix-Multiply(X,Y, p,q,r) multiplies matrices X and Y, X and Y have pxq and qxr demension, respectively. Given a chain of 6 matrices whose dimensions are given in 15.2-1, and elements are random real numbers from -10 to 10, use Matrix-Chian-ultiply to calculate the product of these matrices.

Answer 1

Solution

First we will assign the values

(5,10,3,12,5,50,6)

Let p0=5

p1=10

p2=3

p3=12

p4=5

p5=50

p6=6

The corresponding matrix as follows

A1=5*10

A2=10*3

A3=3*12

A4=12*5

A5=5*50

A6=50*6

Using the algorithm

for all  m[i,j]=0

m[1,2]=m[1,1]+m[2,2]+p0 x p2 x p2

m[1,2]=0+150

m[1,2]=150

--

m[3,4]=m[3,3]+m[4,4]+p2 x p3 x p4

m[3,4]=0+180

m[3,4]=180

--

m[4,5]=m[4,4]+m[5,5]+p3 x p4 x p5

m[4,5]=0+3000

m[4,5]=3000

---

m[5,6]=m[5,5]+m[6,6]+p4 x p5 x p6

m[5,6]=0+1500

m[5,6]=1500

--

m[1,3]

=

min of

{m[1,1]+m[2,3]+p0 x p1 x p3 =750 }

{m[1,2]+m[3,3]+p0 x p2 x p3 =330 }

=330

--

m[2,4]

=

min of

{m[2,2]+m[3,4]+p1 x p2 x p4 =330 }

{m[2,3]+m[4,4]+p1 x p3 x p4 =960 }

=330

---

m[3,5]

=

min of

{m[3,3]+m[4,5]+p2 x p3 x p5 =4800 }

{m[3,4]+m[5,5]+p2 x p4 x p5 =930 }

=930

--

m[4,6]

=

min of

{m[4,4]+m[5,6]+p3 x p4 x p6 =1860 }

{m[4,5]+m[6,6]+p3 x p5 x p6 =6600 }

=1860

---

m[1,4]

=

min of

{m[1,1]+m[2,4]+p0 x p1 x p4 =580 }

{m[1,2]+m[3,4]+p0 x p2 x p4 =405 }

{m[1,3]+m[4,4]+p0 x p3 x p4 =630 }

=630

--

m[2,5]

=

min of

{m[2,2]+m[3,5]+p1 x p2 x p5 =2430 }

{m[2,3]+m[4,5]+p1 x p3 x p5 =9360 }

{m[2,4]+m[5,5]+p1 x p4 x p5 =2830 }

=2430

---

m[3,6]

=

min of

{m[3,3]+m[4,6]+p2 x p3 x p6 =2076 }

{m[3,4]+m[5,6]+p2 x p4 x p6 =1770 }

{m[3,5]+m[6,6]+p2 x p5 x p6 =1830 }

=1770

---

m[1,5]

=

min of

{m[1,1]+m[2,5]+p0 x p1 x p5 =4930 }

{m[1,2]+m[3,5]+p0 x p2 x p5 =1830 }

{m[1,3]+m[1,4]+p0 x p3 x p5 =6330 }

{m[1,4]+m[1,5]+p0 x p4 x p5 =1655 }

=1655

--

m[1,6]

=

min of

{m[1,1]+m[2,6]+p0 x p1 x p6 =2250 }

{m[1,2]+m[3,6]+p0 x p2 x p6 =2010 }

{m[1,3]+m[4,6]+p0 x p3 x p6 =2550 }

{m[1,4]+m[5,6]+p0 x p4 x p6 =2055 }

{m[1,5]+m[6,6]+p0 x p5 x p6 =3155 }

=2010

--

m[2,6]

=

min of

{m[2,2]+m[3,6]+p1 x p2 x p6 =1950 }

{m[2,3]+m[4,6]+p1 x p3 x p6 =2940 }

{m[2,4]+m[5,6]+p1 x p4 x p6 =2130 }

{m[2,5]+m[6,6]+p1 x p5 x p6 =5430 }

=1950

m-table

M123456 2010 1950 1770 1840 1500 0 1655 2430 930 3000 0 405 330 180 0 330 360 2 150 10

s-table

ا نا كل S 6 5 4 3 1 2 4 2 2 2 2 2 2 2 ما نیا

The min cost is 2010

the optimal paranthesizaiton =

((A1*A2)*(A3*A4)*(A5*A6))

---

ALL THE BEST