第六章回溯算法

回溯算法的理论基础 以深度优先的方式系统地搜索问题的解的方法称为回溯法。 可以系统地搜索一个问题的所有解或任意解。 有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。 回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法 空间特性 （完全）二叉树. 问题的解是一棵子树（一条路） 通过深度优先搜索获得最优解 回溯法的基本思想 在生成解空间树时，定义以下几个相关概念： 活结点： 如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。 扩展结点： 当前正在生成其儿子结点的活结点叫扩展结点（正扩展的结点）。 死结点： 不能再进一步扩展或者其儿子结点已全部生成的结点就是死结点。 回溯从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。 开始结点(根结点)成为第一个活结点，同时成为当前的扩展结点。 在当前的扩展结点，搜索向深度方向进入一个新的结点。这个新结点成为一个新的活结点，并成为当前的扩展结点。 若在当前扩展结点处不能再向深度方向移动，则当前的扩展结点成为死结点，即该活结点成为死结点。 此时回溯到最近的一个活结点处，并使得这个活结点成为当前的扩展结点。 回溯法以这样的方式递归搜索整个解空间（树），直至满足中止条件 旅行商问题 TSP问题(Traveling Salesman Problem)通常称为旅行商问题，也称为旅行售货员问题、货担郎问题等，是组合优化中的著名难题，也是计算复杂性理论、图论、运筹学、最优化理论等领域中的一个经典问题，具有广泛的应用背景。

问题的一般描述为：旅行商从n个城市中的某一城市出发，经过每个城市仅有一次，最后回到原出发点，在所有可能的路径中求出路径长度最短的一条。 子集树与排列树 有时问题是要从一个集合的所有子集中搜索一个集合，作为问题的解。或者从一个集合的排列中搜索一个排列，作为问题的解。 回溯算法可以很方便地遍历一个集合的所有子集或者所有排列。 当问题是要计算n个元素的子集，以便达到某种优化目标时，可以把这个解空间组织成一棵子集树。 例如，n个物品的0-1背包问题相应的解空间树就是一棵子集树。 这类子集树通常有2n个叶结点，结点总数为2n +1-1。 遍历子集树的任何算法，其计算时间复杂度都是Ω(2n)。

void backtrack (int t){ //形参t为树的深度，根为1 　　if (t>n) update(x); //扩展到叶子结点，得到了一组解决方案 　　else 　　　　for (int i=0; i<=1; i++)　　//每个结点只有两个子树 　　　　{ 　　　　　　x[t]=i;　　　 //即0/1，表示第 t个元素是否是可选元素 　　　　　　if (constraint(t) && bound(t)) //判断当前结点是否是扩展结点 backtrack(t+1); //对当前结点按照深度优先搜索的方式进行扩展 　　　　} }

回溯算法搜索排列树的伪代码

//形参t为树的深度，根为1 void backtrack (int t){ 　　if (t>n) update(x); //得到了一个全排列，对排列结果进行更新 　　else 　　　　for (int i=t; i<=n; i++)　　　　{ 　　　　　　//为了保证排列中每个元素不同，通过交换 来实现 　　　　　　swap(x[t], x[i]); 　　　　　　if (constraint(t) && bound(t)) backtrack(t+1); 　　　　　　swap(x[t], x[i]);　　　　//恢复状态 　　　　} }

**素数环:从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。 **

#include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> using namespace std; bool b[21]={0}; //判断i是否出现在素数环中 int total=0,a[21]={0}; //a记录素数环中的每一个数 int search(int t); //回溯过程。形参表示素数环中的数的编号 int print(); //输出方案 bool pd(int,int); //判断素数

装载问题 给定n个集装箱要装上一艘载重量为c的轮船，其中集装箱i的重量为wi。集装箱装载问题要求确定在不超过轮船载重量的前提下，将尽可能多的集装箱装上轮船（贪心算法中的装载问题讨论的是装载件数；本题讨论的是最大装载重量。）

#include <iostream> using namespace std; class goods{ int weight; public: goods(int w=0):weight(w) {} int get_w(){ return weight; } void set(int w){ weight=w; } }; //goods *g,集装箱列表 //int *best,待求解的最优装载方案 //int t,子集树数的层号。根节点在第0层，叶节点在第n层 //int n,集装箱的总数 //int &cw, 当前的轮船的荷载 //int bestcw ,当前的最大荷载 //int *x,满足当前最大荷载的装载方案 //int r剩余的集装箱重量和 void load(goods *g, int *x, int t, int n,int cw, int &bestcw ,int *best,int r,int c){ if(t>n) { //已经遍历的到叶子结点，得到了一个解决方案 if(cw>bestcw) { for(int i=0;i<n;i++) best[i]=x[i]; bestcw=cw; } }

剩余集装箱的重量r初始化

int main(){ int n,c,bestcw=0; int *x,*best, r=0; cout<<“请输入物品的件数和轮船的装载重量："; cin>>n>>c; goods *g; g=new goods[n]; x=new int [n]; best=new int[n]; cout<<"请输入每件物品的重量："; for(int i=0;i<n;i++) { int w; cin>>w; g[i].set(w);r=r+w; } load(g,x,0,n,0,bestcw,best,r,c); cout<<bestcw<<endl; for(i=0;i<n;i++) cout<<best[i]<<" "; cout<<endl; return 0; }

0－1背包问题 给定一个物品集合s＝｛1，2，3，…，n｝，物品i的重量是wi，其价值是vi，背包的容量为W，即最大载重量不超过W。在限定的总重量W内，我们如何选择物品，才能使得物品的总价值最大。

#define NUM 100 int c; //背包的容量 int n; //物品的数量 int cw; //当前重量 int cv; //当前价值 int bestv; //当前最优价值 //描述每个物品的数据结构 struct Object{ int w; //物品的重量 int v; //物品的价值 double d; //物品的单位重量价值比 }Q[NUM];

图的m着色问题 给定无向连通图G=(V, E)和m种不同的颜色，用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中相邻的两个顶点有不同的颜色?

数据结构

#define NUM 100 int n; //图的顶点数量 int m; //可用颜色数量 int a[NUM][NUM]; //图的邻接矩阵 int x[NUM]; //当前的解向量 int sum ;

实现

void BackTrack(int t ){ 　　int i; 　　//到达叶子结点，获得一个着色方案 　　if( t > n )　　{ 　　　　sum ++ ; 　　　　for(i=1; i<=n ;i++) 　　　　　　printf("%d ",x[i]); 　　　　printf("\n"); 　　} 　　else 　//搜索当前扩展结点的m个孩子 　　　　for(i=1; i<=m; i++ ){//尝试每种颜色 　　　　　　x[t] = i; 　　　　　　if( Same(t) ) //判断t 和其邻接点的着色方法是否相同 　BackTrack(t+1); 　　　　　　x[t] = 0;//回溯的需要，恢复到未着色的状态 　　　　} }

n皇后问题 在n×n格的棋盘上放置彼此不受攻击的n个皇后。 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n皇后问题等价于在n×n格的棋盘上放置n个皇后，任何两个皇后不放在同一行或同一列或同一斜线上。 编程要求：找出一个n×n格的棋盘上放置n个皇后并使其不能互相攻击的所有方案。 数据结构

#define NUM 20 int n; //棋盘的大小 int x[NUM]; //解向量 int sum;

实现

void Backtrack(int t) {//形参t是回溯的深度，从1开始 　　int i; 　　//到达叶子结点，获得一个可行方案。累计总数，并输出该方案 　　if (t>n) { 　　　　sum++; //是全局变量 　　　　for (i=1; i<=n; i++) 　　　　　　printf(" %d", x[i]); 　　　　printf("\n"); 　　} 　　else 　　　　for (i=1; i<=n; i++) { 　　　　　　x[t] = i; 　　　　　　if (Place(t)) Backtrack(t+1); 　　　　} }

旅行商问题 是指一销售商从n个城市中的某一城市出发，不重复地走完其余n-1个城市并回到原出发点，在所有可能的路径中求出路径长度最短的一条。本题假定该旅行商从第1个城市出发。 输入 数据结构

#define NUM 100 int n; //图G的顶点数量 int m; //图G的边数 int a[NUM][NUM]; //图G的邻接矩阵 int x[NUM]; //当前解 int bestx[NUM]; //当前最优解向量 int cc; //当前费用 int bestc; //当前最优值 int NoEdge = -1;

实现

//形参t是回溯的深度，从2开始。根结点为第1层。城市编号从1开始.从第1个城市出发 void Backtrack(int t){ 　　//到达叶子结点的父结点。旅行路径上的倒数第二个城市。最后一个城市是出发点 　　if(t==n)　　{ 　　　　if(a[x[n-1]][x[n]]!= NoEdge && a[x[n]][1]!= NoEdge && 　　　　　　(cc + a[x[n-1]][x[n]]+a[x[n]][1]<bestc||bestc== NoEdge)) 　　　　{ 　　　　　　for(int i=1; i<=n; i++) 　　　　　　　　bestx[i] = x[i]; 　　　　　　bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1]; 　　　　} 　　　　return; 　　} 　else { 　　　　for(int i=t; i<=n; i++) 　　　　{ 　　　　　　if(a[x[t-1]][x[i]]!= NoEdge && 　　　　　　　　(cc + a[x[t-1]][x[i]]< bestc||bestc == NoEdge)) 　　　　　　{ 　　　　　　　　swap(x[t],x[i]); // 先交换。此时，X[t]的值发变化。 　　　　　　　　cc += a[x[t-1]][x[t]]; //再计算。不能交换顺序。 　　　　　　　　Backtrack(t+1); // 如果要改变顺序，应该为cc += a[x[t-1]][x[i]]。 　　　　　　　　cc -= a[x[t-1]][x[t]]; 　　　　　　　　swap(x[t],x[i]); 　　　　　　} 　　　　} 　　} }

（流水）批处理作业调度问题 给定n个作业的集合j＝{j1，j2，…，jn}。 每一个作业ji都有两道工序，分别在两台机器上完成。一台机器一次只能处理一道工序，并且工序一旦开始，就必须进行下去直到完成。 每一个作业必须先由机器1处理，然后由机器2处理。 作业ji需要机器j的处理时间为t[i][j]，其中i＝ 1, 2, …, n ，j＝1, 2。对于一个确定的作业调度，设f[i][j]是作业i在机器j上的完成处理的时间（等待时间+处理时间），所有作业在机器2上完成处理的时间之和定义如下：

称为该作业调度的完成时间之和。 由于只有两台机器，作业的处理顺序极大地影响结束时间f。流水作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和(等待服务时间)达到最小。

#include <iostream> using namespace std; class jobs{ int m1,m2;//每到工序所需要的时间 int index; //作业的编号 public: jobs(int a=0, int b=0):m1(a),m2(b){} int get_m1(){ return m1; } int get_m2(){ return m2; } void set(int a, int b ){ m1=a; m2=b; } };

子集和问题 子集和问题的一个实例为＜S，c＞。其中，S＝{w1, w2, …, wn}是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得S1的和为c。 编程任务：对于给定的正整数集合S＝{w1, w2, …, wn}和正整数c，编程计算S的一个子集S1，使得S1的和为c 数据结构

#include <iostream> using namespace std; class Sum { int n; //集合中数据的个数 int *x;//解向量，当x[i]=1表示第i 个元素属于子集，否则，x[i]=0; int c;//输入的条件 int s;//正在构造的子集中元素的和 int *set;//集合 int r;//不再子集中的其他数据元素之和； int total;//记录符合条件的子集的个数 public: Sum(int n=0,int c=0); void calculate(int t); void display(); int get_T(){ return total; } };

实现

void Sum::calculate(int t){ if(t>n ){ if(c==s){ display(); total++;} } else{ r=r-set[t]; if(s+set[t]<=c){ //约束规则 x[t]=1; s=s+set[t]; calculate(t+1); s=s-set[t]; x[t]=0; } if(s+r>=c) //限界规则 calculate(t+1); r=r+set[t]; } } int main() { int n,c; cout<<"输入n 和c 的值："; cin>>n>>c; Sum s(n,c); s.calculate(1); if(s.get_T()==0) cout<<"NO Solution!!"<<endl; else cout<<s.get_T()<<endl; return 0; }

计算右边表达式值的算法

int compute() { 　　int sum = bracket(); 　　//右边第一个数 　　//对每一个运算符进行计算 　　while (b[bpos] == MUL || b[bpos] == ADD || b[bpos] == SUB) { 　　　　int operation = b[bpos++];　　　　//取出运算符 　　　　int ret = bracket();　　　　　　　　//取出下一个数 　　　　//根据运算符进行计算 　　　　switch　　(operation){ 　　　　case MUL: sum *= ret; break; 　　　　case ADD: sum += ret; break; 　　　　case SUB: sum -= ret; break; 　　　　} 　　} 　　return sum; }