Use the dynamic programming technique to find an optimal parenthesization of a m
ID: 3697911 • Letter: U
Question
Use the dynamic programming technique to find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is <5, 8, 4, 10, 7, 50, 6>.
Matrix Dimension
A1 5*8
A2 8*4
A3 4*10
A4 10*7
A5 7*50
A6 50*6
You may do this either by implementing the MATRIX-CHAIN-ORDER algorithm in the text or by simulating the algorithm by hand. In either case, show the dynamic programming tables at the end of the computation.
Using Floyd’s algorithm (See Dynamic Programming slide 54), calculate the length of the shortest path between each pair of nodes in the graph by constructing a matrix. Give the each step of the adjacency matrix.
ASAP
Explanation / Answer
Use the dynamic programming technique to find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is <5, 8, 4, 10, 7, 50, 6>.
Dynamic programming is typically applied to optimization problems. In such problems there can be many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value. We call such a solution an optimal solution to the problem, as opposed to the optimal solution, since there may be several solutions that achieve the optimal value.
The development of a dynamic-programming algorithm can be broken into a sequence of four steps.
1. Characterize the structure of an optimal solution.
2. Recursively defines the value of an optimal solution.
3. Compute the value of an optimal solution in a bottom-up fashion.
4. Construct an optimal solution from computed information.
We have many options to multiply a chain of matrices because matrix multiplication is associative. In other words, no matter how we parenthesize the product, the result will be the same. For example, if we had four matrices A, B, C, and D, we would have:
(ABC)D = (AB)(CD) = A(BCD) = ....
Input p[] ={ 5, 8, 4, 10, 7, 50, 6}
There are 6 matrices of dimensions 5*8, 8*4, 4*10, 10*7, 7*50, 50*6.
Let the input 6 matrices be A, B, C, D, E and F. the minimum number of multiplications are obtained by putting parenthesis.
Output: 3960
Using Floyd’s algorithm (See Dynamic Programming slide 54), calculate the length of the shortest path between each pair of nodes in the graph by constructing a matrix.
The starting matrix D0 as follows:
Do= 1 2 3 4 5 6 7
1 0 15 50 30 10
2 0 10 5
3 10 0
4 10 0
5 0 5
6 10 0 15
7 30 50 40 0
All elements along the main diagonal of matrix Do equal zero since by definition dij=0 for i=j.
We note d1,2 element of matrix Do. This element equals 15 since the length of the branch connecting nodes 1 and 2 is 15.
Element d3,4 equals infinity since the network has no branch which is oriented from node 3 to node 4.
Q0= 1 2 3 4 5 6 7
1 - 1 1 1 1 1 1
2 2 - 2 2 2 2 2
3 3 3 - 3 3 3 3
4 4 4 4 - 4 4 4
5 5 5 5 5 - 5 5
6 6 6 6 6 6 - 6
7 7 7 7 7 7 7 -
We now go to the first algorithmic step. Let k = 1. As an illustration of Step 2 we calculate the elements of the first three rows of matrix D1. Calculations for other rows are left as an exercise.
D1= 1 2 3 4 5 6 7
1 0 15 50 30
2 -
3 10 60 - 10 20
4 60 -
5 - 5
6 10 25 60 40 12 - 12
7 30 50 40 -
Matrix elements which changed values compared to the values they had in matrix DO are circled.
So, for example, the shortest distance between nodes 3 and 4 is 10 after the first algorithic step. In starting matrix DO this distance was . Since
Then node 1 is the new immediate predecessor of node 4 on the shortest path from node 4 to node 3. After passing through the algorithm the first time, Q1 looks like this:
Q1= 1 2 3 4 5 6 7
1 - 1 1 1 1 1 1
2 2 - 2 2 2 2 2
3 3 1 - 1 3 1 3
4 4 4 1 - 4 4 4
5 5 5 5 5 - 5 5
6 6 1 1 1 1 - 1
7 7 7 7 7 7 7 -
After the second, third, fourth and fifth passages, sixth and seventh passages through the algorithm, matrices D2, Q2, D3, Q3, D4, Q4, D5, Q5 D6, Q6,and D7, Q7.
By seventh passage we will get the shortest path between the nodes.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.