试题详情
简答题用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进部分；试说明斜线部分完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同。
  • 斜线标识的部分完成的功能为：提前更新bestw值；
    这样做可以尽早的进行对右子树的剪枝。具体为：算法Maxloading初始时将bestw设置为0，直到搜索到第一个叶结点时才更新bestw。因此在算法搜索到第一个叶子结点之前，总有bestw=0，r>0 故Ew+r>bestw总是成立。也就是说，此时右子树测试不起作用。
    为了使上述右子树测试尽早生效，应提早更新bestw。又知算法最终找到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在搜索进入左子树是增加，因此，可以在算法每一次进入左子树时更新bestw的值。

  • 关注下方微信公众号，在线模考后查看

热门试题