分支界限
0.目录
以下均转载于：五大常用算法-分支界限,加入了一些我自己的想法
1.基本描述
类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
分支搜索算法
所谓“分支”就是采用广度优先的策略，依次搜索E-结点的所有分支，也就是所有相邻结点，抛弃不满足约束条件的结点，其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点，继续搜索。
选择下一个E-结点的方式不同，则会有几种不同的分支搜索方式。
1.FIFO搜索
2.LIFO搜索
3.优先队列式搜索
2.分支限界法的一般过程
由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。
1.分支限界法的搜索策略是：
在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解
2.分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。
3.回溯法和分支界限法的一些区别
回溯法和分支限界法的一些区别：
- 方法对解空间树的搜索方式
- 存储结点的常用数据结构
- 结点存储特性常用应用
- 回溯法深度优先搜索堆栈活结点的所有可行子结点被遍历后才被从栈中弹出找出满足约束条件的所有解
- 分支限界法广度优先或最小消耗优先搜索队列、优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解或特定意义下的最优解
4.举个例子
还是上文回溯算法中的例子，给定一组数组nums，再给定一个目标值target,找出集合nums的所有子集使其之和刚好为目标值，nums中的数只能使用一次。不过我们稍作修改，现在只需要找到一个子集即可。虽然这个例子不算优化问题，但是却很好的展示了只要满足条件即可。
下面按照思路进行求解。
4.1构造解空间树
这里和回溯算法中解空间树其实相同，我们采用子集树
4.2确定搜索方式
这里我使用的FIFO的队列形式，使用该队列维护一张活节点表，队首为扩展节点。
4.3利用剪枝函数进行界限分割
假定我们给出的数组为nums = {1,1,2,3,4,5,6},target=9,那么现在有一种情况是1+1+2=4,当前节点为第3层（从第0层开始），那么其左子树则为1+1+2+3=7满足条件，那么需不需要进入其右子树呢？其右子树表示为1+1+2+0+xxx,即不加入第3层，下面还有3层为4,5,6。计算上界为1+1+2+4+5+6>9的，这样说明第3层的右子树可能存在解，我们需要遍历，但是考虑另一种情况，如果我把nums改为{1,1,2,3,1,1,1},则右子树上界为1+1+2+0+1+1+1=7<9,显然就算下面所有都加完，都不能达到9，不需要搜索右子树。
以图的形式再次说明
下面是整体代码
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
/**
* 分支限界法
*/
static int[] nums = {1,1,2,3,4,5,6};
static int target = 9;
static int n = nums.length;
public static void main(String[] args) {
solve();
}
private static void solve() {
boolean[] currentX = new boolean[n];
//这里采用FIFO队列存储活节点
Queue<Node> queue = new LinkedList<Node>();
int i = 0;
int currentValue = 0;
int up;
do {
//检查左子树可行性
if(currentValue+nums[i] < target) {
//进入左子树
currentX[i] = true;
queue.add(new Node(currentX.clone(),currentValue+nums[i] ,i+1));
}else if (currentValue+nums[i] == target) {
//如果产生可行解
currentX[i] = true;
System.out.println(Arrays.toString(currentX));
break;
}
up = bound(i);
if(currentValue+up >= target) {
//进入右子树
currentX[i] = false;
queue.add(new Node(currentX.clone(),currentValue,i+1));
}
//取得扩展节点
Node currentNode = queue.poll();
currentX = currentNode.x;
currentValue = currentNode.vlaue;
i = currentNode.level;
}while(!queue.isEmpty());
}
private static class Node{
boolean[] x;//用于恢复现场，记录其父节点及其以上加入情况
int vlaue;//当前累加值
int level;//当前是第几层
public Node(boolean x[],int vlaue, int level) {
super();
this.x = x;
this.vlaue = vlaue;
this.level = level;
}
}
//剪枝函数
private static int bound(int i) {
int sum = 0;
i++;
for(;i<n;i++) {
sum+=nums[i];
}
return sum;
}
}
运行结果如下：
[true, true, false, true, true, false, false]
即：1+1+3+4=9下面在给出0-1背包问题的分支限界解法。
0-1背包问题：给定一些物品，每个物品均有其价格和重量，现有一个有限容量的背包，问如何选择物品才能使得所获价值最大，物品不能分块装。
物品:
weight = {2, 2, 6, 5, 4};
value = {6, 3, 5, 4, 6};
容量:
c = 10;代码如下：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
/**
* 分支界限法，解决0-1背包问题
*/
static int bestValue = 0;
static int[] weight = {2, 2, 6, 5, 4};
static int[] value = {6, 3, 5, 4, 6};
static int c = 10;
static int n = weight.length;
static boolean[] bestX = new boolean[n];
public static void main(String[] args) {
//对物品进行按照性价比预排序，因为总是期望性价比高的先存放（当然也可以自定义规则）
int[] oldIndex = selSort();
solve();
//恢复原序列
boolean[] realX = new boolean[n];
int valueS =0;
for (int i = 0; i < bestX.length; i++) {
realX[oldIndex[i]] = bestX[i];
if(bestX[i]){
valueS+=value[i];
}
}
System.out.println(Arrays.toString(realX));
System.out.println("vlaue:"+valueS);
}
/*
* 使用简单选择排序，数据量大时可选择快速排序，堆排，归并排序等高效排序算法
*/
private static int[] selSort() {
float[] p = new float[weight.length];
int[] oldeIndex = new int[p.length];
for (int i = 0; i < p.length; i++) {
p[i] = (float) value[i] / weight[i];
oldeIndex[i] = i;
}
//用来存储排序后，元素在原来数组中的位置，方便后续恢复信息,不要求按原数组输出可不用这一步
for (int i = 0; i < p.length - 1; i++) {
for (int j = i + 1; j < p.length; j++) {
if (p[i] < p[j]) {
float tempP = p[i];
p[i] = p[j];
p[j] = tempP;
int tempW = weight[i];
weight[i] = weight[j];
weight[j] = tempW;
int tempV = value[i];
value[i] = value[j];
value[j] = tempV;
int tempI = oldeIndex[i];
oldeIndex[i] = oldeIndex[j];
oldeIndex[j] = tempI;
}
}
}
return oldeIndex;
}
private static void solve() {
int i = 0;
int currentValue = 0;
int currentWeight = 0;
boolean[] currentX = new boolean[weight.length];
//申请活节点FIFO队列
Queue<Node> queue = new LinkedList<Node>();
do {
//判定左子树可行性
if (currentWeight + weight[i] <= c) {
currentX[i] = true;
queue.add(new Node(currentX.clone(), currentValue + value[i], currentWeight + weight[i], i + 1));
//判断是否需要更新最优解
if (currentValue + value[i] > bestValue) {
bestValue = currentValue + value[i];
bestX = currentX.clone();
}
}
//计算上界
if (currentValue + bound(i, currentWeight) >= bestValue) {
//可以进入右子树
currentX[i] = false;
queue.add(new Node(currentX.clone(), currentValue, currentWeight, i + 1));
}
//更新扩展节点
Node currrentNode = queue.poll();
currentValue = currrentNode.currentValue;
currentWeight = currrentNode.currentWeight;
currentX = currrentNode.x;
i = currrentNode.level;
} while (!queue.isEmpty() && i != n);
}
private static float bound(int i, int currentWeight) {
i++;
float p = 0;
while (currentWeight <= c && i < n) {
p += value[i];
currentWeight += weight[i];
}
if (i < n) {
//删除多装的一个
p -= value[i];
currentWeight -= weight[i];
p += (c - currentWeight) * ((float) (value[i]) / (weight[i]));
}
return p;
}
private static class Node {
boolean[] x;//保存背包中以存放的物品信息
int currentValue;
int currentWeight;
int level;
public Node(boolean[] x, int currentValue, int currentWeight, int level) {
this.x = x;
this.currentValue = currentValue;
this.currentWeight = currentWeight;
this.level = level;
}
}
}
执行结果:
[true, true, false, false, true]
vlaue:15
即：第1,2,5个物品，价值6+3+6=15，重量2+2+4 = 8上一篇： linux 搭建svn服务器
下一篇： 装载问题 | 分支界限法