免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 2427 | 回复: 0

[算法] 求助:回溯法 装载问题 [复制链接]

论坛徽章:
0
发表于 2017-02-20 16:52 |显示全部楼层
本帖最后由 proof 于 2017-02-20 17:08 编辑

回溯法解装载问题(轮船、集装箱。题略)。
可以引入一个上界函数,用于剪去不含最优解的子树,
设z是解空间树第i层上的当前扩展结点。cw是当前载重量;bestw是当前最优载重量;r是剩余集装箱的重量。
定义上界函数为cw+r。在以z为根的子树中任一叶结点所相应的载重量均不超过cw+r。因此,当cw+r<=bestw时,可将z的右子树剪去。


关于“上界函数”。既然是“以z为根的所有叶结点”都不满意条件。为什么不剪去z的所有子树,返回z上一层?
为什么只剪去z的“右子树”,保留了“左子树”?

例如:
asdf.jpg

已经搜索到了结点F
此时发现“当前载重量”+“剩余集装箱重量”< “当前最优载重量”
那么就没必要搜索L和M了。为什么书上说只裁剪右子树(M),没说裁剪L?



您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP