分支限界法解01背包问题.docx

分支限界法解01背包问题
学院：网研院 姓名：XXX 学号：2013XXXXXX

一、 分支限界法原理
分支限界法类似于回溯法， 也是在问题的解空间上搜索问题解的算法。一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解；而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
由于求解目标不同，导致分支限界法与回溯法对解空间的搜索方式也不相同。回溯法以深度优先的方式搜索解空间，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间。
分支限界法的搜索策略是，在扩展结点处，先生成其所有的儿子结点(分支)，然后再从当前的活结点表中选择下一扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值(限界)，并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。
常见的分支限界法有如下两种：
队列式（FIFO）分支限界法：按照先进先出原则选取下一个节点为扩展节点。 活结点表是先进先出队列。FIFO分支限界法搜索策略：
u 一开始，根结点是唯一的活结点，根结点入队。
u 从活结点队中取出根结点后，作为当前扩展结点。
u 对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。
u 再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，重复上述过程，直到找到一个解或活结点队列为空为止。
LC（least cost）分支限界法（优先队列式分支限界法）：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。活结点表是优先权队列，LC分支限界法将选取具有最高优先级的活结点出队列，成为新的扩展节点。优先队列式分支限界法搜索策略：
u 对每一活结点计算一个优先级（某些信息的函数值）；
u 根据这些优先级从当前活结点表中优先选择一个优先级最高（最有利）的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。
u 再从活结点表中下一个优先级别最高的结点为当前扩展结点，重复上述过程，直到找到一个解或活结点队列为空为止。
二、 01背包问题简介
01背包问题假设有一个容量为c的背包，有n件物品，每件物品有重量w和价值v，求解怎样往背包里装物品能够在不超出背包容量c的情况下获得最大价值（本实验中物品的w和v都是大于0的实数，可以是整数也可以是浮点数）。
三、 FIFO分支限界法解01背包问题
1. 算法
l 输入背包容量capacity、物品数量count、物品的重量数组weights和物品的价值数组values，根据物品单位价值（value/weight）从大到小构造一个新数组，数组元素(OriginNode)有weight、value和valuePerWeight属性，根据该排序数组构造问题的解空间树（完全二叉树）；
l 定义一个FIFO队列(队列元素是节点，见下文)，队列可以在队尾插入节点和在队头删除节点；
l 定义节点（ArrayNode），节点是问题的解空间树上的点，它的属性有当前价值currentValue、当前重量currentWeight、上限价值upboundValue、节点对应的选择情况nodeChoses（0表示不选，1表示选，如“1 0 1”表示该节点选择了物品1和物品3，没有选择物品2）和节点在问题解空间树上的层次nodeCount(0 ~ n)；
l 定义一个计算节点价值上限的函数upBound()，upBound函数的计算规章是：
价值上限=节点现有价值+背包剩余容量*剩余物品的最大单位重量价值
l 定义一个全局的currentMaxValue记录程序目前取得的最大价值；
l 将一个空节点推入队列，空节点的当前价值、当前重量、节点层次均为0，全局的currentMaxValue初始化为0，使用upBound函数计算几点的价值上限并使用该属性初始化节点的upboundValue属性；
l 当队列不为空时，一直重复下述操作：从队首取得头节点，如果头节点的上限价值upboundValue比全局的currentMaxValue要大，则表明头节点的子节点中可能有最优节点，取头节点在问题的解空间树上的左子节点和右子节点，若左子节点和右子节点的重量没有超出背包容量且它们的upboundValue大于全局的currentMaxValue，将该子节点插入队尾，否则不插入，同时若子节点的当前价值currentValue大于全局的currentMaxValue，更新currentMaxValue。如果头结点的上限价值upboundValue比全局的currentMaxValue要小，则表明头结点及其子节点不可能有最优节点，将其舍弃。若头结点的当前价值currentValue正好等于全局的currentMaxValue且头结点的层次nodeCount等于物品数量n，则表明头结点是问题的解空间树上的叶子，该头结点可能就是最优节点，将其存储在全局的currentMaxNode属性中(随着队列遍历的进行当前存起来的节点仍可能被更优的节点覆盖)。
l 当队列为空时，表明所有的可能情况已被处理，此时全局的currentMaxNode属性指向了最优的节点，该节点的currentValue属性即为背包问题的最优解。
2. 算法复杂度
在最坏的情况下所有的节点都入队，最后一个节点才是最优解，这种情况下时间复杂度是指数阶。最好的情况是只装单位价值最大的物品，其余分支都不符合条件被截去这种情况下时间复杂度是常数时间。但分支限界法本质上还是穷举法，平均时间复杂度仍是指数阶。
空间复杂度的分析类似时间复杂度，也是指数阶。
3. 可能的改进
在本次实验中，即便取得了可能是最优解的问题空间树上的叶子节点的时候仍然会遍历其它节点以保证得到的是最优解，当对正确率的要求不是很高的时候，可以在取得第一个可能是最优解的节点时候便停止算法。
本次实验使用的是FIFO分支限界法，若使用优先队列式分支限界法（LC），在空间复杂度上的性能肯定会得到改善，若不要求结果十分准确，使用优先队列取得第一个可能节点时候便停止算法，则在时间复杂度上的性能应该也能优于FIFO分支限界（优先队列采取的是深度遍历，能更快到达叶子节点）。
四、 算法实现框架
本次实验使用的语言是java，OriginNode类用来按价值重量比构造排序数组，sort方法用于数组排序（出于便于实现的考虑使用了冒泡排序，改成快速排序可获得更好的性能）。

ArrayNode类用于构造问题的解空间树上的节点。

FIFOBBKnapsack类是程序的主类，定义了currentMaxValue等属性，起全局变量的作用供节点共同维护，upBound方法用于计算节点价值上限。

在FIFOBBKnapsack类的main方法里定义了分支限界法的逻辑，截取主要部分如下。

五、 总结
在本科的时候曾经做过背包问题的项目，所以本次实验我选择了01背包问题该题目。但在做本次实验之前，我对分支限界法的原理并不是很理解，经过查看课件及网上查找资料，同时结合自己对回溯法等的理解，我对分支限界法有了一个较好的理解，知道了两种主要的分支限界法及分支限界法如何应用于解01背包问题。在查找资料的过程中，我查看了许多网上的别人的代码实现，但大多都存在着问题或者混淆使用了两种分支限界法，最后通过参考别人的部分代码以及结合自己对FIFO分支限界法的理解，使用了java语言完成了该实验。通过本次试验，我基本上掌握了分支限界法解0-1背包问题的原理，同时锻炼了自己动手编写及调试代码的能力，收获良多。

附录
程序运行示例：

代码
import java.util.LinkedList;
import java.util.Scanner;

public class FIFOBBKnapsack {
int capacity;
int count;
float[] weights;
float[] values;
OriginNode[] originNodes;
float currentMaxValue;
ArrayNode currentMaxNode;

private float upBound(ArrayNode node) {
float weightLeft = this.capacity - node.currentWeight;
float bound = node.currentValue;
int t = node.nodeCount;
while (t < this.count && originNodes[t].weight <= weightLeft) {
weightLeft -= originNodes[t].weight;
bound += originNodes[t].value;
t++;
}
if (t < this.count)
bound += (originNodes[t].value / originNodes[t].weight)
* weightLeft;
return bound;
}

public static void main(String[] args) {
while (true) {
Scanner in = new Scanner(System.in);
FIFOBBKnapsack knapsack = new FIFOBBKnapsack();
System.out.println("******FIFO分支限界法解01背包问题开始******");
// 输入背包容量
System.out.println("---请输入背包容量（正整数）并回车---");
knapsack.capacity = in.nextInt();
// 输入物品数量
System.out.println("---请输入物品数量（正整数）并回车---");
knapsack.count = in.nextInt();
knapsack.weights = new float[knapsack.count];
knapsack.values = new float[knapsack.count];
// 构造物品重量数组
System.out.println("---请输入物品重量数组（空格隔开）并回车---");
for (int i = 0; i < knapsack.count; i++) {
knapsack.weights[i] = in.nextFloat();
}
// 构造物品价值数组
System.out.println("---请输入物品价值数组（空格隔开）并回车---");
for (int i = 0; i < knapsack.count; i++) {
knapsack.values[i] = in.nextFloat();
}

// 排序
knapsack.originNodes = new OriginNode[knapsack.count];
for (int i = 0; i < knapsack.count; i++) {
knapsack.originNodes[i] = new OriginNode(knapsack.weights[i],
knapsack.values[i]);
}
OriginNode.sort(knapsack.originNodes);

// FIFO队列
LinkedList<ArrayNode> arrayNodeList = new LinkedList<ArrayNode>();
ArrayNode headNode = new ArrayNode(0, 0, "", 0);
headNode.upboundValue = knapsack.upBound(headNode);
knapsack.currentMaxValue = 0;
knapsack.currentMaxNode = null;
arrayNodeList.push(headNode);
while (!arrayNodeList.isEmpty()) {
ArrayNode firstNode = arrayNodeList.pop();
if (firstNode.nodeCount == knapsack.count
&& firstNode.currentValue == knapsack.currentMaxValue) {
knapsack.currentMaxNode = firstNode;
continue;
}
if (firstNode.upboundValue >= knapsack.currentMaxValue
&& firstNode.nodeCount < knapsack.count) {
ArrayNode leftNode = new ArrayNode(
firstNode.currentWeight
+ knapsack.originNodes[firstNode.nodeCount].weight,
firstNode.currentValue
+ knapsack.originNodes[firstNode.nodeCount].value,
firstNode.nodeChoices + " 1",
firstNode.nodeCount + 1);
leftNode.upboundValue = knapsack.upBound(leftNode);
if (leftNode.currentWeight <= knapsack.capacity
&& leftNode.upboundValue > knapsack.currentMaxValue) {
arrayNodeList.add(leftNode);
if (leftNode.currentValue > knapsack.currentMaxValue) {
knapsack.currentMaxValue = leftNode.currentValue;
}
}
ArrayNode rightNode = new ArrayNode(
firstNode.currentWeight, firstNode.currentValue,
firstNode.nodeChoices + " 0",
firstNode.nodeCount + 1);
rightNode.upboundValue = knapsack.upBound(rightNode);
if (rightNode.upboundValue >= knapsack.currentMaxValue) {
arrayNodeList.add(rightNode);
}
}
}
System.out.println("背包能装下的最大价值是："
+ knapsack.currentMaxNode.currentValue + " 此时背包装的重量是："
+ knapsack.currentMaxNode.currentWeight);
System.out.println("物品的选择情况是：");
System.out.print("物品重量：");
for (int i = 0; i < knapsack.count; i++) {
System.out.print(knapsack.originNodes[i].weight + " ");
}
System.out.println("");
System.out.print("物品价值：");
for (int i = 0; i < knapsack.count; i++) {
System.out.print(knapsack.originNodes[i].value + " ");
}
System.out.println("");
System.out.print("选择情况（0表示不选1表示选）：");
System.out.println(knapsack.currentMaxNode.nodeChoices);
}
}
}

// 物品的重量一定不为0，价值可以是0
class OriginNode {
float weight;
float value;
float valuePerWeight;

public OriginNode(float weight, float value) {
this.weight = weight;
this.value = value;
this.valuePerWeight = value / weight;
}

// 冒泡排序将节点按照单位价值从大到小排序
public static void sort(OriginNode[] nodes) {
OriginNode tmp = null;
for (int i = 0; i < nodes.length; i++) {
for (int j = i + 1; j < nodes.length; j++) {
if (nodes[j].valuePerWeight > nodes[i].valuePerWeight) {
tmp = nodes[i];
nodes[i] = nodes[j];
nodes[j] = tmp;
}
}
}
}
}

class ArrayNode {
float currentWeight;
float currentValue;
float upboundValue;
String nodeChoices;
int nodeCount;

public ArrayNode(float currentWeight, float currentValue,
String nodeChoices, int nodeCount) {
this.currentWeight = currentWeight;
this.currentValue = currentValue;
this.nodeChoices = nodeChoices;
this.nodeCount = nodeCount;
}
}