文档章节

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

小强斋太
 小强斋太
发布于 2016/11/09 20:05
字数 890
阅读 6
收藏 0
点赞 0
评论 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
动态规划和分治法,贪心算法以及递归的再一次深刻理解和体会

每次体会算法都有新的感觉,刷题越多,对算法的理解感觉也就越深刻。 下面我们来重新体会下分治法,动态规划,贪心法,递归的理解。 1.分治法: 将问题分成单独的阶段,每个阶段互相不干扰很...

qingliangdexiar
2017/08/25
0
0
python 回溯法 记录

一直不是太理解回溯法,这几天集中学习了一下,记录如下。 回溯法有“通用的解题法”之称。 1.定义: 也叫试探法,它是一种系统地搜索问题的解的方法。 2.基本思想: 从一条路往前走,能进则...

罗兵
2017/05/29
0
0
Java类装载体系中的隔离性

正 文 Java中类的查找与装载出现的问题总是会时不时出现在Java程序员面前,这并不是什么丢脸的事情,相信没有一个 Java程序员没遇到过ClassNotException,因此不要为被人瞅见自己也犯这样的错...

crazyinsomnia
2010/01/31
743
0
面试算法:线性表

链表 队列 堆栈 实践应用 难题首选[动归],受阻[贪心][暴力];考虑[分治]思想,配合[排序][哈希]; 动态规划:动态数组降低空间复杂度 贪心法:Dijkstra最短路径、最小生成树Prim、Kruskal算...

datacube
2016/07/20
0
0
常用算法和复杂度总结

一、常用算法和复杂度 算法 名称 复杂度 备注 快速排序 QuickSort(A,p,r) 最坏:O(n2) 平均:O(nlog n) 均衡划分:O(nlog n) 合并排序 MergeSort(A,p,r) O(nlog n) 选最大 FindMax O(n) 选最...

啊莱
2010/01/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

mysql导入导出包括函数或者存储过程

mysql导入导出包括函数或者存储过程 2012-11-16 10:12:20 0个评论 收藏 我要投稿 mysql导入导出包括函数或者存储过程 1.mysql导出整个数据库 mysqldump -h hostname -u username -p databas...

rootliu
4分钟前
0
0
Hyperledger Fabric 客户端开发一

前面介绍了hyperledger Fabric 安装, Chaincode的开发和运维, 现在来说说hyperledger fabric的客户端相关的开发。hyperledger 的客户端开发, 实际上指的是Chaincode的客户端开发。 同传统...

十一月不远
8分钟前
0
0
第18章 Linux集群架构

keepalived介绍 在这里使用keepalived来实现高可用集群,因为heartbeat在centos6上有一些问题,影响实验效果 heartbeat 切换的时候,会不是很及时——>比如:主 已经宕机了,但 从 却一直启动...

Linux学习笔记
9分钟前
0
0
awk常用的几条命令组合

前言 最近在生产上查问题,也是练就了一下awk的命令。 生产上的数据安全性要求比较高,一般要拿到测试环境都需要脱敏,但是脱敏的数据会有很多程序上的不适应。 所以有时候查询问题,查询一条...

码代码的小司机
9分钟前
0
0
python 多版本安装及切换

1.安装必要的扩展 # yum install zlib-devel bzip2-devel openssl-devel ncurses-devel sqlite-devel readline-devel tk-de 2.下载python3.7源码 # wget https://www.python.org/ftp/python......

青-争
10分钟前
0
0
看看8年阿里架构师怎样讲述Dubbo和Spring Cloud微服务架构

微服务架构是互联网很热门的话题,是互联网技术发展的必然结果。它提倡将单一应用程序划分成一组小的服务,服务之间互相协调、互相配合,为用户提供最终价值。虽然微服务架构没有公认的技术标...

Java大蜗牛
10分钟前
0
0
CDH的坑之Sqoop导出数据到MySQL

CDH的坑之Sqoop导出数据到MySQL 最近使用Sqoop从Hive导出数据到MySQL中,出现了一系列的问题,下面将这个问题记录一下,避免再度踩坑! 导出语句 sqoop export --connect jdbc:mysql://192....

星汉
13分钟前
0
0
PowerDesigner连接MySQL和逆向工程图

最近想梳理公司项目的表间关系,从项目后台管理系统的操作入手,以及代码的hibernate注解入手,都不算特别尽人意,于是最后还是鼓捣了一下PowerDesigner的逆向工程图,这样更直观一些。 想着...

Oo若离oO
14分钟前
0
0
威胁web应用安全的错误

一般绝大部分的web应用攻击都是没特定目标的大范围漏洞扫描,只有少数攻击确实是为入侵特定目标而进行的针对性尝试。这两种攻击都非常频繁,难以准确检测出来,许多网站的web应用防火墙都无法...

上树的熊
16分钟前
2
0
pypy2 install crypto error

install pycryptodome instead pip install pycryptodome

coord
20分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部