Page 1 of 1

help needed: matrix chain multiplication (reversed!)

Posted: Tue Oct 22, 2002 4:31 pm
by imranul
To calculate an optimal solution for matrix chain multiplication we have to make two tables : one for the cost ('m' table) and other one to take the point where to break ('s' table).

Now given a sequence of matrix we can easily calculate an optimal solution.

Now the question is that:

If we are given an optimal solution can we calculate the 's' table fully?
What i mean is that if I have an optimal solution :
((A1A2)((A3A4)(A5A6)))
will i be able to fill up all the entries of the 's' table?

I can construct some parts of the table e.g.:
- | 1 | 2 | 3 | 4 | 5 | 6
-----------------------------------------------------
1 | - | 1 |? | ? |? | 2
2 | - | - |2 | ? |? | ?
3 | - | - | - | 3 | ? | 4
4 | - | - | - | - | 4 | ?
5 | - | - | - | - | - | 5


Now will i be able to find out the '?' marked entries in the following manner:

If i disregard A6 then the soluton becomes:

((A1A2)((A3A4)(A5)))

then we can say that in [1][5] there will be : 2

can we do it in this way? why ??


Imran