分支定界法总结

                         分支定界法总结

分支定界法介绍：

         分支限界法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。分支限界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为限界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。这种算法一般可以求得最优解。

1.基本理论：

       1.1 分支限界算法策略

              在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所      有 儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点        中。从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或      活结点表为空时为止。

        1.2 从活结点表中选择下一个活结点作为新的扩展结点，分支限界算法通常可以分为两种形式：

1.2.1 FIFO（First In First Out）分支限界算法

        按照先进先出（FIFO）原则选择下一个活结点作为扩展结点，即从活结点表中取出结点的顺序与加入结点的顺序相同。

1.2.2 最小耗费或最大收益分支限界算法

在这种情况下，每个结点都有一个耗费或收益。

根据问题的需要，可能是要查找一个具有最小耗费的解，或者是查找一个具有最大收益的解。

        1.3 提高分支定界法的效率

               实现分支限界算法时，首先确定目标值的上下界，边搜索边减掉搜索树的某些分支，提高搜索效率。

     在搜索时，绝大部分需要用到剪枝。“剪枝”是搜索算法中优化程序的一种基本方法，需要通过设计出合理的判断         方 法，以决定某一分支的取舍。

              若我们把搜索的过程看成是对一棵树的遍历，那么剪枝就是将树中的一些“死结点”，不能到达最优解的枝           条“剪”掉，以减少搜索的时间。 

2.下面通过例题来具体的说明一下分支定界法的具体过程

       2.1 单源最短路径的问题

            给定带权有向图G＝(V，E)，其中每条边的权是非负实数。 给定V中的一个顶点，称为源。现在要计算从源        到所有其他各顶点的最短路长度，这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。（每      条边上标注有字母和数字，在字母旁边的数字为路长。）

     输入

第一行是顶点个数n，第二行是边数edge；接下来edge行是边的描述：from，to，d，表示从顶点from到顶点 to的边权是d。后面是若干查询，从顶点s到顶点t。

输出

给出所有查询，从顶点s到顶点t的最短距离。

如果从顶点s不可达到顶点t，则输出“No path!”。

输出样例：       

解题思路：

   解单源最短路径问题的优先队列式分支限界法，使用C++标准模板库的优先队列存储活结点表，其优先级是结点所对应的当前路长。

算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的儿子结点a，b，c被依次插入优先队列中。

算法从优先队列中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。

如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。

这个结点的扩展过程一直继续到活结点优先队列为空。

            单源最短路径问题分支限界算法的数据结构

        #define inf 1000000 //∞

#define NUM 100

int n; //图G的顶点数

int edge; //图G的边数

int c[NUM][NUM]; //图G的邻接矩阵

int prev[NUM]; //前驱顶点数组

int dist[NUM]; //从源顶点到各个顶点最短距离数组     

       //优先队列的元素

struct MinHeapNode {

　　//排序算法，升序

　　friend bool operator < (const MinHeapNode& a,

　　　　　　　　　　　　　　const MinHeapNode& b)

　 　{

　　　　if(a.length > b.length)　　return true;

　　　　else return false;

　 　}

　 　int i;　　　　　　　　　//结点编号

　 　int length;　　　　　　//结点路径的长度

};

   ZOJ1136-Multiple

给出一个自然数N（0～4999，包括0和4999）和M个不同的十进制数字X1，X2，…，XM（至少一个数）。

找出由数字X1，X2，…，XM构成的正整数，是N的最小倍数。

每组数据之间有一个空行，数据格式如下：

第一行：数字N

第二行：数字M

接下来M行：数字X1，X2，…，XM。

对每组测试数据，假如存在此数，则直接输出该数，占一行；否则输出0。

由数字X1, X2, …, XM构成的正整数，而且这些数字是可以重复使用的，属于可重复的全排列问题。

样例数据1：X1＝7，X2＝0，X3＝1，构成正整数110是22的倍数，而且是22的最小倍数。其中X3使用了2次，X2使用了1次。

假设构成的数字有num位，则问题解空间是：mnum。

虽然没有给定m和num的大小，显然这两个数不会太大，且N的最小倍数是正整数，结合在线测试得知，m和num不超过11。

本题只要一个最优解，最适合的方法是分支限界算法，使用广度优先搜索（BFS）来实现

数据结构

设要计算的数字是n，用于构造的数字个数是m。

使用数组存放用于构造的数字（即m个正整数）：

int a[20];

队列结点数据结构：

struct node { 

int num; //该结点构造的数字除以n的余数

string digit; //该结点构造的数字

};

队列的定义：

queue <node> q;

辅助数组r，表示下标为x的值是否在队列中：

bool r[5000] = {false};

在队列式分支限界算法中，不断从活结点队列中取出当前扩展结点cur，并产生当前结点cur的所有儿子结点。在扩展结点时，先将数字a[i]（即Xi）扩展到当前结点余 数的尾部：

如果x＝0， 0%n是无效的，该子结点不放进队列。如果x%n还没有计算过，将该子结点放入队列中，否则其计算结果保存在r[x%n]中。

对当前结点E，如果r[0]=true，表示找到了n的倍数，直接输出E.digit。

      //定义队列

queue <node> q;

//构造队列的头元素

node cur;

cur.num = 0;

cur.digit = "";

q.push(cur);

//定义辅助数组

bool r[5000] = {false};

//是否已经找到答案

bool find = false;

while ( !q.empty() )　 //搜索问题的解空间

{

　　 cur = q.front();　 //取出队列的头元素

　　q.pop();

　　//产生当前扩展结点的儿子结点

　　for(int i = 0; i < m; i++)

　　{

　　　　int x = cur.num * 10 + a[i];

　　　　if (x == 0) continue;

　　　　node E; 　 //定义一个结点

　　　　if ( !r[x%n] ) 　 //如果x%n还没有计算过

　　　　{

　　　　　　r[x%n] = true;

　　　　　　E.num = x%n;

　　 　　　　E.digit = cur.digit + char(a[i]+'0');

　　 　　 　　q.push(E);

　 　　　}

　　 　　if (r[0]) 　 //已经找到答案

　　 　　{

　　 　　　　cout << E.digit << endl; 

　　 　　　　find = true;　break;

　　　　}

　 　}

　 　if (find) break;

}

if ( !find ) cout<<0<<endl; //没有找到答案

return;

实现N的最小倍数

为了确保找到的就是N的最小倍数，我们每次从数字X1，X2，…，XM中，首先取出最小的数字构造，然后是次小的等等，这样第一个满足条件的数字就是最小的倍数。通过对 这些数字按升序排序，就可以实现。

使用C++标准模板库函数，对一维数组可以直接升序排序：

sort(a, a+m);

3.总结

         分支限界法类似于回溯法，是一种在问题的解空间树T上搜索问题解的算法。

一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。