1、The Matrix Multiplication Order Problem（矩阵相乘的序问题）例Multiply arrays with the size shown:A1 A2 A3 A4 301 140 4010 10 25Matrix multiplication is associative满足结合律A(BC)=(AB)C How many multiplications are done?(A1 A2)A3)A4 301 40+3040 10+3010 25=20,700A1(A2(A3A4)4010 25+140 25+3040 25=11,750(A1 A2)(A3A4)30
2、1 40+4010 25+3040 25=41,200A1(A2 A3)A4)140 10+110 25+301 25=1,400 For the general problem,suppose the dimensions of Ai are di-1 di for 1inA1 A2 An d0 d1 d1 d2 dn-1 dn There are(n-1)!kinds of association How should we compute and what is the minimum cost of doing so?The cost is the number of element-
3、wise multiplication.)2(2/n)2(2/nA Greedy AttemptFirst,choose the multiplication with minimum cost.Determine the dimensions of the matrices in the modified matrix chainChoose the multiplication with minimum cost.And so on.This strategy may fails to be optimal for some sequences of three matrices?Exam
4、ple:A1 A2 A3 5 4 4 5 5 6Typically,dynamic programming algorithms are more expensive than greedy algorithm,so they are used when no greedy strategy can be found that delivers the optimal solution.A Recursive AlgorithmSoppose,after choosing a first multiplication,say at position i in the sequence,we r
5、ecursively solve the remaining problem optimally.We do this for each i that represents a valid choice,and finally select the i that gives the lowest combined cost.Backtracking After trying one complete choice sequence,the algorithm backtracks to the point before the most recent choice and tries an a
6、lternative;when alternatives are exhausted at this point,it backtracks to an earlier point and tries alternatives there,and continues until all alternative are exhausted.d0,d1,d2 ,dn are in an array dim.The initial index sequence is 0,nAll indexes of the sequence,except the first and the last,specif
7、y multiplication operators,as well.After making a first choice of multiplication i,the index sequence for the remaining problem is 0,i-1,i+1,nAll indexes of the sequence,except the first and the last,specify multiplication operators,as well.B=Ai Ai+1 A1 Ai-1 B Ai+2 An d0 d1 di-2 di-1 di-1 di+1 di+1
8、di+2 Assume the index sequence itself is stored in a zero-based array seq,and len is the length of seq.mmTry1(dim,len,seq)if(len 3)bestCost=0;else bestCost=;for(i=1;i len 1;i+)c=cost of multiplication at position seqi.newSeq=seq with i-th element deleted.b=mmTry1(dim,len-1,newSeq);bestCost=min(bestC
9、ost,b+c)return bestCost;The complexity of mmTry()T(n)=(n-1)T(n-1)+n(n-1)!)How many subproblems are reachable from the initial problem,which is described by the index sequence 0,n?Although subsequences start out as a few continuous subranges,they get more and more fragmented as the subproblem depth i
10、ncreases.For example,with n=10,after choosing multiplication operators 1,4,6,9,the subsequence of remaining indexes becomes 0,2,3,5,7,8,10.There is no concise way to specify these subsequence.Every subsequence(with at least three elements)is a reachable subproblem.There are about 2n such subsequence
11、s(Without considering associative order).This graph is simply too large to be searched efficiently.The subproblem should have a concise identifier to limit the maximum size of the subproblem graph(in terms of vertices there may be more edges)If we focus on making the maximum dictionary size a polyno
12、mial function of the input size,and as small as possible,we will ensure that the depth-first search of the subproblem graph can be carried out in polynomial time.(i,j)represents sequence(i,i+1,j-1,j)and set it a vertex of subproblem graph.A1 A2 Ai =B1 d0 d1 d1 d2 di-1 di d0 diAi+1 Ai+2 An =B2 di di+
13、1 di+1 di+2 dn-1 dn di dnThe last step is to multiply B1B2eand the cost for that is any based on(d0,di,dn)mmTry2(dim,low,high)if(high low=1)bestCost=0;else bestCost=;for(k=low+1;k high-1;k+)a=mmTry2(dim,low,k);b=mmTry2(dim,k,high);c=cost of multiplication at position k,with dimensions dim low,dimk,d
14、imhigh.bestCost=min(bestCost,a+b+c);return bestCost;(2n)Consider the subproblem graph,where the initial problem is described by the pair(0,n),the vertices(subproblems)are identified by a pair of integers,say(i,j),in the range 0,n with ij,so there are about n2/2 of them.For the subproblem identified
15、by the pair(i,j)there are two subproblems to be solved by recursive calls for each k between i+1 and j-1,so this is less than 2n edges leaving the vertex(i,j)The whole subproblem graph has fewer than n3 edges,so DFS can traverse it in time O(n3)The dictionary is named cost,the identifier for an elem
16、ent is a pair of integers.Operations include create,member,retrieve and store.mmTry2DP(dim,low,high,cost)if(high low=1)bestCost=0;else bestCost=;for(k=low+1;k high-1;k+)if(member(low,k)=false)a=mmTry2(dim,low,k,cost);else a=retrieve(cost,low,k)mmTry2(dim,low,k);if(member(k,high)=false)b=mmTry2DP(dim
17、,k,high,cost);else b=retrieve(cost,k,high);c=cost of multiplication at position k,with dimensions dim low,dimk,dimhigh.bestCost=min(bestCost,a+b+c);store(cost,low,high,bestCost);return bestCost;The dictionary is named cost,the identifier for an element is a pair of integers.Operations include create,member,retrieve and store.
