 |  |
EXAMPLE E5.6-1 : Best way to multiply arrays.
Lets assume that we must calculate the result of:A:=A1*A2*....*An,where Ai is an array whose dimension are d(i-1)Xd(i).We must say that this problem and the way to solve it is obviously similar to the problem of the minimum routes in paragraph P5.7.To make the problem simpler,we say that if the M array is pXq and the N array is qXr in dimensions then the cost calculating the product M*N is a*p*q*r and a is independent from the p,q,r.
The multiplication of the arrays can be done in numerous of ways.If for example n=4 then A=A1 (A2 (A3A4) ) or A=( (A1A2) (A3A4) ) etc.There can be easily made examples,where there are great differences in the calculation cost,for every different way.Therefore the way of calculation with the minimum costs is asked,without having to find the cost for every solution itself.
Let there be:
G(i,j):=A(i),,A(j) , j>=i
What we are interested in is the array G(1,n)=A.Let's call e(G(i,j)) the minimum calculation cost
for the G(i,j) array.If j=i,no calculation is needed,that is e(G(i,j))=0 for i=1,..,n . If j>i we can see
that no matter how we will calculate the G(i,j) array,at the last step the multiplication of 2 other
arrays will be needed.Every one of those arrays,will consist a sub-product,that is:
G(i,j):=G(i,k)G(k+1,j) i<>j
Therefore
e(G(i,j))=min {e(G(i,k)) + e(G(k+1,j)) + a*d(i-1)*d(k)*d(j) } and i<=k<j
We notice that the differences k-i and j-k can not grow bigger then the j-i difference. This means that the formula above can be considered as a retroactive formula,where the calculation of the e(G(i,j) is made by the difference of the pointers order.The initial conditions are:e(G(i,j))=0.That means that we start with the calculation of the minimums e(G(i,i+1)) and go on like this,or in other words calculate the elements of the upper triangular array which contains the e(G(i,j)), j>i in diagonals.This array holds the role of storing,and the (5.6-1) formula obviously rejects many of the choices among all the possible ways to calculate the G(i,j) chooses the minimum one,so that it can be used in the calculation of the e(G(i,j)).In this way we understand that both main characteristics a and b of D.P. are satisfied.Finally it is quite easy to show that our algorithm has a total cost of O(n3),despite the presence of exponential number of possible solutions.
| |
HTML PAGE DIRECTOR :Papaioannou Panagiotis