多米诺 分治法

计算机算法设计与分析分治法求解多米诺骨牌题目：现有n块“多米诺骨牌”S1，S2，……，Sn水平放成一排，每块骨牌Si包含左右两个部分，每个部分赋予一个非负整数值，如下图所示为包含6块骨牌的序列。骨牌可做180度旋转，使得原来在左边的值变到右边，而原来在右边的值移到左边，假设不论si如何旋转，L[i]总是存储si左边的值，R[i]总是存储右边的值，W[i]用于存储si的状态：当L[i]=R[i]时记为0，否则记为1，试采用分治法设计算法求∑𝑅[𝑖]𝐿[𝑖+1]𝑛−1𝑖=1最大值，以及当取得最大之时每个骨牌的状态。解：输入为n个多米诺骨牌S1，S2，……，Sn，可将输入在中间那块骨牌的中间，即骨牌S1+n2的中间处拆分，这样原问题就被拆分为两个子问题，但是可以发现，新的子问题与原问题结构不完全一样。为解决这一问题，可对原始的输入作如下处理：在原始输入序列左右两端各加半块骨牌，记为S0和Sn+1，对应于此处拆分L、R则为R[0]和L[n+1]，并且令R[0]和L[n+1]里面的值为0。如下图所示：则原规模为n的问题求MAX（∑𝑅[𝑖]𝐿[𝑖+1]𝑛−1𝑖=1）变为规模为规模为n+2的问题求∑𝑅[𝑖]𝐿[𝑖+1]𝑛𝑖=0，结构有所变化，但实际上由于左右两边加的半块骨牌中的元素值为0，对原问题结果并不会产生影响。这时在按原来的拆分方法进行拆分，就可将问题拆为两个规模为原问题一半的子问题。具体算法如下：(其中数组W用于存放所求和最大时各个骨牌的状态，first和last分别为第一块和最后一块骨牌的序号)AlgorithmMax_of_Domino(L,R,first,last,W)1.iflast-first=0thenreturn;//骨牌数不能少于两个2.R[first-1]=0,L[last+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=1thenMax=R[first]*L[last];2.elsemid=(first+last)/2;//这里用表示上取整3.ifL[mid]R[mid]//LR,这时W[mid]状态为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(L[mid],R[mid]);//再交换被拆分的骨牌的左右半块，使W[mid]状态为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.ifMax1Max012.Max=Max1,W[mid]=1;13.elseMax=Max0,W[mid]=0;14.else//L=R,W[mid]=015.MaxL0=Simplify_Max_of_Domino(L,R,first,mid);16.MaxR0=Simplify_Max_of_Domino(L,R,mid,last);17.Max0=MaxL0+MaxR0;18.Swap(L[mid],R[mid]);//再交换被拆分的骨牌的左右半块，使W[mid]状态为019.MaxL1=Simplify_Max_of_Domino(L,R,first,mid);20.MaxR1=Simplify_Max_of_Domino(L,R,mid,last);21.Max1=MaxL1+MaxR1;22.ifMax1Max023.Max=Max1,W[mid]=1;24.ElseMax=Max0,W[mid]=0;25.end26.end27.returnMax;现在分析时间复杂度：算法中较多的操作是乘法操作，可将乘法操作视为关键操作，除法也看作是乘法。用T(n)表示原问题的时间复杂度，H(n)为加入两个半块，即R[0]和L[n+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)