资源描述：
《TheMatrixMultiplicationOrderProblem矩阵相乘的序问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、TheMatrixMultiplicationOrderProblem （矩阵相乘的序问题）例Multiplyarrayswiththesizeshown:A1×A2×A3×A430×11×4040×1010×25Matrixmultiplicationisassociative满足结合律A(BC)=(AB)CHowmanymultiplicationsaredone?((A1A2)A3)A430·1·40+30·40·10+30·10·25=20,700A1(A2(A3A4))40·10·25+1·40·25+30·40·25=1
2、1,750(A1A2)(A3A4)30·1·40+40·10·25+30·40·25=41,200A1((A2A3)A4)1·40·10+1·10·25+30·1·25=1,400Forthegeneralproblem,supposethedimensionsofAiaredi-1×difor1≤i≤nA1×A2×…×And0×d1d1×d2dn-1×dnThereare(n-1)!kindsofassociationHowshouldwecomputeandwhatistheminimumcostofdoingso?Thecos
3、tisthenumberofelement-wisemultiplication.AGreedyAttemptFirst,choosethemultiplicationwithminimumcost.DeterminethedimensionsofthematricesinthemodifiedmatrixchainChoosethemultiplicationwithminimumcost.Andsoon.Thisstrategymayfailstobeoptimalforsomesequencesofthreematrices?
4、Example:A1×A2×A35×44×55×6Typically,dynamicprogrammingalgorithmsaremoreexpensivethangreedyalgorithm,sotheyareusedwhennogreedystrategycanbefoundthatdeliverstheoptimalsolution.ARecursiveAlgorithmSoppose,afterchoosingafirstmultiplication,sayatpositioniinthesequence,werecur
5、sivelysolvetheremainingproblemoptimally.Wedothisforeachithatrepresentsavalidchoice,andfinallyselecttheithatgivesthelowestcombinedcost.BacktrackingAftertryingonecompletechoicesequence,thealgorithmbacktrackstothepointbeforethemostrecentchoiceandtriesanalternative;whenalt
6、ernativesareexhaustedatthispoint,itbacktrackstoanearlierpointandtriesalternativesthere,andcontinuesuntilallalternativeareexhausted.d0,d1,d2…,dnareinanarraydim.Theinitialindexsequenceis0,…,nAllindexesofthesequence,exceptthefirstandthelast,specifymultiplicationoperators,
7、aswell.Aftermakingafirstchoiceofmultiplicationi,theindexsequencefortheremainingproblemis0,…,i-1,i+1,…,nAllindexesofthesequence,exceptthefirstandthelast,specifymultiplicationoperators,aswell.B=Ai×Ai+1A1×…×Ai-1×B×Ai+2×…×And0×d1di-2×di-1di-1×di+1di+1×di+2Assumetheindexseq
8、uenceitselfisstoredinazero-basedarrayseq,andlenisthelengthofseq.mmTry1(dim,len,seq)if(len<3)bestCost=0;elsebestCost=∞
