文档章节

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

小强斋太
 小强斋太
发布于 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

共有 人打赏支持
小强斋太
粉丝 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
算法设计策略----回溯法和分枝限界法

显示约束和解空间:规定每个分量xi取值的约束条件称为显式约束。对给定的一个问题,显示约束规定了所有可能的元组,他们组成问题的候选解集,被称为该问题实例的解空间。 隐式约束和判定函数...

Superheros
03/10
5
0

没有更多内容

加载失败,请刷新页面

加载更多

RxJS的另外四种实现方式(四)——性能最高的库(续)

接上一篇RxJS的另外四种实现方式(三)——性能最高的库 上一篇文章我展示了这个最高性能库的实现方法。下面我介绍一下这个性能提升的秘密。 首先,为了弄清楚Most库究竟为何如此快,我必须借...

一个灰
40分钟前
1
0
麒麟AI首席科学家现世

8月31日,华为发布了新一代顶级人工智能手机芯片麒麟980,成为全球首款7nm工艺手机芯片,AI方面也实现飞跃,支持人脸识别、物体识别、物体检测、图像分割、智能翻译等。 虽然如今人人都在热议...

问题终结者
昨天
1
0
告警系统主脚本、告警系统配置文件、告警系统监控项目

告警系统主脚本 main.sh内容 #!/bin/bash#Written by aming.# 是否发送邮件的开关export send=1# 过滤ip地址export addr=`/sbin/ifconfig |grep -A1 "ens33: "|awk '/inet/ {pr...

芬野de博客
昨天
2
0
MySQL autocommit探究

-- sessionA:tx_isolation=REPEATABLE-READmysql> select connection_id();+-----------------+| connection_id() |+-----------------+| 28 |+-----------------+......

安小乐
昨天
7
0
c++多线程锁 Mutex  自动判断死锁

c++多线程锁可以使用absl::Mutex std::mutex这两种,下面是demo代码。 使用absl:Mutex的时候打印: [mutex.cc : 1338] RAW: Cycle: [mutex.cc : 1352] RAW: mutex@0x683b68 stack: @ 0x43856......

青黑
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部