⎨⎧0c[i−1,j−1]+1max(c[i,j−1],c[i−1,j])if i=0 or j=0if i,j>0 and xi=yjif i,j>0 and xi=yj第3步:采用自底向上的方法计算最优解的值
考虑每个长度下的X和每个长度下的Y对应的c[i][j]
- 如果X或Y当前长为0,则对应的LCS都是0
- X最长为1
- Y最长为1:LCS(1,1)的长度取决于LCS(0,1),LCS(1,0),LCS(0,0),而这三个都在之前得到
- Y最长为2:LCS(1,2)的长度取决于LCS(0,2),LCS(1,1),LCS(0,1),而LCS(1,1)在之前已经得到
- 以此类推,直到Y最长为n
- X最长为2
- Y最长为1:LCS(2,1)的长度取决于LCS(1,1),LCS(2,0),LCS(1,0),而LCS(1,1)在之前已经得到
- Y最长为2:LCS(2,2)的长度取决于LCS(1,2),LCS(2,1),LCS(1,1),而LCS(2,1)在之前已经得到
- 以此类推,直到Y最长为n
- 以此类推,直到X最长为m
第4步:利用结果构造得到最优解的过程
由定理可知,只有同时改变X和Y,即当xm=yn时,才会在LCS中加入元素xm,其他情况下都是单独改变X或单独改变Y去寻找xm=yn的情况,所以一个二维数组记录每次情况
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| def optimal(road, X, len_X, len_Y): if len_X == 0 or len_Y == 0: return '' if road[len_X][len_Y] == 'bingo': return optimal(road, X, len_X - 1, len_Y - 1) + X[len_X] elif road[len_X][len_Y] == 'left': return optimal(road, X, len_X, len_Y - 1) elif road[len_X][len_Y] == 'up': return optimal(road, X, len_X - 1, len_Y)
def LCS(X, Y): X = '$' + X Y = '$' + Y len_X = len(X) len_Y = len(Y) common = [[0 for _ in range(len_Y)] for _ in range(len_X)] road = [['' for _ in range(len_Y)] for _ in range(len_X)] for i in range(1, len_X): for j in range(1, len_Y): if X[i] == Y[j]: common[i][j] = common[i - 1][j - 1] + 1 road[i][j] = 'bingo' else: X_left = common[i][j - 1] Y_up = common[i - 1][j] if X_left > Y_up: common[i][j] = X_left road[i][j] = 'left' else: common[i][j] = Y_up road[i][j] = 'up' res = optimal(road, X, len_X - 1, len_Y - 1) return common, res
|
5. 最优二叉搜索树
问题介绍
问题描述:给定n个关键字<k1,k2,k3,…,kn>,其中还存在n+1个伪关键字<d0,d1,d2,…,dn>,满足dn>kn,ki<di<ki+1,关键字没找到就会找到伪关键字,每个关键字有一个访问概率p,每个伪关键字也有一个访问概率q,假定搜索代价是找到关键字所访问的结点个数,即depth(i)+1,要求构造出一个二叉搜索树,使得在该树中的搜索各种关键字的代价最小,即:1+∑i=1ndepth(ki)×pi+∑i=0ndepth(di)×qi最小,也称为OBST问题(Optimal Binary Search Tree)
案例分析:对一个n=5的关键字集合及如下搜索概率,有以下两种树结构,其中第二种代价最小为2.75
i | 0 | 1 | 2 | 3 | 4 | 5 |
---|
p_i | 0.00 | 0.15 | 0.10 | 0.05 | 0.10 | 0.20 |
q_i | 0.05 | 0.10 | 0.05 | 0.05 | 0.05 | 0.10 |
最优二叉搜索树不一定是高度最矮的,搜索频率越大的也不一定出现在越上面
第1步:刻画一个最优子结构
如果一颗树是最优二叉搜索树,则它的根节点的左子树和右子树也都是最优二叉搜索树
第2步:递归地定义重叠子问题
假设当前树存在按序关键字<ki,ki+1,…,kj>,其中选取kr,i≤r≤j作为根结点,那么它的左子树就只有关键字<ki,…,kr−1>和伪关键字<di−1,…,dr−1>,右子树就只有关键字<kr+1,…,kj>和伪关键字<dr,…,dj>
但子树的搜索代价是以其高度计算的,将子树插到原树的根节点的位置会导致高度增加1,因此需要计算子树插入原树导致的搜索代价增量,即w[i][j]=1×(∑l=ijpl+∑l=i−1jql),它也满足递归式w[i][j]=w[i][r−1]+w[r+1,j]+1×pr
令e[i][j]表示以关键字<ki,…,kj>和伪关键字<di−1,…,dj>组成的最优二叉搜索树的搜索代价则有:
e[i][j]={qimini≤r≤j{e[i][r−1]+e[r+1][j]+w[i][j]}if i>jif i≤j
第3步:采用自底向上的方法计算最优解的值
考虑每个子树的关键字的起始下标是i,终止下标是j,则结点总数为l = j - i + 1
- l=0,就是伪关键字,搜索代价为q[i-1]
- l=1,r只能是i(左0右0)
- l=2,r可以是i(左0右1),i+1(左1右0),其中结点总数为0、1的在之前已经算出
- l=3,r可以是i(左0右2),i+1(左1右1),i+2(左2右0),其中结点总数为0、1、2的在之前已经算出
- 以此类推,直到l=n,其中长为0、1、2、3、…、n-1的在之前已经算出
第4步:利用结果构造得到最优解的过程
用一个二维数组root[i][j]记录划分子树选取的最佳根节点,那么从root[1][n]选取的划分根节点开始划分成左子树和右子树,然后再选取左子树的划分根节点和右子树的划分根节点,以此类推,直到无法划分
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| def optimal(root, i, j): if i == j + 1: print('d_' + str(j)) return r = root[i][j] print('k_' + str(r)) optimal(root, i, r-1) optimal(root, r+1, j)
def OBST(p,q): p = [0.0] + p length = len(q) w = [[0.0 for _ in range(length)] for _ in range(length)] e = [[0.0 for _ in range(length)] for _ in range(length)] root = [[0 for _ in range(length)] for _ in range(length)] for i in range(1, length): e[i][i-1] = q[i-1] w[i][i-1] = q[i-1] for l in range(1, length): for i in range(1, length - l + 1): j = i + l - 1 e[i][j] = float('inf') w[i][j] = w[i][j-1] + p[j] + q[j] for r in range(i, j+1): if r + 1 > j: min_e = e[i][r-1] + q[j] + w[i][j] else: min_e = e[i][r-1] + e[r+1][j] + w[i][j] if min_e < e[i][j]: e[i][j] = min_e root[i][j] = r optimal(root, 1, 5) min_e = e[1][length-1] return min_e
|
6.