一、实验目的
1．加深学生对回溯法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；
2．提高学生利用课堂所学知识解决实际问题的能力；
3．提高学生综合应用所学知识解决实际问题的能力。
二、实验任务
用回溯法解决下列问题：
1、 八皇后问题
在8×8的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到n皇后问题，即在n×n的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。
2、 连续邮资问题
连续邮资问题：某国家发行了n种不同面值的邮票，并且规定每张信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m的值，给出邮票面值的最佳设计。
3、 卫兵布置问题
一个博物馆由排成m×n个矩阵陈列的陈列室组成，需要在陈列室中设立哨位，每个哨位上的哨兵除了可以监视自己所在陈列室外，还可以监视他上、下、左、右四个陈列室。试给出一个最佳哨位安排方法，使得所有陈列室都在监视之下，但使用的哨兵最少。
4、 圆排列问题
给定n个大小不等的圆c1,c2,…,cn，现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。
三、实验设备及编程开发工具
编程开发工具：Microsoft Visual c++
四、实验过程设计（算法设计过程）
（一）八皇后问题
1、基本算法思想
首先我们分析一下问题的解，我们每取出一个皇后，放入一行，共有八种不同的放
简单的说就是 从当前列中依次选取位置，与前面列中选取的位置进行比较，判断是否冲突，若冲突，回溯到上一列寻找，否则进入下一列寻找位置
1、从column=0列中选取一个位置，column+1，转到2。（这里column为当前列 值为0~7），
2、从第column列中选取一个位置， 转到3。
3、判断是否与前面各列选取位置冲突。
若冲突：判断column列中位置是否全部判断过，若是 转到5，否则 直接转到2；
否则：转到4。
4、判断是否到最后一列。
若到最后一列说明本次查找成功，记录位置并将结果输出，转到5；
否则，记录当前位置，进入下一列寻找合适位置，即column+1转到2
5、判断是否回溯到第一列。
若是：结束。
否则：继续回溯，回溯到上一列继续选取位置，即column-1转到2 。
2、源程序
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace eightQueen
{
//八皇后问题：在8*8格的国际象棋上摆放八个皇后，使其不能互相攻击，
//即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
class Program
{
staticvoid Main(string[] args)
{
DateTime time1 = DateTime.Now;
QueenArithmetic(8); //皇后个数可选
DateTime time2 = DateTime.Now;
TimeSpan span = time2 - time1;
Console.WriteLine("\n执行时间："+span);
Console.ReadKey();
}
//定义解决皇后问题方法，使用回溯法，根据皇后数量获取结果
staticvoid QueenArithmetic(int queenNum)
{
int[] Queen =newint[queenNum]; //保存每次成功的结果，索引代表所在列，值代表皇后在该列的位置
int row =0; //当前所在的行
int column =0; //当前所在列
Queen[0]=-1;
int count =0; //用来记录当前是第几种摆法
while (true)
{
for (row = Queen[column]+1; row < queenNum; row++) //遍历本次回溯 该列中未被访问到的行
{
if (!IsConflict(Queen, column, row)) //如果不冲突
{
break;
}
}
if (row >= queenNum) //没有找到合适的位置
{
if (column ==0) //如果当前已经回溯到了第一列
{
break; //退出while循环，整个过程结束
}
else
{
Queen[column] =-1; //否则回溯到上一列
column--;
}
}
else//找到了合适的位置
{
Queen[column] = row;
column++; //为下一列找合适位置
if (column < queenNum)//如果当前不是最后一列
{
Queen[column] =-1;
}
else//说明本次查找完毕，开始打印输出
{
PrintQueen(Queen, queenNum, ++count);//打印输出当前结果
column--; //回溯到上一列继续查找
}
}
}
}
//根据获得的皇后数组，判断当前位置（row,column）是否与前面冲突
staticbool IsConflict(int[] queen, int column, int row)
{
for (int exsitColumn =0; exsitColumn < column; exsitColumn++) //遍历当前列之前的所有列中找到的皇后位置，检测是否与当前位置冲突
{
int exsitRow = queen[exsitColumn];
int span = column - exsitColumn;
if ((row == exsitRow) || (row == exsitRow + span) || (row == exsitRow - span)) //如果在同一行或者同一条斜线上
{
returntrue; //即冲突
}
}
returnfalse;
}
//打印输出结果
staticvoid PrintQueen(int[] queen,int queenNum, int count)
{
Console.WriteLine("\n第{0}种摆法：", ++count);
for (int c =0; c < queenNum; c++)
{
for (int r =0; r < queenNum; r++)
{
if (r == queen[c])
{
Console.Write("Q");
}
else
{
Console.Write("*");
}
}
Console.Write("\n");
}
}
}
}
（二）连续邮资问题
1、基本算法思想
在下面的回溯法描述中，递归函数Backtrack实现对整个解空间的回溯搜索。 maxvalue记录当前已经找到的最大连续邮资区间，bestx是相应的当前最优解。 数组y用来记录当前已经选定的邮票面值x[1:i]能贴出各种邮资所需的最少邮票数。 也就是说,y[k]是用不超过m张面值为x[1:i]的邮票，贴出邮资k所需的最少邮票张数。 在函数Backtrack中， 当i>n时，表示算法已经搜索到一个叶结点，得到一个新的邮票面值设计方案x[1:n]。如果该方案能贴出的 最大连续邮资区间大于当前已经找到的最大连续邮资区间maxvalue，则更新当前最优值maxvalue和相应的最优解。 当i <= n时，当前扩展结点z是解空间中的一个内部结点，在该结点处x[1:i-1] 能贴出的最大最大邮资区间为r-1.因此在结点z处x[i]的可取范围是x[i-1]+1:r， 从而，结点z有r-x[i-1]个儿子结点。算法对当前扩展结点z的每一个儿子结点， 以深度优先的方式递归地对相应子树进行搜索 解空间是多叉树，孩子接点个数是每层都在变化的。
2、源程序
#include <stdio.h>
#include <string.h>
int n,m;//n为邮票种类,m为一封信上最多贴的邮票个数
int Max;
int ans[10000];//最终答案数组
int min(int a,int b)
{
return a<b?a:b;
}
int panduan(int x[10000],int n,int sum)
//能否用n种邮票，面值在x数组中,最多贴m张，表示出sum(是个动态规划问题，
//方法是求出dp[n][sum]看它是否小于sum,状态转移方程dp[i][j]=min(dp[i-1][j-k*x[i]]+k)(其中dp[i][j]表示用到第i种邮票，表示邮资为j的最少邮票
{
int i,j,k;
int dp[15][1005];
for (i=0;i<=n;i++)
dp[i][0]=0;
for (i=0;i<=sum;i++)
dp[1][i]=i;
for (i=2;i<=n;i++)
for (j=1;j<=sum;j++)
{
dp[i][j]=9999;
for (k=0;k<=j/x[i];k++)
dp[i][j]=min(dp[i][j],dp[i-1][j-x[i]*k]+k); //使用min函数
}
if (dp[n][sum]>m)
return 0;
return 1;
}
void DFS(int x[10000],int cur,int max)//x数组储存当前的解，cur代表目前到第几种面值，当到n为止，max表示到目前为止的最大可到达邮资。
{
int i,j,next;
if (cur==n)//如果已经得出了n种邮票
{
if (max>Max)//并且它的最大值已经大于当前最大邮资数
{
Max=max;
for (i=1;i<=cur;i++)
ans[i]=x[i];//更新答案数组
}
return;
}
for (next=x[cur]+1;next<=max+1;next++)//如果还没得到n中邮票，那么从x[cur]+1~max+1选一个作为下一个邮资，
//因为max+1没法表示，所以必定到max+1为止
{
x[cur+1]=next;//接下来是重点，用种类为cur+1,数目分别为x[1..cur+1]的邮票,最多使用m张，能否表示出大于max的某个数
for (i=max+1;i<=m*x[cur+1];i++)//这个数最少要为max+1(不然没有意义了),最多是x[cur+1]*m
if (panduan(x,cur+1,i)==0)//如果成立
break;
if (i>max+1)//如果至少让最大值更新了一次
DFS(x,cur+1,i-1);
}
}
int main()
{
int i,j,max,cur;
int x[1000];//中间传递的数组，存储当前的邮票值的解
printf("请输入邮票种类数:");
scanf("%d",&n);
printf("请输入最多粘贴邮票数:");
scanf("%d",&m);
Max=0;
max=m;
cur=1;
x[cur]=1;
DFS(x,cur,max);//x存储当前的解,cur表示当前传递到第几种邮票,max表示目前能表示到的最大值
printf("生成的最大邮资是:%d\n",Max);
for (i=1;i<=n;i++)
printf("%d ",ans[i]);
return 0;
}
（三）卫兵布置问题
1、基本算法原理
从上到下、从左到右的顺序依次考查每一个陈列室设置警卫机器人哨位的情况，以及该陈列室受到监视的情况，用[i,j]表示陈列室的位置，用x[i][j]表示陈列室[i,j]当前设置警卫机器人哨位的状态。当x[i][j]=1时，表示陈列室[i,j]设置了警卫机器人，当x[i][j]=0时，表示陈列室[i,j]没有设置了警卫机器人。用y[i][j]表示陈列室[i,j]当前受到监视的的警卫机器人的数量。当y[i][j]>0时，表示陈列室[i,j]受到监视的警卫机器人的数量，当y[i][j]=0时，表示陈列室[i,j]没有受到监视。设当前已经设置的警卫机器人的哨位数为k，已经受到监视的陈列室的数量为t，当前最优警卫机器人哨位数为bestc。
设回溯搜索时，当前关注的陈列室是[i,j]，假设该陈列室已经受到监视，即y[i][j]==1，
此时在陈列室[i,j]处设置一个警卫机器人哨位，即x[i][j]==1，相应于解空间树的一个节点q，在陈列室[i+1,j]处设置一个机器人哨位，x[i+1][j]==1，相应于解空间树的另一个节点p。容易看出，以q为根的子树的解，不优于以p为根的子树的解，以q为根的子树可以剪去。因此，在以从上到下，从左到右的顺序依次考察每一个陈列室时，已受监视的陈列室不必设置警卫机器人哨位。
设陈列室[i,j]是从上到下、从左到右搜索到的第一个未受监视的陈列室，为了使陈列室[i,j]受到监视，可在陈列室[i+1,j]、[i,j]、[i,j+1]处设置警卫机器人哨位，在这3处设置哨位的解空间树中的结点分别为p、q、r。
当y[i][j+1]==1时，以q为根的子树的解，不优于以p为根的子树的解，当y[i][j+1]==1且y[i][j+2]==1时，以r为根的子树的解，不优于以p为根的子树的解。搜索时应按照p、q、r的顺序来扩展结点，并检测节点p对节点q和节点r的控制条件。
2、源代码
#include<fstream>
#include<iostream>
using namespace std;
ifstream fin("input.txt");
ofstream fout("output.txt");
ofstream testout("testout.txt");
class Exhibit_hall {
friend void Setrobot(int, int);
private:
void set(int i, int j, int a[]);//安排哨兵
void recover(int i, int j, int a[]);
void Backtrack(int i, int j);
void GreedySearch(); //贪婪搜索
int search(int i, int j); //搜索在a[i][j]安排哨兵人时它所监督未被监督的陈列室个数
void set(int i, int j);
int m, n; //陈列馆的行数,列数
int mn; //陈列室个数
int g_num; //陈列室中已被监视的个数
int num; //当前哨兵个数
int num1; //用于贪心搜索中哨兵的个数
int **x; //当前解
int bestn; //当前最优解的个数
int **bestx;//当前最优解
};
void Exhibit_hall::set(int i, int j, int a[])//x[][]为1表示此房间已放置了一个哨兵，为2表示此房间已被监视
{
num++;
a[0] = x[i][j];
if (a[0] == 0) g_num++;//若此陈列室未被监视，则此时已被监视g_num++
x[i][j] = 1;//此位置放置了一个哨兵
if (x[i - 1][j] == 0) { a[1] = 1;x[i - 1][j] = 2;g_num++; }//若上方未被监视,则此时设置未已被监视
if (x[i][j + 1] == 0) { a[2] = 1;x[i][j + 1] = 2;g_num++; }
if (x[i + 1][j] == 0) { a[3] = 1;x[i + 1][j] = 2;g_num++; }
if (x[i][j - 1] == 0) { a[4] = 1;x[i][j - 1] = 2;g_num++; }
}
void Exhibit_hall::recover(int i, int j, int a[])//撤消哨兵
{
num--;
x[i][j] = a[0];
if (a[0] == 0) g_num--;
if (a[1]) { x[i - 1][j] = 0;g_num--; }
if (a[2]) { x[i][j + 1] = 0;g_num--; }
if (a[3]) { x[i + 1][j] = 0;g_num--; }
if (a[4]) { x[i][j - 1] = 0;g_num--; }
a[0] = 0;a[1] = 0;a[2] = 0;a[3] = 0;a[4] = 0;
}
void Exhibit_hall::Backtrack(int i, int j)//回溯
{
if (i>m) {
if (num<bestn)
{
for (int k = 1;k<m + 1;k++)
for (int l = 1;l<n + 1;l++)
bestx[k][l] = x[k][l];
bestn = num;
}
return;
}
if (num + (mn - g_num) / 5 >= bestn) return;
//当此陈列室已被监视，则没必要在此陈列室安排哨兵
//因为x[i+1][j+1]放置一机器人优于此处哨兵
if (x[i][j] != 0)
Backtrack(i + j / n, j%n + 1);
//在此陈列室被监视
else
{
int a[5] = { 0 };
if (i<m) //在此陈列室下面安排哨兵监视此陈列室
{
set(i + 1, j, a);
Backtrack(i, j);
recover(i + 1, j, a);
}
if ((j<n) && (x[i][j + 1] == 0 || x[i][j + 2] == 0)) //在此陈列室右边安排哨兵监视此陈列室
{
set(i, j + 1, a);
Backtrack(i, j);
recover(i, j + 1, a);
}
if (x[i + 1][j] == 0 && x[i][j + 1] == 0) //在此陈列室安排哨兵
{
set(i, j, a);
Backtrack(i, j);
recover(i, j, a);
}
}
}
int Exhibit_hall::search(int i, int j)
{
if (i == m + 1 || j == n + 1) return 0;
int count = 0;
if (x[i][j] == 0)count++;
if (x[i - 1][j] == 0)count++;
if (x[i][j + 1] == 0)count++;
if (x[i + 1][j] == 0)count++;
if (x[i][j - 1] == 0)count++;
return count;
}
void Exhibit_hall::set(int i, int j)
{
num1++;
x[i][j] = 1;
if (x[i - 1][j] == 0)x[i - 1][j] = 2;
if (x[i][j + 1] == 0)x[i][j + 1] = 2;
if (x[i + 1][j] == 0)x[i + 1][j] = 2;
if (x[i][j - 1] == 0)x[i][j - 1] = 2;
}
void Exhibit_hall::GreedySearch()
{
for (int i = 1;i <= m;i++)
for (int j = 1;j <= n;j++)
{
if (x[i][j] == 0)
{
int a1 = 0, a2 = 0, a3 = 0;
a1 = search(i, j);
a2 = search(i + 1, j);
a3 = search(i, j + 1);
if (a1 >= a2&&a1 >= a3)set(i, j);
else {
if (a2 >= a3)
{
if (a2>a3)set(i + 1, j);
else
if (x[i + 1][j] != 0 && x[i][j + 1] == 0)set(i, j + 1);
else set(i + 1, j);
}
else set(i, j + 1);
}
}
}
for (i = 1;i <= m;i++)
for (int j = 1;j <= n;j++)
{
bestx[i][j] = x[i][j];
x[i][j] = 0;
}
bestn = num1;
}
void Setrobot(int m, int n)
{
Exhibit_hall Ex;
Ex.m = m;
Ex.n = n;
Ex.mn = m*n;
Ex.num = 0;
Ex.num1 = 0;
Ex.bestn = m*n;
Ex.g_num = 0;
Ex.x = new int*[m + 2];
for (int i = 0;i<m + 2;i++)
{
Ex.x[i] = new int[n + 2];
for (int j = 0;j<n + 2;j++)Ex.x[i][j] = 0;
}
Ex.bestx = new int*[m + 2];
for (i = 0;i<m + 2;i++)
{
Ex.bestx[i] = new int[n + 2];
for (int j = 0;j<n + 2;j++)Ex.bestx[i][j] = 0;
}
for (int k = 0;k<n + 2;k++) { Ex.x[0][k] = 2;Ex.x[m + 1][k] = 2; }
for (k = 1;k<m + 1;k++) { Ex.x[k][0] = 2;Ex.x[k][n + 1] = 2; }
Ex.GreedySearch();
//cout << Ex.bestn << endl;
Ex.Backtrack(1, 1);
fout << Ex.bestn << endl;
for (int j = 1;j <= m;j++) {
for (int k = 1;k <= n;k++)
{
if (Ex.bestx[j][k] == 1)fout << 1 << ' ';
else fout << 0 << ' ';
testout << Ex.bestx[j][k] << ' ';
}
fout << endl;
testout << endl;
}
delete[] Ex.x;
delete[] Ex.bestx;
}
void main()
{
int m, n;
cin >> m >> n;
Setrobot(m, n);
}
（四）圆排列问题
1、基本算法原理
圆排列问题的解空间是一棵排列树。按照回溯法搜索排列树的算法框架，设开始时a=[r1,r2,……rn]是所给的n个元的半径，则相应的排列树由a[1:n]的所有排列构成。
解圆排列问题的回溯算法中，CirclePerm(n,a)返回找到的最小的圆排列长度。初始时，数组a是输入的n个圆的半径，计算结束后返回相应于最优解的圆排列。center计算圆在当前圆排列中的横坐标，由x^2 = sqrt((r1+r2)2-(r1-r2)2)推导出x = 2sqrt(r1r2)。Compoute计算当前圆排列的长度。变量min记录当前最小圆排列长度。数组r表示当前圆排列。数组x则记录当前圆排列中各圆的圆心横坐标。
在递归算法Backtrack中，当i>n时，算法搜索至叶节点，得到新的圆排列方案。此时算法调用Compute计算当前圆排列的长度，适时更新当前最优值。
当i<n时，当前扩展节点位于排列树的i-1层。此时算法选择下一个要排列的圆，并计算相应的下界函数
2、源代码
//圆排列问题 回溯法求解
#include "stdafx.h"
#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++)
{
//由x^2 = sqrt((r1+r2)^2-(r1-r2)^2)推导而来
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;
}
五、实验结果及算法复杂度分析
（一）八皇后问题
1、实验结果
2、时间复杂度
时间复杂度为O(n^2)。
（二）连续邮资问题
1、实验结果
2、时间复杂度
时间复杂度为O(n^2)。
（三）卫兵布置问题
1、实验结果
2、时间复杂度
时间复杂度为O(n*2^n)。
（四）圆排列问题
1、实验结果
2、时间复杂度
最坏时间复杂为O((n+1)!)。
实验小结（包括问题和解决方法、心得体会等）
本次实验的中心思想就是回溯法，回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。在通过本次实验的四道题目的实践，相信自己对回溯法已经足够掌握了。
