XX大学
算法实践与创新论文
题目 回溯法的分析与应用
学生姓名：
学号：
摘要
对于计算机科学来说，算法的概念是至关重要的，算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。为了更加的了解算法，本篇论文中，我们先研究一个算法---回溯法。
回溯法是一种常用的重要的基本设计方法。它的基本做法是在可能的范围之内搜索，适于解一些组合数相当大的问题。圆排列描述的是在给定n个大小不等的圆 C1,C2,„,Cn,现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。图着色问题用数学定义就是给定一个无向图G=（V, E），其中V为顶点集合，E为边集合，图着色问题即为将V分为K个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的K值。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。
在本篇论文中，我们将运用回溯法来解决着图的着色问题，符号三角形问题，图排列问题，将此三个问题进行深入的探讨。
关键词:
回溯法
图的着色问题
符号三角形问题
图排列问题
I
目录
第1章 引言 1
第2章
回溯法的背景 2
第3章 图的着色问题 4
3.1
问题描述 4
3.2
四色猜想 4
3.3
算法设计 5
3.4
源代码 6
3.5
运行结果图 10
第4章
符号三角形问题 11
4.1
问题描述 11
4.2
算法设计 11
4.3
源代码 12
4.4
运行结果图 16
第5章
圆的排列问题 17
5.1
问题描述 17
5.2
问题分析 17
5.3
源代码 18
5.4
运行结果图 22
结论 23
参考文献 24
II
第1章 引言
在现实世界中，有相当一类问题试求问题的全部解或求问题的最优解。最基本的方法是通过枚举法搜索问题的解空间。但许多问题解空间的大小随问题规模n的增长呈指数规律增长，这就使问题理论上可解而实际不可行。为了使搜索空间减少到尽可能小，就需要采用良好的搜索技术。回溯法就是一种较好的搜索技术。
回溯法又称为试探法，它是一种有效的试探回溯搜索技术。即运用回溯法求解问题不是基于某种确定的法则，而是通过大量反复的试探和回溯。它的基本做法是搜索，能避免不必要搜素的穷举式搜索。回溯法在问题的解空间树中按深度优先策略，从根结点出发搜索解空间树，算法搜索至解空间树的任意一点时，先判断该节点是否包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。简单地说，采用回溯法求解问题的整个过程贯穿了搜索---试探—决定回溯或前进这三种基本运算。
通过运用回溯法，可以解决很多问题，譬如我们所熟知的“八皇后问题”，“0/1背包问题”，这只是在教学阶段中的运用，在实际运用中也产生很大的作用在学习过程中，我们会遇到这样的问题，让我们去寻找给定问题的解集或者让我们找出满足某些约束条件的最优解，这时候我们就可以采用回溯法来解决这一类的问题。通过运用回溯法，可以解决很多问题，譬如我们所熟知的“八皇后问题”，“0/1背包问题”，这只是在教学阶段中的运用，在实际运用中也产生很大的作用回溯法的优点是容易理解，可行性比较强。[1] 原福永算法设计与分析.机械工业出版社，1998；P213-214
第2章
回溯法的背景
回溯法是一种穷举类型的算法，与其说它是一种算法，倒不如说它是一种试法。回溯法并没有什么高深的算法思想，虽然名字起的很高规格，但其实它的算法性连二分查找都比不上。这里说的算法性其实就是指技巧性，对问题特性了解越深入，越能创造出很巧妙的算法，在时间复杂度的级别上提高算法效率。这体现了算法效率与适用性之间的矛盾，二分查找效率很高，但适用性比较低，类似的还有著名的KMP算法。而穷举法效率最低，但几乎适用于所有问题。。回溯法是一种试探性算法，从这一点上看，它很像穷举法。但它终究不是穷举法，回溯法是有组织的进行穷举，在试探过程中不断通过题设要求减少搜索空间，而这种减少不是一个一个解的减少，而是对搜索空间进行大规模剪枝，从而使得实际搜索空间远远小于问题的解空间，所以回溯法的实际运行效率还是比较高的。回溯法的应用背景说大很大，说小很小。算法大都在“不得不”的情况 下才会使用，如果有别的算法，那它很有可能比回溯法高效，别忘了，回溯法是基于穷举的。回溯法适用于解排列组合类问题，也就是说目标解是从一个候选空间中选择出来的。从数量级上考虑，设候选空间的大小为n，如果选择是可重复的，那生成的搜索树为完全n叉树，搜索空间为n^n（如0-1背包问题，生成的解空间为高度为n完全二叉树，其中n为物体个数）。如果选择不能重复，那生成的解空间为n!(如TSP问题生成的解空间为n!,其中n为城市个数)。也就是说，当我们通过分析发现问题的解空间为n^n或者n!时，那很可能要用到我们的回溯法了。要用回溯法解决问题，那首先要确定问题的状态空间树。这个并不是很难，就看每一步选择有多少个可选值就可以了，第一步有8个可选值，那树第一层就有8个节点，第二步有5个可选值，那第一层每个节点都有5个分支，则第二层有8×5=40个节点，以此类推……到第n层一共有m1×m2×……×mn个节点，其中mi为第i步的可选值的个数。[2] 王晓东.计算机算法设计与分析.电子工业出版社，2012；P53-54
确定了状态空间树，那下一步就是搜索了。这时候就体现出回溯法的优势了，前面不是说了嘛，回溯法的特点就是有规律、有组织的进行搜索，那下面就来看一下回溯法是如何进行搜索的：在开始搜索之前，我们先来说一下我们要做的事情，我们要得到一个解向量solution，每个分量对应每一步选择的结果，显然这个解向量的长度应该为n（我们采用c语言的标准，下标范围为0到n-1）。好了，现在我们有了一个状态空间树（逻辑上的，并不用实现）和一个解向量（物理上的，要用来装数据的）。现在可以开始搜
索了，先设定一个下标r，这个r就是解向量的下标，也用于标识状态树的第r行。先做第一步，令r=0，选solution[0]，也就是从树的第0行选择一个值放入solution[0]，显然刚开始我们应该选择第一个，即前面提到的8个里面的第一个。然后看这个半成品解向量是否是可行的，也就是说看看刚才选择的那个值是否满足要求，加入那个值不满足要求，那应该选择第二个，以此类推直到选择一个可行的值，放入solution[0]。然后r++进行第二步，选择solution[1]，同样的，我们应该从树的第二行中选择第一个看构成的解是否可行（此时解向量中包含两个元素），这样的步骤一直进行下去，直到出现这样的情况[3] 毛静华，刘丽红.基于回溯法的案例推理方法研究.《情报杂志》,2015；P40-41
（1）r=n-1了，也就是说我们得到了问题的一个可行解，这时候就要看题设要求了，如果只要求找到一个可行解，那此时算法就可以停止了。
（2）某一层的候选值选完了，我们知道，没一层的候选值都有一定个数，如上面提到的例子中第二层只有5个候选值，如果这五个候选值都试探完了还是没有可行解那该怎么办呢？这里体现的思想就是我们回溯法名字的由来，回溯。也就是令r--退回去，从新选择上面的解。比如上面的例子先选择8个中的第一个作为解的一部分，然后发现后面的5个和前面这个都不能组成可行解，那这就说明前面那个选择是不可行的，和后面是不搭配的。所以应该返回去选择8个中的第二个，然后再对5个进行选择，看哪个与这个第二个想匹配。
（3）最后一种情况，因为我们这个过程中有回溯过程，即r--的过程，那可能最后r小于0了，这说明整个树都搜索完了，也就是问题没有可行解。
回溯法一般有两种代码实现方案，递归方法和非递归方法。相比之下，递归设计方法比较简单，用前面提到的r作为递归变量即可，如果满足搜索条件，则递归调用r+1对应函数，如果不满足，则递归调用r-1对应的函数。基础步为当r＜0或r=n-1分别对应无解和得到可行解，这个就不多说了。非递归方法，也就是循环方法设计细节比较多，但只要掌握了其特点，对不同问题的适用性很强（即代码只通过很少的修改就可以应用到不同问题），加之其效率高于递归算法（循环的优势），所以这里我们着重讲一下回溯的非递归代码实现。
第3章 图的着色问题
3.1
问题描述
给定一个无向连通图G和m>0种颜色，在只准使用者m中颜色对G的结点重色的情况下，是否能使途中任何相邻的两个结点都具有不同的颜色吗?
3.2
四色猜想
四色问题是m图着色问题的一个特例，根据四色原理，证明平面或球面上的任何地图的所有区域都至多可用四种、颜色来着色，并使任何两个有一段公共边界的相邻区域没有相同的颜色。
这个问题可转换成对一平面图的４－着色判定问题(平面图是一个能画于平面上而边无任何交叉的图)。将地图的每个区域变成一个结点，若两个区域相邻，则相应的结点用一条边连接起来。
4
3
5
2
1
1
2
3
4
5
多年来，虽然已证明用5种颜色足以对任一幅地图着色，但是一直找不到一定要求多于4种颜色的地图。直到1976年这个问题才由爱普尔，黑肯和考西利用电子计算机的帮助得以解决。他们证明了4种颜色足以对任何地图着色。[4] 冯俊.算法与程序设计基础教程.清华大学出版社，2010；P252-256
图
图3-1
3.3
算法设计
考虑所有的图，讨论在至多使用m种颜色的情况下，可对一给定的图着色的所有不同方法。通过回溯的方法，不断的为每一个节点着色，在前面n-1个节点都合法的着色之后，开始对第n个节点进行着色，这时候枚举可用的m个颜色，通过和第n个节点相邻的节点的颜色，来判断这个颜色是否合法，如果找到那么一种颜色使得第n个节点能够着色，那么说明m种颜色的方案是可行的。
用m种颜色为无向图G=(V,E)着色，其中，V的顶点个数为n，可以用一个n元组x=(x1,x2,…,xn)来描述图的一种可能着色，其中，xi∈{1, 2, …, m}，(1≤i≤n)表示赋予顶点i的颜色。例如，5元组(1, 2, 2, 3, 1)表示对具有5个顶点的无向图（a）的一种着色，顶点A着颜色1，顶点B着颜色2，顶点C着颜色2，如此等等。
如果在n元组X中，所有相邻顶点都不会着相同颜色，就称此n元组为可行解，否则为无效解。容易看出，每个顶点可着颜色有m种选择，n个顶点就有mn种不同的着色方案，问题的解空间是一棵高度为n的完全m叉树，这里树高度的定义为从根节点到叶子节点的路径的长度。每个分支结点，都有m个儿子结点。最底层有mn个叶子结点。
图3-2
3.4
源代码
#include <iostream>
#include <fstream>
using namespace std;
const int N = 5;
const int M = 3;
ifstream fin(“5d8.txt“);
class Color
{
friend int mColoring(int, int, int **);
private:
bool Ok(int k);
void Backtrack(int t);
int n,
m,
**a,
*x;
long sum;
};
int mColoring(int n,int m,int **a);
int main()
{
int **a = new int *[N+1];
for(int i=1;i<=N;i++)
{
a[i] = new int[N+1];
}
cout<<“图G的邻接矩阵为:“<<endl;
for(int i=1; i<=N; i++)
{
for(int j=1; j<=N; j++)
{
fin>>a[i][j];
cout<<a[i][j]<<“ “;
}
cout<<endl;
}
cout<<“图G的着色方案如下：“<<endl;
cout<<“当m=“<<M<<“时，图G的可行着色方案数目为：“<<mColoring(N,M,a)<<endl;
for(int i=1;i<=N;i++)
{
delete[] a[i];
}
delete []a;
}
void Color::Backtrack(int t)
{
if (t>n)
{
sum++;
for (int i=1; i<=n; i++)
cout << x[i] << “ “;
cout << endl;
}
else
{
for (int i=1;i<=m;i++) {
x[t]=i;
if (Ok(t)) Backtrack(t+1);
}
}
}
bool Color::Ok(int k)
{
for (int j=1;j<=n;j++)
{
if ((a[k][j]==1)&&(x[j]==x[k]))
{
return false;
}
}
return true;
}
int mColoring(int n,int m,int **a)
{
Color X;
X.n = n;
X.m = m;
X.a = a;
X.sum = 0;
int *p = new int[n+1];
for(int i=0; i<=n; i++)
{
p[i] = 0;
}
X.x = p;
X.Backtrack(1);
delete []p;
return X.sum;
}
图m可着色问题的解空间树中内结点个数是。对于每一个内结点，在最坏情况下，用ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn)。因此，回溯法总的时间耗费是：
3.5
运行结果图
图3-3
第4章
符号三角形问题
4.1
问题描述
下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“-”。
+ + - + - + +
+ - - - - +
- + + + -
- + + -
- + -
- -
+
图4-1
在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数同。[5] 冯学军，石冰.算法设计与分析.安庆师范学院学报，2012年第18卷；P23-32
4.2
算法设计
符号三角形问题用n元组[1:n]表示符号三角形的第一行的n个字符。X[i]=1表示第一行第i个符号为“+”，X[i]=0表示第一行第i个符号为“-”；1<=i<=n。由于X[i]是2值的，所以在用回溯法解符号三角形问题时，可以用完全二叉树来表示其解空间。可行性约束函数，当前符号三角形所包含的“+”个数与“-”个数均不超过n*（n+1）/4。
在算法中递归方法backtrack（1）实现对整个解空间的回溯搜索。Backtrack（i）搜索整个解空间中第i层子树。类Triangles的数据成员记录解空间中间点信息，以减
少传给backtrack的参数。Sum记录当前已找到的“+”的个数与“-”个数相同的符号三角形数。
在算法backtrack中，当i>n时，算法搜索至叶节点，得到一个新的“+”个数与“-”个数相同的符号三角形，当前已找到的符号三角形数sum增1。
当I<=n时，当前扩展节点Z是解空间中的内部结点。该结点有X[i]=1和X[i]=0两个儿子结点。对当前扩展结点Z的每一个儿子结点，计算其相应的符号三角形中的“+”个数count与“-”个数，并以深度优先的方式递归的对可行子树搜索，或减去不可行子树。[6] 未知.计算机算法设计与分析.百度文库，2011；
无解的判断，n*(n+1)/2为奇数。
4.3
源代码
#include <iostream>
using namespace std;
class Triangle
{
friend int Compute(int);
private:
void Backtrack(int i);
int n,
half,
count,
**p;
long sum;
};
int Compute(int n);
int main()
{
for(int n=1;n<=10;n++)
{
cout<<“n=“<<n<<“时，共有“<<Compute(n);
cout<<“个不同的符号三角形。“<<endl;
}
return 0;
}
void Triangle::Backtrack(int t)
{
if ((count>half)||(t*(t-1)/2-count>half))
{
return;
}
if (t>n)
{
sum++;
}
else
{
for (int i=0;i<2;i++)
{
p[1][t]=i;
count+=i;
for(int j=2;j<=t;j++)
{
p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];
count+=p[j][t-j+1];
}
Backtrack(t+1);
for (int j=2;j<=t;j++)
{
count-=p[j][t-j+1];
}
count-=i;
}
}
}
int Compute(int n)
{
Triangle X;
X.n=n;
X.count=0;
X.sum=0;
X.half=n*(n+1)/2;
if(X.half%2==1)return 0;
X.half=X.half/2;
int**p=new int*[n+1];
for(int i=0;i<=n;i++)
{
p[i]=new int[n+1];
}
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
p[i][j]=0;
}
}
X.p=p;
X.Backtrack(1);
for(int i=0;i<=n;i++)
{
delete []p[i];
}
delete []p;
p=0;
return X.sum;
}
计算可行性约束需要O(n)时间，在最坏情况下有 O(2^n)个结点需要计算可行性约束，故解符号三角形问题的回溯算法所需的计算时间为 O(n2^n)。
4.4
运行结果图
图4-2
第5章
圆的排列问题
5.1
问题描述
给定n个大小不等的圆c1,c2,…,cn，现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如，当n=3，且所给的3个圆的半径分别为1，1，2时，这3个圆的最小长度的圆排列如图所示。其最小长度为 2+4。[7] 杨金勇等. 圆排列包装问题最优解解析.华侨大学学报，2013年2期；P58-62
图4-1
2+√4
5.2
问题分析
圆排列问题的解空间是一棵排列树。按照回溯法搜索排列树的算法框架，设开始时a=[r1,r2,……rn]是所给的n个元的半径，则相应的排列树由a[1:n]的所有排列构成。
解圆排列问题的回溯算法中，CirclePerm(n,a)返回找到的最小的圆排列长度。初始时，数组a是输入的n个圆的半径，计算结束后返回相应于最优解的圆排列。
center计算圆在当前圆排列中的横坐标，由x^2= sqrt((r1+r2)^2-(r1-r2)^2)推导出x = 2*sqrt(r1*r2)。
Compoute计算当前圆排列的长度。变量min记录当前最小圆排列长度。数组r表示当前圆排列。数组x则记录当前圆排列中各圆的圆心横坐标。
在递归算法Backtrack中，当i>n时，算法搜索至叶节点，得到新的圆排列方案。此时算法调用Compute计算当前圆排列的长度，适时更新当前最优值。
当i<n时，当前扩展节点位于排列树的i-1层。此时算法选择下一个要排列的圆，并计算相应的下界函数。
5.3
源代码
#include <iostream>
#include <cmath>
using namespace std;
float CirclePerm(int n,float *a);
template <class Type>
inline void Swap(Type &a, Type &b);
int main()
{
float *a = new float[4];
a[1] = 1,a[2] = 1,a[3] = 2;
cout<<“圆排列中各圆的半径分别为：“<<endl;
for(int i=1; i<4; i++)
{
cout<<a[i]<<“ “;
}
cout<<endl;
cout<<“最小圆排列长度为：“;
cout<<CirclePerm(3,a)<<endl;
return 0;
}
class Circle
{
friend float CirclePerm(int,float *);
private:
float Center(int t);
void Compute();
void Backtrack(int t);
float min,
*x,
*r;
int n;
};
float Circle::Center(int t)
{
float temp=0;
for (int j=1;j<t;j++)
{
float valuex=x[j]+2.0*sqrt(r[t]*r[j]);
if (valuex>temp)
{
temp=valuex;
}
}
return temp;
}
void Circle::Compute(void)
{
float low=0,high=0;
for (int i=1;i<=n;i++)
{
if (x[i]-r[i]<low)
{
low=x[i]-r[i];
}
if (x[i]+r[i]>high)
{
high=x[i]+r[i];
}
}
if (high-low<min)
{
min=high-low;
}
}
void Circle::Backtrack(int t)
{
if (t>n)
{
Compute();
}
else
{
for (int j = t; j <= n; j++)
{
Swap(r[t], r[j]);
float centerx=Center(t);
if (centerx+r[t]+r[1]<min)
{
x[t]=centerx;
Backtrack(t+1);
}
Swap(r[t], r[j]);
}
}
}
float CirclePerm(int n,float *a)
{
Circle X;
X.n = n;
X.r = a;
X.min = 100000;
float *x = new float[n+1];
X.x = x;
X.Backtrack(1);
delete []x;
return X.min;
}
template <class Type>
inline void Swap(Type &a, Type &b)
{
Type temp=a;
a=b;
b=temp;}
5.4
运行结果图
图5-1
结论
在三个实例编程中，总的算法思想都是利用回溯法求解问题。第一个我们选的图的着色问题，这是一个NP问题。涉及到图的邻接顶点的访问和图的便利。图的储存结构选择的是邻接矩阵的形式，在遍历图式时是从第一个顶点开始，一次在顶点数组中完成所有顶点的遍历，保证了全部的顶点都是可以访问到的，因为要着色，所以着色是一个动态的过程，可以在遍历的过程中完成着色，每次访问一个结点，先赋值第一种颜色，如果和它的临接点的颜色不重复，则对下个顶点着色，否则本顶点的颜色转化到下一种，直到能够完成赋值。
程序编写本身不难，思路很清晰，就是赋值和比较之间的来回循环比较困难。在通过三个实例的练习中，我们对回溯算法有了更进一步的理解，对回溯法的解框架更清楚了。但在另一方面，也认识到了自己的不足，因此，通过这三个编程，又使自己收获了很多，还需要更加深入的学习算法。这说明回溯法是一种通用性很高的算法模型，这是因为我们回溯法面向的是一棵空间搜索树，这课树已经完成了从实际问题到数学表达的建模。而每棵树的特性都是相当一致的，所以我们的算法也具有高度的一致性。从这个角度看，一旦掌握了回溯法，那以后用起来是比较简单的，所以回溯法是一个很值得学习的算法。
问题的解空间通常是在搜索问题的解得过程中动态产生的，这是回溯的一个重要特性。
其实回溯法的根本思想就是从一条路往前走，能进则进，不能进则退回来，换一条路再试。当我们遇到某一类问题时，它的问题可以分解，但是又不能得出明确的动态规划或是递归解法，此时可以考虑用回溯法解决此类问题。回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。但是，对于可以得出明显的递推公式迭代求解的问题，还是不要用回溯法，因为它花费的时间比较长。
对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得出结果。但是，回溯法中通过构造约束函数，可以大大提升程序效率，因为在深度优先搜索的过程中，不断的将每个解（并不一定是完整的，事实上这也就是构造约束函数的意义所在）与约束函数进行对照从而删除一些不可能的解，这样就不必继续把解的剩余部分列出从而节省部分时间。
参考文献
