主题：[讨论]设计一个分治法算法
makexue
[专家分：0] 发布于 2008-05-25 10:03:00
向各位高手求助：
假设有n多个多米诺骨牌（上下各有一个数字的）A1,A2,……,An，
多米诺骨牌的顺序已经确定，假设就是A1,A2,……,An，每各骨牌只允许上下翻转自己。
找到一个摆法，使得相邻两个数字的乘积之和最大（小）
设计一个分治法的算法。
一个简单的示例：
假设有3张骨牌（A1（1，2）、A2（6，5）、A3（9，7）），顺序为A1、A2、A3，可以肯定的是A1、A3的摆放顺序已经确定，就是A1（1，2），A3（9，7），那么A2的摆放是A2（5，6），使得A1与A2相邻的数字2*5=10，加上A2与A3相邻的数字6*9=54，之和=64为最大。
如果是n个，那么中间的那n-2张牌应该如何摆放，才能得到最大或者最小。
回复列表 （共3个回复）
沙发
27046662 [专家分：210] 发布于 2008-05-31 10:33:00
有点象矩阵连成的dp算法
板凳
hourui2008 [专家分：0] 发布于 2008-06-09 09:42:00
确实有点像矩阵连成的算法，这个算法我要仔细研究一下
3 楼
lnt_program [专家分：180] 发布于 2008-06-12 10:30:00
我想到的分治方法：
假设我们将两段骨牌A[i,j]与A[j+1,k]合并，A[i,j]有4个参数l[0][0],l[0][1],l[1][0],l[1][1]，A[j+1,k]有4个参数r[0][0],r[0][1],r[1][0],r[1][1]，合并后的骨牌段A[i,k]有4个参数c[0][0],c[0][1],c[1][0],c[1][1]。这4个参数分别表示骨牌段首尾2个骨牌在正反两种状态下的骨牌段的最大乘积和。那么，我们可以如下计算A[i,k]的4个参数：
c[0][0]=max((l[0][0]+r[0][0]+A[j][0]*A[j+1][0]),(l[0][0]+r[1][0]+A[j][0]*A[j+1][1]),(l[0][1]+r[0][0]+A[j][1]*A[j+1][0]),(l[0][1]+r[1][0]+A[j][1]*A[j+1][1]))
c[0][1]=max((l[0][0]+r[0][1]+A[j][0]*A[j+1][0]),(l[0][0]+r[1][1]+A[j][0]*A[j+1][1]),(l[0][1]+r[0][1]+A[j][1]*A[j+1][0]),(l[0][1]+r[1][1]+A[j][1]*A[j+1][1]))
c[1][0]=max((l[1][0]+r[0][0]+A[j][0]*A[j+1][0]),(l[1][0]+r[1][0]+A[j][0]*A[j+1][1]),(l[1][1]+r[0][0]+A[j][1]*A[j+1][0]),(l[1][1]+r[1][0]+A[j][1]*A[j+1][1]))
c[1][1]=max((l[1][0]+r[0][1]+A[j][0]*A[j+1][0]),(l[1][0]+r[1][1]+A[j][0]*A[j+1][1]),(l[1][1]+r[0][1]+A[j][1]*A[j+1][0]),(l[1][1]+r[1][1]+A[j][1]*A[j+1][1]))
骨牌段逐级合并到整个A(1,n)，取其4个参数中的最大就是其最大乘积和。
我来回复
您所在位置：