分享-分支限界法(求最优装载)

1. 分支搜索算法

   (1) 引入
       用回溯算法解决问题时，是按照深度优先的策略在问题的状态空间中，尝试搜索可能的路径，不便于在搜索过程中对不同的解进行
比较，只能在搜索到所有解得情况下，才能通过比较确定哪个是最优解。这类问题更适合广度优先策略搜索，因为在扩展结点时，可以在
E-结点的各个子结点之间进行必要的比较，有选择的进行下一步扩展。这里的分支限界法就是一种较好的解决最优化问题的算法。

       分支界限法是由"分支"策略和"限界"策略两部分组成。"分支"策略体现在对问题空间是按照广度优先策略进行搜索的；"限界"策略
是为了加速搜索速度而采用启发信息剪枝的策略。

   (2) 深入
       分支搜索法是一种在问题解空间上进行搜索尝试的算法。所谓"分支"是采用广度优先的策略，依次搜索E-结点的所有分支，也就是
所有的相邻结点。和回溯法一样，在生成的结点中，抛弃那些不满足约束条件(或者说不可能导致最优可行解)的结点，其余结点加入到活结
点表。然后从表中选择下一个结点作为下一个E-结点，继续搜索。

   (3) 分类
       选择下一个E-结点的方式不同，会出现几种不同的分支搜索方式。

       1> FIFO 搜索
          先进先出(FIFO)搜索算法要依赖"队列"做基本的数据结构。一开始，根结点是唯一的活结点，根结点入队。
从活结点队列中取出根结点后，作为当前扩展结点。对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，
把所有满足约束条件的儿子加入到活结点队列中。再从活结点表中取出队首结点(队中最先进来的结点)为当前扩展结点，
......,直到找到一个解或活结点队列为空为止。

       2> LIFO搜索
          后进先出(LIFO)搜索算法要依赖"栈"做基本的数据结构。一开始，根结点入栈。从栈中弹出一个结点为当前扩展结点。对当前
扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子入栈，再从栈中弹出一个结点(栈中最后进来
的结点)为当前扩展结点，......,直到找到一个解或栈空为止。

       3> 优先队列式搜索
          为了加速搜索的进程，应采用有效的方式选择E-结点进行扩展。优先队列式搜索，对每一个结点计算一个优先级，并根据这些
优先级，从当前活结点表中优先选择一个优先级最高(最有利)的结点作为扩展结点，使得搜索朝着解空间树上最优解的分支推进，以便尽
快找到一个最优解。

2. 用FIFO分支搜索算法求解最优解

   (1) 问题描述：
       有两艘船和需要装运的n个货箱，第一艘船的载重量是c1，第二艘船的载重量是c2,wi是货箱的质量，且w1+w2+...+wn <= c1+c2.
希望确定是否有一种可将所有n个货箱全部装船的方法。若有的话，找出该方法。

   (2) 举例描述：
       当n=3，c1=c2=50，w=[10,40,40]时，可将货箱1、2装到第一艘船上，货箱3装到第二艘船上。
       但是如果w=[20,40,40]，则无法将货箱全部装船。由此可知问题可能有解，可能无解，也可能有多解。
  
   (3) 问题分析
       虽然是关于两艘船的问题，其实只讨论一艘船的最大装载问题即可。因为当第一艘船的最大装载为bestw时，
若w1+w2+...+wn-bestw <= c2，则可以确定一种解，否则问题就无解。这样的问题转化为第一艘船的最大装载问题。

   (4) 算法设计
       转化为一艘船的最优化问题后， 问题的解空间为一个子集树。也就是算法要考虑所有物品取、舍情况的组合，
n个物品的取舍组合共有2的n次方个分支。

       1> 和回溯算法的思想一样，用FIFO分支搜索所有的分支，并记录已搜索分支的最优解，搜索完子集树也就找出了问题的解。
  
       2> 要想求出最优解，必须搜索到叶结点，所以要记录数的层次。当层次为n+1时，搜索完全部叶结点，算法结束。

       3> 分支搜索过程中活结点的"层"是需要标识的，否则入队后无法识别结点所在的层。每处理完一层让"-1"入队，以此来标识
          "层"，并用变量i来记录当前层。

       4> 每个活结点要记录当前船的装载量。

3. Java代码:

package boke.branchlimit;

/**
 * 分支限界FIFO
 * 
 * @since jdk1.6
 * @author 毛正吉
 * @version 1.0
 * @date 2010.05.25
 * 
 */
public class BranchLimitFIFOSearch {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// n个货箱
		int n = 3;
		// 第一艘船的载重量
		float c1 = 50;
		// 第二艘船的载重量
		float c2 = 50;
		// 货箱质量数组
		float[] w = { 0, 10, 40, 40 };

		// 测试例子
		BranchLimitFIFOSearch bfis = new BranchLimitFIFOSearch(n, c1, c2, w);
		// 所有货箱的重量之和
		float s = bfis.getS();
		if (s <= c1 || s <= c2) {
			System.out.println("need only one ship!");
		}
		if (s > c1 + c2) {
			System.out.println("no solution!");
			return;
		}

		bfis.maxLoading(c1);

		float bestw = bfis.getBestw();

		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!");
		}

	}

	private int n; // n个货箱
	private float c1; // 第一艘船的载重量
	private float c2; // 第二艘船的载重量
	private float bestw; // 第一艘船的最大装载
	private float ew = 0; // 当前船的装载量
	private float[] w; // 货箱质量数组
	private float s = 0; // 所有货箱的重量之和
	private MyQueue mq = new MyQueue(); // FIFO队列

	/**
	 * 构造方法
	 * 
	 * @param _n
	 * @param _c1
	 * @param _c2
	 * @param _w
	 */
	public BranchLimitFIFOSearch(int _n, float _c1, float _c2, float[] _w) {
		n = _n;
		c1 = _c1;
		c2 = _c2;
		w = _w;

		for (float f : _w) {
			s += f;
		}
	}

	/**
	 * 最优装载值
	 * 
	 * @param c
	 */
	public float maxLoading(float c) {
		mq.put(new Float(-1)); // 初始化结点队列，标记分层
		int i = 1; // E-结点的层
		ew = 0; // 当前船的装载量
		bestw = 0; // 目前的最优值

		while (!mq.empty()) { // 搜索子集空间树
			if (ew + w[i] <= c) { // 检查E-结点的左孩子，货箱i是否可以装载
				addLiveNode(ew + w[i], i); // 货箱i可以装载
			}

			addLiveNode(ew, i); // 右孩子总是可行的，不装载货物i

			ew = (Float) mq.get(); // 取下一个结点

			if (ew == -1) { // 到达层的尾部
				if (mq.empty()) {
					return bestw;
				}
				mq.put(new Float(-1));
				ew = (Float) mq.get(); // 取下一个结点
				i++; // ew的层
			}
		}
		return bestw;
	}

	/**
	 * 入队
	 * 
	 * @param wt
	 * @param i
	 */
	public void addLiveNode(float wt, int i) {
		if (i == n) { // 是叶子
			if (wt > bestw) {
				bestw = wt;
			}
		} else { // 不是叶子
			mq.put(new Float(wt));
		}
	}

	public int getN() {
		return n;
	}

	public void setN(int n) {
		this.n = n;
	}

	public float getC1() {
		return c1;
	}

	public void setC1(float c1) {
		this.c1 = c1;
	}

	public float getC2() {
		return c2;
	}

	public void setC2(float c2) {
		this.c2 = c2;
	}

	public float getBestw() {
		return bestw;
	}

	public void setBestw(float bestw) {
		this.bestw = bestw;
	}

	public float getEw() {
		return ew;
	}

	public void setEw(float ew) {
		this.ew = ew;
	}

	public float getS() {
		return s;
	}

	public void setS(float s) {
		this.s = s;
	}

}

------------------------------------------

package boke.branchlimit;

import java.util.LinkedList;

/**
 * 自定义队列
 * 
 * @since jdk1.6
 * @author 毛正吉
 * @version 1.0
 * @date 2010.05.25
 * 
 */
public class MyQueue {
	private LinkedList ll = new LinkedList();

	/**
	 * 入队
	 * 
	 * @param o
	 */
	public void put(Object o) {
		ll.addLast(o);
	}

	/**
	 * 出队
	 * 
	 * @return
	 */
	public Object get() {
		return ll.removeFirst();
	}

	/**
	 * 队是否为空
	 * 
	 * @return
	 */
	public boolean empty() {
		return ll.isEmpty();
	}
}