1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Sindrei [870]
3 years ago
14

You are given 4 matrices M1, M2, M3, M4 and you are asked to determine the optimal schedule for the product M1 ×M2 × M3 ×M4 that

minimizes the number of operations (addition/multiplication) involved. The dimensions of the four matrices are respectively 100 × 50, 50 × 200, 200 × 50, and 50 × 10. What is the best (cheapest) schedule to multiply all the matrices together and compute M1 × M2 × M3 × M4? What is the total cost for this schedule?

Mathematics
1 answer:
alexandr1967 [171]3 years ago
7 0

Answer:

Step-by-step explanation:

first method is to try out all possible combinations and pick out the best one which has the minimum operations but that would be infeasible method if the no of matrices increases  

so the best method would be using the dynamic programming approach.

A1 = 100 x 50

A2 = 50 x 200

A3 = 200 x 50

A4 = 50 x 10

Table M can be filled using the following formula

Ai(m,n)

Aj(n,k)

M[i,j]=m*n*k

The matrix should be filled diagonally i.e., filled in this order

(1,1),(2,2)(3,3)(4,4)

(2,1)(3,2)(4,3)

(3,1)(4,2)

(4,1)

<u>                  Table M[i, j]                                             </u>

             1                      2                  3                    4

4    250000          200000        100000                0  

3      

750000        500000            0

2      1000000             0

1            

0

Table S can filled this way

Min(m[(Ai*Aj),(Ak)],m[(Ai)(Aj*Ak)])

The matrix which is divided to get the minimum calculation is selected.

Table S[i, j]

           1          2         3        

4

4          1           2         3

3          

1          2

2            1

1

After getting the S table the element which is present in (4,1) is key for dividing.

So the matrix multiplication chain will be (A1 (A2 * A3 * A4))

Now the element in (4,2) is 2 so it is the key for dividing the chain

So the matrix multiplication chain will be (A1 (A2 ( A3 * A4 )))

Min number of multiplications: 250000

Optimal multiplication order: (A1 (A2 ( A3 * A4 )))

to get these calculations perform automatically we can use java

code:

public class MatrixMult

{

public static int[][] m;

public static int[][] s;

public static void main(String[] args)

{

int[] p = getMatrixSizes(args);

int n = p.length-1;

if (n < 2 || n > 15)

{

System.out.println("Wrong input");

System.exit(0);

}

System.out.println("######Using a recursive non Dyn. Prog. method:");

int mm = RMC(p, 1, n);

System.out.println("Min number of multiplications: " + mm + "\n");

System.out.println("######Using bottom-top Dyn. Prog. method:");

MCO(p);

System.out.println("Table of m[i][j]:");

System.out.print("j\\i|");

for (int i=1; i<=n; i++)

System.out.printf("%5d ", i);

System.out.print("\n---+");

for (int i=1; i<=6*n-1; i++)

System.out.print("-");

System.out.println();

for (int j=n; j>=1; j--)

{

System.out.print(" " + j + " |");

for (int i=1; i<=j; i++)

System.out.printf("%5d ", m[i][j]);

System.out.println();

}

System.out.println("Min number of multiplications: " + m[1][n] + "\n");

System.out.println("Table of s[i][j]:");

System.out.print("j\\i|");

for (int i=1; i<=n; i++)

System.out.printf("%2d ", i);

System.out.print("\n---+");

for (int i=1; i<=3*n-1; i++)

System.out.print("-");

System.out.println();

for (int j=n; j>=2; j--)

{

System.out.print(" " + j + " |");

for (int i=1; i<=j-1; i++)

System.out.printf("%2d ", s[i][j]);

System.out.println();

}

System.out.print("Optimal multiplication order: ");

MCM(s, 1, n);

System.out.println("\n");

System.out.println("######Using top-bottom Dyn. Prog. method:");

mm = MMC(p);

System.out.println("Min number of multiplications: " + mm);

}

public static int RMC(int[] p, int i, int j)

{

if (i == j) return(0);

int m_ij = Integer.MAX_VALUE;

for (int k=i; k<j; k++)

{

int q = RMC(p, i, k) + RMC(p, k+1, j) + p[i-1]*p[k]*p[j];

if (q < m_ij)

m_ij = q;

}

return(m_ij);

}

public static void MCO(int[] p)

{

int n = p.length-1;     // # of matrices in the product

m    =    new    int[n+1][n+1];        //    create    and    automatically initialize array m

s = new int[n+1][n+1];

for (int l=2; l<=n; l++)

{

for (int i=1; i<=n-l+1; i++)

{

int j=i+l-1;

m[i][j] = Integer.MAX_VALUE;

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;

}

}

}

}

}

public static void MCM(int[][] s, int i, int j)

{

if (i == j) System.out.print("A_" + i);

else

{

System.out.print("(");

MCM(s, i, s[i][j]);

MCM(s, s[i][j]+1, j);

System.out.print(")");

}

}

public static int MMC(int[] p)

{

int n = p.length-1;

m = new int[n+1][n+1];

for (int i=0; i<=n; i++)

for (int j=i; j<=n; j++)

m[i][j] = Integer.MAX_VALUE;

return(LC(p, 1, n));

}

public static int LC(int[] p, int i, int j)

{

if (m[i][j] < Integer.MAX_VALUE) return(m[i][j]);

if (i == j) m[i][j] = 0;

else

{

for (int k=i; k<j; k++)

{

int   q   =   LC(p,   i,   k)   +   LC(p,   k+1,   j)   +   p[i-1]*p[k]*p[j];

if (q < m[i][j])

m[i][j] = q;

}

}

return(m[i][j]);

}

public static int[] getMatrixSizes(String[] ss)

{

int k = ss.length;

if (k == 0)

{

System.out.println("No        matrix        dimensions        entered");

System.exit(0);

}

int[] p = new int[k];

for (int i=0; i<k; i++)

{

try

{

p[i] = Integer.parseInt(ss[i]);

if (p[i] <= 0)

{

System.out.println("Illegal input number " + k);

System.exit(0);

}

}

catch(NumberFormatException e)

{

System.out.println("Illegal input token " + ss[i]);

System.exit(0);

}

}

return(p);

}

}

output:

You might be interested in
Gia opened two savings accounts at two diffrent banks. One account earns an annual 3.4% simple interest, and the other earns hal
dsp73

Interest from first account is :

I_1 = \dfrac{p\times r \times t}{100}\\\\I_1 = \dfrac{509\times 3.4\times 3}{100}\\\\I_1 =\$ 51.918

Interest form second account is :

I_2 = \dfrac{p\times r\times t}{100}\\\\I_2 = \dfrac{509\times 1.7\times 3}{100}\\\\I_2 =  \$25.959

So, total interest is :

I = I_1 + I_2 \\\\I = 51.918 + 25.959\\\\I = \$77.877

Therefore, total interest is $77.877 .

5 0
3 years ago
HURRY. Write a ratio for the following word phrase. Write the fraction in lowest terms.
mestny [16]

Answer:

84:2 42/1

Step-by-step explanation:

i think

hope ths helps

8 0
3 years ago
Marie plants flowers in a planter that is 1 1/2 feet long and 1 2/3 feet wide. She plans to cover the entire area with fertilize
Arisa [49]

Answer:

2 3/6

Step-by-step explanation:

You must turn 1 2/3 and 1 1/2 into improper fractions. You then multiply them and get an answer of 15/6, but since 6 can go into 15 twice (6x2=12+3=15), you get a whole of 2 and 3/6.


5 0
2 years ago
In isosceles triangle ABC, BC is the shortest side. If the degree measure of A is a multiple of 10, what is the smallest degree
Andrei [34K]

Answer:

n b knhkn hbk n

Step-by-step explanation:

jhuguoljhjjl;

8 0
3 years ago
Read 2 more answers
Pls solve...I will mark as BRAINLIST........​
lesantik [10]

Answer:

Step-by-step explanation:

3 0
1 year ago
Other questions:
  • What is RT, OB, and US equal PLEASE HELP !!!
    14·1 answer
  • Which of the following are accepted without proof on a logical system?
    10·1 answer
  • Six times a number is ten plus four times a number
    10·1 answer
  • Write an expression, using an exponent, that is equivalent to 9\times 9\times 9\times 9\times 9\times 9\times 99×9×9×9×9×9×9
    6·2 answers
  • It takes one student 8 hours to wash all of the cars at a school car wash. If 6
    5·1 answer
  • What’s the answer to <br><br> 250 = 4(1 - 7x)
    11·1 answer
  • Shelly pays $22.75 for 3.5 yards of fabric. What is the price per yard of fabric?
    15·2 answers
  • 1<br> How can +<br> 5<br> be modeled on a<br> 5<br> number line? Complete the sentence.
    14·1 answer
  • Help due in 30 min!!!!!!!!!!!!!!!
    13·1 answer
  • The product of 11/13 and 4 is:
    13·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!