五大算法之分支定界法 2——通过剪枝提升效率

本贴最后更新于 2890 天前,其中的信息可能已经时过境迁

上篇博客(五大算法之分支定界法)介绍了使用分支定界法解决装载问题,该算法的时间、空间复杂度均为2^n,这篇博客考虑如何改进该算法,提升效率。

每次加入活节点之前,都需要考虑一下当前装载重量加上剩余货物总重量是否大于当前最优解,如果不是的话则表明该分支不可能在产生最优解,可以去除。也即根据这个约束条件进行剪枝。

改进后运行w={ 10, 2, 5, 7, 5, 9, 4, 3, 2, 5, 3, 3, 4, 2, 3, 4, 3, 3, 4, 1, 2, 1, 2, 1, 2, 1 }实例,需要1838ms,没有优化之前的算法需要27776ms,效率提升明显。

代码:

package test;

import java.util.LinkedList;

/**

  • 用分支定界法求装载问题,改进版
  • @author yanghang

*/
public class Fenzhidingjie2 {

private static float[] w = { 10, 2, 5, 7, 5, 9, 4, 3, 2, 5, 3, 3, 4, 2, 3,
		4, 3, 3, 4, 1, 2, 1, 2, 1, 2, 1 }; // 货箱质量数组
private static int n = w.length; // 货箱数量
private static float c1 = 50; // 第一艘船的载重量
private static float c2 = 50; // 第二艘船的载重量

private static float bestw; // 第一艘船的最大装载
private static float ew; // 当前船的装载量
private static LinkedList<Float> mq = new LinkedList<Float>(); // FIFO队列

/**
 * 最优装载值
 * 
 * @param c
 */
public static float maxLoading(float c) {
	mq.addLast(new Float(-1)); // 初始化结点队列,标记分层
	int i = 0; // E-结点的层
	ew = 0; // 当前船的装载量
	bestw = 0; // 目前的最优值
	// 剩余货物的重量,用于剪枝
	float r = 0;
	for (float f : w) {
		r += f;
	}
	r -= w[0];

	while (!mq.isEmpty()) { // 搜索子集空间树
		// 检查E-结点的左孩子,货箱i是否可以装载
		if (ew + w[i] <= c) {
			if (ew + w[i] > bestw) {
				bestw = ew + w[i]; // 更新最优值
			}
			addLiveNode(ew + w[i], i); // 货箱i可以装载
		}
		// 剪枝,当前重量加剩余重量大于当前最优值才继续,否则该分支不可能产生最优解
		if (ew + r > bestw) {
			addLiveNode(ew, i); // 右孩子总是可行的,不装载货物i
		}
		ew = (Float) mq.removeFirst(); // 取下一个结点

		if (ew == -1) { // 到达层的尾部
			if (mq.isEmpty()) {
				return bestw;
			}
			mq.addLast(new Float(-1));
			ew = (Float) mq.removeFirst(); // 取下一个结点
			i++; // ew的层
			r -= w[i]; // 更新剩余重量
		}
	}
	return bestw;
}

/**
 * 入队
 * 
 * @param wt
 * @param i
 */
public static void addLiveNode(float wt, int i) {
	if (i == n - 1) { // 下标从0开始,是叶子
		if (wt > bestw) {
			bestw = wt;
		}
	} else { // 不是叶子
		mq.addLast(new Float(wt));
	}
}

public static void main(String[] args) {
	// TODO Auto-generated method stub
	// 所有货箱的重量之和
	long start = System.currentTimeMillis();

	float s = 0;
	for (float f : w) {
		s += f;
	}
	if (s <= c1 || s <= c2) {
		System.out.println("need only one ship!");
	}
	if (s > c1 + c2) {
		System.out.println("no solution!");
		return;
	}

	float bestw = Fenzhidingjie2.maxLoading(c1);

	if (s - bestw <= c2) {
		System.out.println("The first ship loading " + bestw);
		System.out.println("The second ship loading " + (s - bestw));
	} else {
		System.out.println("no solution!");
	}
	long end = System.currentTimeMillis();
	System.out.println(end - start);
}

}

  • 算法
    428 引用 • 254 回帖 • 24 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • Ant-Design

    Ant Design 是服务于企业级产品的设计体系,基于确定和自然的设计价值观上的模块化解决方案,让设计者和开发者专注于更好的用户体验。

    17 引用 • 23 回帖
  • 数据库

    据说 99% 的性能瓶颈都在数据库。

    342 引用 • 708 回帖
  • GitBook

    GitBook 使您的团队可以轻松编写和维护高质量的文档。 分享知识,提高团队的工作效率,让用户满意。

    3 引用 • 8 回帖 • 4 关注
  • B3log

    B3log 是一个开源组织,名字来源于“Bulletin Board Blog”缩写,目标是将独立博客与论坛结合,形成一种新的网络社区体验,详细请看 B3log 构思。目前 B3log 已经开源了多款产品:SymSoloVditor思源笔记

    1063 引用 • 3453 回帖 • 203 关注
  • SVN

    SVN 是 Subversion 的简称,是一个开放源代码的版本控制系统,相较于 RCS、CVS,它采用了分支管理系统,它的设计目标就是取代 CVS。

    29 引用 • 98 回帖 • 680 关注
  • Openfire

    Openfire 是开源的、基于可拓展通讯和表示协议 (XMPP)、采用 Java 编程语言开发的实时协作服务器。Openfire 的效率很高,单台服务器可支持上万并发用户。

    6 引用 • 7 回帖 • 94 关注
  • SQLServer

    SQL Server 是由 [微软] 开发和推广的关系数据库管理系统(DBMS),它最初是由 微软、Sybase 和 Ashton-Tate 三家公司共同开发的,并于 1988 年推出了第一个 OS/2 版本。

    21 引用 • 31 回帖 • 1 关注
  • SQLite

    SQLite 是一个进程内的库,实现了自给自足的、无服务器的、零配置的、事务性的 SQL 数据库引擎。SQLite 是全世界使用最为广泛的数据库引擎。

    5 引用 • 7 回帖
  • Quicker

    Quicker 您的指尖工具箱!操作更少,收获更多!

    32 引用 • 131 回帖 • 1 关注
  • Kotlin

    Kotlin 是一种在 Java 虚拟机上运行的静态类型编程语言,由 JetBrains 设计开发并开源。Kotlin 可以编译成 Java 字节码,也可以编译成 JavaScript,方便在没有 JVM 的设备上运行。在 Google I/O 2017 中,Google 宣布 Kotlin 成为 Android 官方开发语言。

    19 引用 • 33 回帖 • 64 关注
  • InfluxDB

    InfluxDB 是一个开源的没有外部依赖的时间序列数据库。适用于记录度量,事件及实时分析。

    2 引用 • 73 关注
  • FreeMarker

    FreeMarker 是一款好用且功能强大的 Java 模版引擎。

    23 引用 • 20 回帖 • 462 关注
  • Postman

    Postman 是一款简单好用的 HTTP API 调试工具。

    4 引用 • 3 回帖 • 4 关注
  • Redis

    Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 API。从 2010 年 3 月 15 日起,Redis 的开发工作由 VMware 主持。从 2013 年 5 月开始,Redis 的开发由 Pivotal 赞助。

    286 引用 • 248 回帖 • 61 关注
  • 反馈

    Communication channel for makers and users.

    123 引用 • 911 回帖 • 245 关注
  • Chrome

    Chrome 又称 Google 浏览器,是一个由谷歌公司开发的网页浏览器。该浏览器是基于其他开源软件所编写,包括 WebKit,目标是提升稳定性、速度和安全性,并创造出简单且有效率的使用者界面。

    62 引用 • 289 回帖 • 1 关注
  • TextBundle

    TextBundle 文件格式旨在应用程序之间交换 Markdown 或 Fountain 之类的纯文本文件时,提供更无缝的用户体验。

    1 引用 • 2 回帖 • 49 关注
  • Log4j

    Log4j 是 Apache 开源的一款使用广泛的 Java 日志组件。

    20 引用 • 18 回帖 • 30 关注
  • GAE

    Google App Engine(GAE)是 Google 管理的数据中心中用于 WEB 应用程序的开发和托管的平台。2008 年 4 月 发布第一个测试版本。目前支持 Python、Java 和 Go 开发部署。全球已有数十万的开发者在其上开发了众多的应用。

    14 引用 • 42 回帖 • 764 关注
  • Thymeleaf

    Thymeleaf 是一款用于渲染 XML/XHTML/HTML5 内容的模板引擎。类似 Velocity、 FreeMarker 等,它也可以轻易的与 Spring 等 Web 框架进行集成作为 Web 应用的模板引擎。与其它模板引擎相比,Thymeleaf 最大的特点是能够直接在浏览器中打开并正确显示模板页面,而不需要启动整个 Web 应用。

    11 引用 • 19 回帖 • 355 关注
  • GraphQL

    GraphQL 是一个用于 API 的查询语言,是一个使用基于类型系统来执行查询的服务端运行时(类型系统由你的数据定义)。GraphQL 并没有和任何特定数据库或者存储引擎绑定,而是依靠你现有的代码和数据支撑。

    4 引用 • 3 回帖 • 9 关注
  • ZeroNet

    ZeroNet 是一个基于比特币加密技术和 BT 网络技术的去中心化的、开放开源的网络和交流系统。

    1 引用 • 21 回帖 • 638 关注
  • 持续集成

    持续集成(Continuous Integration)是一种软件开发实践,即团队开发成员经常集成他们的工作,通过每个成员每天至少集成一次,也就意味着每天可能会发生多次集成。每次集成都通过自动化的构建(包括编译,发布,自动化测试)来验证,从而尽早地发现集成错误。

    15 引用 • 7 回帖 • 1 关注
  • 前端

    前端技术一般分为前端设计和前端开发,前端设计可以理解为网站的视觉设计,前端开发则是网站的前台代码实现,包括 HTML、CSS 以及 JavaScript 等。

    247 引用 • 1348 回帖
  • 星云链

    星云链是一个开源公链,业内简单的将其称为区块链上的谷歌。其实它不仅仅是区块链搜索引擎,一个公链的所有功能,它基本都有,比如你可以用它来开发部署你的去中心化的 APP,你可以在上面编写智能合约,发送交易等等。3 分钟快速接入星云链 (NAS) 测试网

    3 引用 • 16 回帖 • 1 关注
  • Kafka

    Kafka 是一种高吞吐量的分布式发布订阅消息系统,它可以处理消费者规模的网站中的所有动作流数据。 这种动作(网页浏览,搜索和其他用户的行动)是现代系统中许多功能的基础。 这些数据通常是由于吞吐量的要求而通过处理日志和日志聚合来解决。

    36 引用 • 35 回帖 • 1 关注
  • V2EX

    V2EX 是创意工作者们的社区。这里目前汇聚了超过 400,000 名主要来自互联网行业、游戏行业和媒体行业的创意工作者。V2EX 希望能够成为创意工作者们的生活和事业的一部分。

    17 引用 • 236 回帖 • 328 关注