算法设计与分析——回溯法

回溯法

简介

回溯法又称为试探法，实际上一个类似穷举的搜索尝试过程,主要是在搜索尝试过程中寻找向题的解,当发现已不满足求解条件时,就“回溯”(即回退),尝试别的路径。回溯法有“通用解题法”之称它适合于解一些 组合数 较大的最优化向题。

算法设计思想

回溯法从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。在搜索至树中任一结点时，先判断该结点对应的部分解 是否满足约束条件（约束函数），或者是否超出限界函数的界限（限界函数），也就是判断该结点是否可能包含问题的答案解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝( Pruning)；否则，进入以该结点为根的子树，继续按照深度优先策略搜索并进行判断。若用回湖法求问题的所有解时，需要回溯到根结点，且根结点的所有可行的子树都要被搜索完才结束。而若使用回湖法求任一个解时,只要搜索到向题的一个解就可以结束。

重要概念：

	 解空间：排列组合数的枚举
	 解空间树：
		 - 子集树，2的n次方个叶子节点（在集合中找某个符合条件的子集）；
		 - 排列树，Amn个叶子节点（在确定n个数中找到符合条件的排列）；

	解决：求任一解，求全部可行解，求最优解
	约束：显式约束（给定问题集合），隐式约束（目标求解条件）
	剪枝函数：
		 - 约束函数：用约束函数在扩展结点处剪除不满足约束的子树;
		 - 限界函数：用限界函数剪去得不到向题解或最优解的子树。   

子集树示例：

排列树示例：

解题步骤：

1、针对所给向题,确定问题的解空间树,问题的解空间树应至少包含问题的一个解就者最优解
2、确定结点的扩展搜索规则
3、以深度优先方式搜索解空间树,并在搜索过程中采用剪枝函数来避免无效搜索。
    其中,深度优先方式可以选择递归回溯或者迭代回溯

代码实例：

子集树参考代码，经典问题 0/1背包：
    有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？

/*0-1背包  子集树 */ 
void calV(int i,int tolw,int tolv){
    if(i>NUM){
        if (tolw <= WEIGHT && tolv > maxv) {
            maxw=tolw;
            maxv=tolv;
            System.arraycopy(x,0,res,0,x.length);
        }
        return;
    }
    if(tolw+tolW(i)>WEIGHT){ // 左剪枝 减去加上当前i小于等于WEIGHT的节点
        x[i]=0;
        calV(i+1,tolw,tolv);
    }
    if(tolw+w[i]<=WEIGHT){// 右剪枝 减去加上当前节点大于WEIGHT的节点
        x[i]=1;
        calV(i+1,tolw+w[i],tolv+v[i]);
    }
}

排列树参考代码：
    坐标中多个点，从出发点一次经过其他点然后回到出发点，要求路径最短，只能按坐标方格边走，求最短路径？

/*bool标识全遍历递归*/ 
private static void calculate(Point p, int count) {
    //判断停止条件,如果所有的点遍历完，则返回
    if (count == points.length) {
        minPath = tolLen + p.getLength(StartPoint);
    }
    //否则遍历其余的点并进行路径和的计算
    for (Point point : points) {
        //判断此点是否遍历过
        if (!point.isVisited) {
            //计算起始点到遍历点之间的距离，从而更新最小路径
            tolLen += point.getLength(p);
            //该点的标志位置为true
            point.isVisited = true;
            //若小于最小路径，则遍历此点继续下一层
            if (tolLen + point.getLength(StartPoint) < minPath) {
                //每遍历一个点，层次加1，起始点更改为遍历后的点,继续计算其余点
                calculate(point, count + 1);
            }
            //将路径和倒减，标志置为false，进行下一个方案的计算
            tolLen -= point.getLength(p);
            point.isVisited = false;
        }
    }
}

/** 排列树 实排列 上下交换递归
 * 将所有的点进行全排列，然后一次累加求tolLen，同时进行剪枝
 */
private static void calculate1(Point p,int i, int n) {
    if(i>=n){
        minPath=tolLen+p.getLength(StartPoint);
        //dispa();
        return;
    }
    // i 层的枚举
    for (int j = i; j < n; j++) {
        swap(i,j); // 交换实现排列元素不同
        tolLen+=p.getLength(points[i]); // 目标条件等处理
        if(tolLen+points[i].getLength(StartPoint)<minPath){ // 剪枝函数
            calculate1(points[i],i+1,n);
        }
        tolLen-=p.getLength(points[i]);
        swap(i,j); // 还原环境
    }
}

剪枝改进:
0/1背包问题

    左剪枝对于第层的有些结点,tw+[]已超过了M,显然再选择w[]是不合适的。如第2层的(5,4)结点,tM=5,M[2]=3,而tw+WM[2]>M,选择物品2进行扩展是不必要的,可以增加一个限界条件进行剪枝,如若选择物品i会导致超重即tw+W[i]>M,就不再扩展该结点,也就是仅仅扩展tM+W[]sM的左孩子结点。


    右剪枝用rw表示考虑第讠个物品时剩余物品的重量当不选择物品时,若tw+rw<M(注意w中包含[])时,也就是说即使选择后面的所有物品,重量也不会达到M,因此不必要再考虑扩展这样的结点,也就是说,对于右分枝仅仅扩展tw+rw>M的结点(注意不包含等于)如第2层的(0,0)结点,此时tw=8,rw=6(物品2、3、4的重量和),tw+rw=6,不大手于M(此时又不选择物品2),所以不必扩展其右孩子结点.