《多米诺-分治法》由会员分享，可在线阅读，更多相关《多米诺-分治法（4页珍藏版）》请在金锄头文库上搜索。
1、计算机算法设计与分析分治法求解多米诺骨牌 题目：现有n块“多米诺骨牌”S1，S2，Sn水平放成一排，每块骨牌Si包含左右两个部分，每个部分赋予一个非负整数值，如下图所示为包含6块骨牌的序列。骨牌可做180度旋转，使得原来在左边的值变到右边，而原来在右边的值移到左边，假设不论si如何旋转，Li总是存储si左边的值，Ri总是存储右边的值，Wi用于存储si的状态：当Li=Ri时记为0，否则记为1，试采用分治法设计算法求i=1n-1RiLi+1最大值，以及当取得最大之时每个骨牌的状态。解：输入为n个多米诺骨牌S1，S2，Sn ，可将输入在中间那块骨牌的中间，即骨牌S1+n2的中间处拆分，这样原问题就被
2、拆分为两个子问题，但是可以发现，新的子问题与原问题结构不完全一样。为解决这一问题，可对原始的输入作如下处理：此处拆分在原始输入序列左右两端各加半块骨牌，记为S0 和Sn+1 ，对应于L、R则为R0和Ln+1，并且令R0和Ln+1里面的值为0。如下图所示：则原规模为n的问题求MAX（i=1n-1RiLi+1）变为规模为规模为n+2的问题求i=0nRiLi+1，结构有所变化，但实际上由于左右两边加的半块骨牌中的元素值为0，对原问题结果并不会产生影响。这时在按原来的拆分方法进行拆分，就可将问题拆为两个规模为原问题一半的子问题。具体算法如下：(其中数组W用于存放所求和最大时各个骨牌的状态，first和
3、last分别为第一块和最后一块骨牌的序号)AlgorithmMax_of_Domino(L,R,first,last,W)1. if last-first=0 thenreturn;/骨牌数不能少于两个2. Rfirst-1=0,Llast+1=0;3. Max=Simplify_Max_of_Domino(L,R,first-1,last+1);4. returnMax;AlgorithmSimplify_Max_of_Domino(L,R,first,last)1. iflast-first=1 thenMax=Rfirst*Llast;2. elsemid=;/这里用表示上取整3. if
4、LmidRmid/LR,这时Wmid状态为14. MaxL1=Simplify_Max_of_Domino(L,R,first,mid);5. MaxR1=Simplify_Max_of_Domino(L,R,mid,last);6. Max1=MaxL1+MaxR1;7. Swap(Lmid,Rmid);/再交换被拆分的骨牌的左右半块，使Wmid状态为08. MaxL0=Simplify_Max_of_Domino(L,R,first,mid);9. MaxR0=Simplify_Max_of_Domino(L,R,mid,last);10. Max0=MaxL0+MaxR0;11. ifM
5、ax1Max012. Max=Max1,Wmid=1;13. else Max=Max0,Wmid=0;14. else/LMax023. Max=Max1,Wmid=1;24. ElseMax=Max0,Wmid=0;25. end26. end27. returnMax;现在分析时间复杂度：算法中较多的操作是乘法操作，可将乘法操作视为关键操作，除法也看作是乘法。用T(n)表示原问题的时间复杂度，H(n)为加入两个半块，即R0和Ln+1后的问题的时间复杂度，则有：T(n)=H(n+2);n=2由算法可知：H(n)=2(H(n/2)+H(n/2)+1=4H(n/2)+1;根据主定理：b=4, c=2; E=logcb=2; f(n)=1;.H(n)O(n2); T(n)=H(n+2)O(n2); 原问题以乘法为关键操作的时间复杂度为：A(n) O(n2)
