5.《算法设计与分析》试题库

{// 搜索左子树Р x[i] = 1;Р cw += w[i];Р backtrack(i + 1);Р cw -= w[i]; }Р if (cw + r > bestw) {Р x[i] = 0; // 搜索右子树Р backtrack(i + 1); }Р r += w[i];Р }Р5. 用分支限界法解装载问题时,对算法进行了一些改进,下面的程序段给出了改进部分;试说明斜线部分完成什么功能,以及这样做的原因,即采用这样的方式,算法在执行上有什么不同。Р// 检查左儿子结点Р Type wt = Ew + w[i]; // 左儿子结点的重量Р if (wt <= c) { // 可行结点Р if (wt > bestw) bestw = wt;Р // 加入活结点队列Р if (i < n) Q.Add(wt);Р}Р// 检查右儿子结点Р if (Ew + r > bestw && i < n)Р Q.Add(Ew); // 可能含最优解Р Q.Delete(Ew); // 取下一扩展结点Р Р解答:斜线标识的部分完成的功能为:提前更新bestw值;Р这样做可以尽早的进行对右子树的剪枝。具体为:算法Maxloading初始时将bestw设置为0,直到搜索到第一个叶结点时才更新bestw。因此在算法搜索到第一个叶子结点之前,总有bestw=0,r>0 故Ew+r>bestw总是成立。也就是说,此时右子树测试不起作用。Р为了使上述右子树测试尽早生效,应提早更新bestw。又知算法最终找到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在搜索进入左子树是增加,因此,可以在算法每一次进入左子树时更新bestw的值。Р7. 最长公共子序列问题:给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子序列。