help needed: matrix chain multiplication (reversed!)

Post here if you don't find any other place for your post. But please, stay on-topic: algorithms, programming or something related to this web site and its services.

Moderator: Board moderators

Post Reply
imranul
New poster
Posts: 12
Joined: Fri Jul 19, 2002 6:28 pm
Location: Bangladesh

help needed: matrix chain multiplication (reversed!)

Post 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
Life is like a box of Chocolates,
you never know what you're going to get...

Post Reply

Return to “Other words”