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();
 }
}

本文链接:https://www.it72.com/1511.htm