分支限界---->装载问题
分支限界---->装载问题
小强斋太 发表于1年前
分支限界---->装载问题
  • 发表于 1年前
  • 阅读 6
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

装载问题

一、问题描述

有两艘船,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

共有 人打赏支持
粉丝 0
博文 181
码字总数 0
×
小强斋太
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: