文档章节

分支限界---->装载问题

小强斋太
 小强斋太
发布于 2016/11/09 20:05
字数 890
阅读 6
收藏 0

装载问题

一、问题描述

有两艘船,n个货箱。第一艘船的载重量是c1,第二艘船的载重量是c2,wi是货箱i 的重量,且w1+w2+……+wn≤c1+c2。确定是否有一种可将所有n个货箱全部装船的方法。若有的话,找出该方法。

例子:

有两艘船,3个货箱。第一艘船的载重量是50,第二艘船的载重量是50。

         当w =[10,40,40]时,有解;

         当w =[20,40,40]时,无解。

二、问题是否可解的判断

当第一艘船的可行最大装载为bestw时,若w1+w2+……+wn-bestw≤c2,则问题有解。即

总的重量 - 第一艘船实际能够装载的最大重量  < 第二艘船的载重量 时

因此,此问题可以转化为第一艘船的装载问题。

三、分析

  • “装载上界”,就是假设装载当前物品以后的所有物品。
  • 若当前分支的“装载上界”,比现有的最大装载小,则该分支就无需继续搜索。这样就缩小搜索范围,提高了搜索效率。
  • 优先队列中结点优先级常规定为一个与该结点相关的数值p,它一般表示其接近最优解的程度,本例就以当前结点所在分支的装载上界为优先值

四、例子

W={10,30,50},C1=60, 所构成的子集树如下图所表示:

4.1、FIFO限界搜索过程

1)初始队列中只有结点A;

2)结点A变为E-结点扩充B入队,bestw=10;

  结点C的装载上界为30+50=80> bestw,也入队;

3)结点B变为E-结点扩充D入队,bestw=40;

  结点E的装载上界为60> bestw,也入队;

4)结点C变为E-结点扩充F入队,bestw仍为40;

  结点G的装载上界为50> bestw,也入队;

5)结点D变为E-结点,叶结点H超过容量,

  叶结点I的装载为40,bestw仍为40;

6)结点E变为E-结点,叶结点J装载量为60,bestw为60;

  叶结点K被剪掉;

7)结点F变为E-结点,叶结点L超过容量,bestw为60;

  叶结点M被剪掉;

8)结点G变为E-结点,叶结点N、O都被剪掉;

  此时队列空算法结束。

4.2、LC-搜索的过程

1) 初始队列中只有结点A;

2) 结点A变为E-结点扩充B入堆,bestw=10;

结点C的装载上界30+50=80>bestw,入堆;堆中B上界为90在优先队列首。

3) 结点B变为E-结点扩充D入堆,bestw=40;

结点E的装载上界60>bestw,入堆;堆中D上界为90为优先队列首。

4) 结点D变为E-结点,叶结点H超过重量,叶结点I的装载为40,入堆,bestw仍为40;此时堆中C上界为80为优先队列首。

5) 结点C变为E-结点扩充F入堆,bestw仍为40;

结点G的装载上界50> bestw,入堆;此时堆中E上界为60为优先队首

6) 结点E变为E-结点,叶结点J装载量为60入堆,bestw变为60;

叶结点K上界10<bestw被剪掉;此时堆中J上界为60为优先队列首。

7) 结点J变为E-结点,扩展的层次为4算法结束。

虽然此时堆并不空,但可以确定已找到了最优解。

优先队列限界搜索解空间的过程是:A-B-D-C-E-J

本文转载自:http://www.cnblogs.com/xqzt/archive/2013/05/18/5637081.html

共有 人打赏支持
下一篇: ETL面试题
小强斋太
粉丝 0
博文 181
码字总数 0
作品 0
广州
私信 提问
算法设计与分析复习——第六章:分支先结法

第六章:分支先结法 1,请简述分支限界法的算法思想以及两种主要的实现方法。 答:分支限界法的算法思想是在问题的解空间树上以广度优先或最小耗费(最大效益)优先方式搜索问题的满足约束条...

科技小能手
2017/11/12
0
0
游戏与常用的五大算法---下篇

前言: 心是一个人的翅膀,心有多大,世界就有多大。很多时候限制我们的,不是周遭的环境,也不是他人的言行,而是我们自己!看不开,放不下,忘不了,把自己囚禁在灰暗的记忆里;不敢想,不...

loving_forever_
2017/01/08
0
0
五大常用算法:分治、动态规划、贪心、回溯、分支限界

分治:把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并 http://www.cnblogs.com/ste...

毛朱
2015/09/11
2.5K
0
回溯算法之购物车(0-1 背包问题)

1、问题(参考趣学算法) 2、分析 3、代码实现 #include include using namespace std; define MAX_NUM 200 //商品的个数,载物车最大承受重量int n = 0, W = 0;//当前载物车里面的总重量和总...

u011068702
05/10
0
0
优先队列式分支限界法-最小重量机器设计问题

问题描述: 设某一机器由n个部件组成,每一种部件都可以从m个不同的供应商处购得。设是从供应商j处购得的部件i的重量,是相应的价格。试设计一个优先队列式分支限界法,给出总价格不超过d的最...

DNE
10/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

移动端Appium自动化测试框架的优势

众所周知,现在市面上的移动端操作系统已被Android和IOS占领,其中Android的份额更是在80%以上。那么面对市面上林林总总的自动化测试框架和工具,为什么说Appium在自动化测试框架的统治级优势...

程序猿拿Q
25分钟前
1
0
设计模式 之 观察者模式

设计模式 之 观察者模式 场景 场景比较简单,当一个对象的状态发生改变时,自动通知所有依赖(或观察)它的对象。 比如:发布/订阅 原理:发布者存储N个订阅者的对象信息,当发布者发布消息时...

GMarshal
29分钟前
1
0
linux 常用

netstat -tunlp |grep 8080 查看8080 占用 netstat -tunlp 用于查看所有的端口号的进程情况

west_coast
33分钟前
2
0
Bytom信息上链教程

比原项目仓库: Github地址:https://github.com/Bytom/bytom Gitee地址:https://gitee.com/BytomBlockchain/bytom ##用比原链(Bytom)实现信息上链 很多了解比原链的都知道,比原链是专注...

比原链Bytom
39分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部