前言

点击查看算法介绍

五大算法

• 分治算法
• 动态规划
• 贪心算法
• 回溯算法
• 分支限界算法

WX搜素”Java长征记”对这些算法也有详细介绍。

回溯算法

一、算法概述

   回溯算法是一种择优搜索法，按照选优的条件向前搜索，以达到目标。但当探索 到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通 就退回再走的技术称之为回溯法。 

二、相关概念

一一解空间

对于一个复杂的问题的解决方案是由一个决策序列构成，所以对于这个问题的节 可以用一个解向量来表示X<x1,x2,…xn>，Xi（1≤i≤n代表对应第i步的选择，所有的取值组合构成问题的解向量空间，简称解空间又称解空间树(Because解空间一般用书的形式来组织)。

一一解空间树的两种类型

• 子集树：当所给问题是从n个元素的集合中找出满足某种性质的子集时，相应的解空间树称为子集树
• 排列数：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间称为排列树。

一一剪枝函数（搜索过程中的裁剪过程）

• 用约束条件剪除得不到的可行解的子树
• 用限界函数剪取得不到最优解的子树

【运用剪枝函数可以避免无效搜索】

一一深度优先与宽度优先

结合例子加深理解

深度优先： 说简单一点就是靠近左边的子树优先遍历，且若可一直向前走（即往深度递增的方向），走到尽头再回头。

（图例深度优先遍历结果：1→2→3→5→8→9 →6→7→4）

宽度优先： 说简单就就是从根开始遍历完每一层（从左至右）再继续下一层。

（图例宽度优先遍历结果：1→2→3→4→5→6 →7→8→9 ）

三、回溯算法的思想

• 回溯算法一般适用于搜索问题和优化问题；
• 回溯算法通过搜索解空间树，其中树的每个节点对应部分问题的解，最终会在树的叶子节点上得到可行解；
• 回溯算法的搜索过程采用系统的搜索方法隐含的去遍历树
  【解释：系统的搜索方法即就是采用深度优先或宽度优先等其他的方法
  隐含遍历是指所有的节点都会被看到，但不一定会完全访问到。因为在搜索过程中会有一个裁剪的过程】
• 对于节点的分支判断，如果满足约束条件，则分支扩张解向量；反之，回溯到该节点的父节点。

四、回溯算法的使用条件

满足多米诺性质

五、回溯算法的实现

一一回溯法的设计步骤：（参考下）

1. 定义解向量和每个分量的取值范围，解向量 为 < x1, x2, …,xn>确定 xi 的取值集合为 Xi , i =1,2,…, n.
2. 在<x1,x2,…,xk-1>确定如何计算 xk取值集合Sk, Sk ⊆ Xk
3. 确定节点儿子的排列规则
4. 判断是否满足多米诺性质
5. 确定每个节点分支的约束条件
6. 确定搜索策略: 深度优先,宽度优先等
7. 确定存储搜索路径的数据结构

一一递归实现思想

一一迭代实现

六、回溯法的经典例子

• 皇后问题
• 装载问题
• 0-1背包问题
• 图的着色

皇后问题

问题介绍（4后）

   在 4 × 4 的方格棋盘上放置4个皇后，使得没有两个皇后在同一行、同一列、也不 同一条45度的斜线上.问有多少种可能的布局？ 

解: <2,4,1,3>， < 3,1,4,2>

例-<2,4,1,3>的排列

【横行依次代表1-4皇后编号，纵行代表对应编号皇后的位置】

部分图解分析搜索过程

【说明： 每个节点都有4个儿子，分别代表选择1,2,3,4列位置】

程序：

//皇后问题 package com.company; import java.util.*; public class Queen { private static int n;//皇后的个数 private static int X[];//存放皇后位置 private static int count;//统计解的数目 public Queen(int n){ this.n=n;         X=new int[n];         System.out.print(backTrace(1)); } /*回溯法放皇后*/ public static int backTrace(int t){ if(t>n) {             System.out.println(Arrays.toString(X));             count++; } else { /*第t个婚后，遍历所有的节点（位置）*/ for(int i=1;i<=n;i++){                 X[t-1]=i;//存放t皇后的当前假设位置 if(isPutQueen(t)) { backTrace(t+1); } } } return count; } /*      *判断是否为45度，用编号差绝对值和存放位置差的绝对值作比较      * 判断是否在同一列直接比较对应位置即可      */ /*判断是否能放置皇后*/ public static boolean isPutQueen(int num){ for(int i = 1; i < num; i++) if(Math.abs(num-i)==Math.abs(X[num-1]-X[i-1])||X[num-1]==X[i-1])//约束条件 return false; return true; } public static void main(String[] args){ new Queen(4); } } 

装载问题

问题介绍

  有n个集装箱，需要装上两艘载重分别为c1和c2的轮船. wi为第 i 个集装箱的重 量，且 w1+w2+...+wn ≤ c1+ c2问：是否存在一种合理的装载方案把这 n 个集装箱 装上船？如果有，请给出一种方案. 

问题分析

输入: W=<w1,w2, …, wn>为集装箱重量c1和c2为船的最大载重量
思想：令第一艘船的装入量为W1,
用回溯算法求得c1−W1达到最小的装载方案.判断是否满足w1+w2+…+wn−W1≤ c2
解空间：0-1取值二叉树，为子集树

伪码

实例
W = < 90,80,40,30,20,12,10 > c1=152, c2=130

部分图解分析

• 程序一：【与伪码对应】

//装载问题 package com.company; import java.util.Arrays; public class Loading { private static int W[]={90,80,40,30,20,12,10}; private static int X[]=new int[W.length+1];//记录可行解 private static int bestX[]=new int[W.length];//记录最优解 private static int c1=152,b=152,best=152; //c1为轮船最大容量，b为当前轮船剩余装载量，best为最优剩余装载量 private static int i=1; /*深度遍历装载*/ public static void loading() { while( i < W.length) { if (W[i-1] <= b) {                 X[i] = 1;                 b = b - W[i-1];                 i++; } else {                 X[i] = 0;                 i++; } } if (b < best) {             best = b; for (int j = 0; j < bestX.length; j++)                 bestX[j] = X[j + 1]; } backTrack(); if(i==1) return ; loading(); } /*回溯*/ public static void backTrack(){ while (i > 1 && X[i] == 0)             i--; if (X[i] == 1) {             X[i]=0;             b += W[i-1];             i++; } } public static void main(String[] args) { loading();         System.out.println("最优解为："+Arrays.toString(bestX) +"n最大装载量为："+(c1-best)); } } 

程序二：【该实现方法不用排序】

//装载问题 package com.company; public class Loading { private static int w[]={90,80,40,30,20,12,10}; private static int n=w.length;//集装箱个数 private static int c=152;//第一艘轮船的载重量 private static int cw;//当前载重量 private static int r;//剩余集装箱重量 private static int bestW;//当前最优载重量 private static int[] x=new int[w.length];//当前解 private static int[] bestX=new int[w.length];//当前最优解 public static void main(String[] args){ loading(); } public static void loading() { for (int i = 0; i < n; i++)             r += w[i];//期初剩余集装箱的重量是所有集装箱重量和 backTrace(0); for (int i = 0; i < n; i++)             System.out.print(bestX[i] + " ");         System.out.println("最优解：" + bestW); } public static void backTrace(int i) { //1.到达叶节点 if (i > n-1) { //i此时的值=叶节点+1 if (cw > bestW) { for (int j = 0; j < n; j++) {                     bestX[j] = x[j];                     bestW = cw; } return; } }         r -= w[i]; //2.搜索左子树 if (cw + w[i] <= c) { //x[i] =1             x[i] = 1;             cw += w[i]; backTrace(i + 1);             cw -= w[i]; } //3.搜索右子树 if (cw + r > bestW) {             x[i] = 0; backTrace(i + 1); }         r += w[i]; } } 

时间复杂度：

W(n)=O(2n)

0-1背包问题

问题介绍【类似于装载问题】

   有n种物品，每种物品只有 1个. 第i 种物品价值为 vi , 重量为 wi , i =1,2,…, n.  问如何选择放入背包的物品，使得总重量不超过 B, 而价值达到最大？ 

问题分析

解：n维0-1向量<x1, x2, …, xn>， xi =1/0⇔物品 i (不)选入背包
搜索空间：0-1取值的二叉树, 称为子集树，有2^n片树叶.

实例:
V={12,11,9,8}, W={8,6,4,3}, B=13

图解分析

程序

package com.company; import java.util.Arrays; public class Package { private static int weight[] = {8, 6, 4, 3}; private static int value[] = {12, 11, 9, 8}; //bestValue保存最优价值，curValue、curWeight分别为当前价值和重量 private static int b = 13, bestValue, curValue, curWeight; private static int X[] = new int[weight.length];//记录解 private static int bestX[] = X;//记录最优解 private static int v;//当前剩余价值 public static void main(String[] args){ for(int i=0;i<value.length;i++)             v+=value[i]; packageTraceBack(0);         System.out.println(Arrays.toString(bestX)+bestValue); } public static void packageTraceBack(int t) { /*到达叶节点*/ if (t > weight.length - 1) { /*更新最优解*/ if (bestValue < curValue) {                 bestValue = curValue; for (int i = 0; i < weight.length; i++)                     bestX[i] = X[i]; return; } }         v-=value[t]; /*搜索左子树*/ if (curWeight + weight[t] <= b) {             X[t] = 1;             curWeight += weight[t];             curValue += value[t]; packageTraceBack(t + 1);             curWeight -= weight[t];             curValue -=value[t]; } /*搜索右子树*/ if(curValue + v > bestValue) {              X[t] = 0; packageTraceBack(t + 1); }         v+=value[t]; } } 

图的着色

问题介绍

   无向连通图 G和 m 种颜色的集合用这些颜色给图的顶点着色，每个顶点一种颜色.  要求是：G 的每条边的两个顶点着不同颜色. 

问题分析

解向量：<x1, x2, …, xn>， x1, x2, …, xn∈{1,2, …, m }
搜索树：m叉树
搜索策略：深度优先

实例分析：

部分图解

程序

//图的着色 package com.company; public class Coloring { private static int vertex[][]={{0,1,0,0,0,1,1}, {1,0,3,1,1,0,1}, {0,1,0,1,0,0,1}, {0,0,1,0,1,1,0}, {0,0,0,1,0,1,0}, {1,0,0,1,1,0,1}, {1,1,1,0,0,1,0}};//图的邻接矩阵表示 private static int n=vertex[1].length;//图的顶点数 private static int m=3;//颜色数，分别用1、2、3代表不同的颜色 private static int x[]= {0,0,0,0,0,0,0},sum=0;//记录可行解和解的个数 public static void main(String[] args){ backTrace(0); } /*判断是否能着色*/ public static boolean isOK(int t) { for(int i=0;i<t;i++) if(vertex[t][i]==1 && x[i]==x[t]) return false; return true; } /*回溯图色*/ public static void backTrace(int t) { if(t>n-1)//到达叶子节点 {             sum++;             System.out.println("第"+sum+"种方案: "); for(int i=0;i<n;i++)                 System.out.print(x[i]+" ");             System.out.println(); return; } for(int i=1;i<=m;i++) {             x[t]=i; if(isOK(t)) backTrace(t+1); } } } 

时间复杂度分析

时间复杂度为：O(nmn)

改进：

高中应该也做过这种概率统计题，不难看出他的对称性，例如上面这个实例，不难分析出它有6种方案，我们只需求出其中1/6即可，后面的通过对称就可得到。这样一来就缩小了时间复杂度。

也可以根据结合图的邻接特点裁掉部分搜索过程，例1、2、3顶点已经涂了三种不同的色，那么7就不能满足要求，所以就可以裁去对应的搜索子树。但是这样就需要增加一个判定工作量。具体问题具体在分析，看哪种方案最优。

干货

想学习更多的关于Java基础、算法、数据结构等编程知识的WX搜索”Java长征记“。上面的这些在里面也有详细介绍。