回溯法实验报告
实验04 回溯法
班级：0920561 姓名：宋建俭学号：20
一、实验目的
1.掌握回溯法的基本思想。
2.掌握回溯法中问题的解空间、解向量、显式约束条件、隐式约束条件以及子
集树与排列树的递归算法结构等内容。
3.掌握回溯法求解具体问题的方法。
二、实验要求
1.认真阅读算法设计教材,了解回溯法思想及方法;
2.设计用回溯算法求解装载问题、n后问题、图的m着色问题的java程序
三、实验内容
1.有一批共n个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱
i的重量为wi，且∑wi≤C1+C2。装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。
2.在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，
皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。
3.给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每
个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。
这个问题是图的m可着色判定问题。
四、算法原理
1、装载问题
用回溯法解装载问题时，用子集树表示其解空间是最合适的。可行性约束可剪去不满足约束条件(w1x1+w2x2+…+wnxn)<=c1的子树。在子集树的第j+1层结点Z处，用cw记当前的装载重量，即cw=(w1x1+w2x2+…+wjxj)，当cw>c1时，以结点Z为根的子树中所有结点都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪去。
解装载问题的回溯法中，方法maxLoading返回不超过c的最大子集和，但未给出达到这个最大子集和的相应子集。
算法maxLoading调用递归方法backtrack(1)实现回溯搜索。Backtrack(i)搜索子集树中第i层子树。类Loading的数据成员记录子集树结点信息，以减少传给backtrack的参数。cw记录当前结点相应的装载重量，bestw记录当前最大装载重量。
在算法backtrack中，当i>n时，算法搜索至叶结点，其相应的装载重量cw。如果cw>bestw,则表示当前解优于当前最优解,此时应更新bestw。
当i<=n时，当前扩展结点Z是子集树的内部结点。该结点有x[i]=1和x[i]=0两个儿子结点。其左儿子结点表示x[i]=1的情形，仅当cw+w[i]<=c时进入左子树，对左子树递归搜索。其右儿子结点表示x[i]=0的情形。由于可行结点的右儿子结点总是可行的，故进入右子树时不需检查可行性。
算法backtrack动态地生成问题的解空间树。在每个结点处算法花费O(1)时间。子集树中结点个数为O(2的n次方)，故backtrack所需的计算时间为O(2的n 次方)。另外backtrack还需要额外的O(n)递归栈空间。
2、n后问题
用n元祖x[1:n]表示n后问题的解。其中x[i]表示皇后i放在棋盘的第i行的第x[i]列。由于不允许将2个皇后放在同一列，所以解向量中的x[i]互不相同。2个皇后不能放在同一斜线上是问题的隐约束。对于一般的n后问题，这一隐约束条件可以化成显约束的形式。将n×n格棋盘看作二维方阵，其行号从上到下，列号从左到右依次编号为1,2，…，n。从棋盘左上角到右下角的主对角线及其平行线(即斜率为-1的各斜线)上，2个下标值的差(行号-列号)值相等。同理，斜率为+1的每一条斜线上，2个下标值的和(行号+列号)值相等。因此，若2个皇后放置的位置分别是(i，j)和(k，l)，且i-j=k-l或i+j=k+l，则说明这2个皇后处于同一斜线上。以上2个方程分别等价于i-k=j-l和i-k=l-j。由此可知，只要|i-k|=|j-l|成立，就表明2个皇后位于同一条斜线上。问题的隐约束化成了显约束。
用回溯法解n后问题时，用完全n叉树表示解空间。可行性约束place剪去不满足行、列和斜线约束的子树。
解n后问题的回溯法中，递归方法backtrack(1)实现对整个解空间的回溯搜索。Backtrack(i)搜索解空间中第i层子树。类Queen的数据成员记录解空间中节点信息，以减少传给backtrack的参数。Sum记录当前已找到的可行方案数。
在算法backtrack中，当i>n时，算法搜索至叶节点，得到一个新的n皇后互不攻击方案，当前已找到的可行方案数sum曾1.
当i<=n时，当前扩展节点Z是解空间中的内部结点。该结点有x[i]=1,2,…，n，共n个儿子结点。对当前扩展结点Z的每一个儿子结点，由place检查其可行
性，并以深度优先的方式递归地对可行子树搜索，或剪去不可行子树。
3、图的m着色问题
给定图G=(V,E)和m种颜色，用图的邻接矩阵a表示无向连接图G=(V,E)。若(i,j)属于图G=(V,E)的边集E，则a[i][j]=0。整数1,2，…，m用来表示m种不同颜色。顶点i所着颜色用x[i]表示。数组x[1:n]是问题的解向量。问题的解空间可表示为一棵高度为n+1的完全m叉树。解空间树的第i(1<=i<=n)层中每一结点都有m个儿子，每个儿子相应于x[i]的m个可能的着色之一。第n+1层结点均为叶节点。
在解图的m着色问题的回溯法中，backtrack(i)搜索解空间中第i层子树。类Coloring的数据成员记录解空间中结点信息，以减少传给backtrack的参数。Sum记录当前找到的m可着色方案数。
在算法backtrack中，当i>n时，算法搜索至叶结点，得到新的m着色方案，当前找到的m可着色方案数sum增1。
当i<=n时，当前扩展结点Z是解空间中的内部结点。该结点有x[i]=1,2,…，m 共m个儿子结点。对当前扩展结点Z的每一个儿子结点，由方案ok检查其可行性，并以深度优先的方式递归地对可行子树搜索，或剪去不可行子树。
五、实验程序功能模块
1、装载问题
import java.io.IOException;
public class MainLoading {
public static void main(String[] args) throws IOException { Loading loading = new Loading();
int n = 4;
System.out.println("集装箱个数: " + n);
int[] x = new int[n + 1];
String[] b = new String[n];
String a = "30 50 20 70";
System.out.println("集装箱重量: " + a);
int[] w = new int[n + 1];
w[1] = 30;
w[2] = 50;
w[3] = 20;
w[4] = 70;
int c1 = 130;
int c2 = 70;
System.out.println("轮船载重量: " + c1 + "," + c2);
int result = loading.maxloading(w, c1, x);
int max, temp;
for (int i = 1; i < 3; i++) {
for (int j = 2; j < 3; j++) {
if (w[i] > w[j]) {
temp = w[i];
w[i] = w[j];
w[j] = temp;
}
}
}
if ((w[3] > c1) && (w[3] > c2)) {
System.out.println("都不可装");
}
else {
System.out.println("轮船1装载的集装箱：");
for (int u = 1; u < n + 1; u++)
if (loading.bestx[u] == 1)
System.out.println(u + " ");
if (loading.r > (result + c2))
System.out.println("轮船1可装：" + result + " " + "轮船2装不完.");
else {
System.out.println("轮船2装载的集装箱：");
for (int u = 1; u < n + 1; u++)
if (loading.bestx[u] == 0)
System.out.println(u + " ");
System.out.println("最优装载--轮船1:" + result + " " + "轮船2:"+ (loading.r - result));
}
}
}
}
public class Loading {
static int n;
static int[] w;
static int c1, c2; // 第一、二艘轮船的载重量
static int cw;
static int bestw;
static int r;
static int[] x;
static int[] bestx;
public static int maxloading(int[] ww, int cc, int[] xx) { n = ww.length - 1;
w = ww;
c1 = cc;
bestw = 0;
cw = 0;
x = new int[n + 1];
bestx = xx;
r = 0;
for (int i = 1; i <= n; i++)
r += w[i];
backtrack(1);
return bestw;
}
private static void backtrack(int i) { if (i > n) {
if (cw > bestw) {
for (int j = 1; j <= n; j++)
bestx[j] = x[j];
bestw = cw;
}
return;
}
r -= w[i];
if (cw + w[i]<=c1){
x[i] = 1;
cw += w[i];
backtrack(i + 1);
cw -= w[i];
}
if (cw + r > bestw) {
x[i] = 0;
backtrack(i + 1);
}
r += w[i];
}
}
2、n后问题
import java.io.IOException;
public class MainNQueen {
public static void main(String[] args) { nQueen nqueen = new nQueen();
int nn; // 输入n值
int sum; // 可行方案个数
try {
nn = 4; // 将输入值转换为int保存
if (nn <= 0) {
throw new IOException("不能输入负数");
}
System.out.println("方格数是：" + nn);
sum = nqueen.nQueen(nn); // 调用nqueen方法
System.out.println("可行方案个数为：" + sum); // 输出sum } catch (IOException e) {
System.out.println(e.getMessage());
} catch (NumberFormatException e) {
System.out.println("请输入数字。。。");
}
}
}
public class nQueen {
static int n; // 皇后个数
static int[] x; // 当前解
static int sum; // 当前已找到的可行方案个数
static int nQueen(int nn) {
n = nn; // 把输入给全局变量n
sum = 0; // 初始化totle
x = new int[n + 1];
for (int i = 0; i <= n; i++)
x[i] = 0; // 初始化x
backtrack(); // 调用回溯算法
return sum;
}
private static void backtrack(){
x[1] = 0;
int k = 1;
while (k > 0) {
x[k]+=1; // 第k列皇后向下移一行
while ((x[k] <= n) && !(place(k))) { // 如果当前第k列皇后未出界或者和其他皇后冲突
x[k] += 1; // 第k列皇后向下移一行继续寻找
}
if(x[k]<=n) // 找到一个值并且未出界
if (k==n) { // 已是最后一列说明已找到一个方案
sum++;
}
else { // 不是最后一列故寻找下一列
k++;
x[k] = 0;
}
else// 找到的值已经出界，回退到上一列
k--;
}
}
// 判断皇后是否冲突
private static boolean place(int k) {
for (int j=1; j if((Math.abs(k-j)==Math.abs(x[j]-x[k])) || (x[j]==x[k])) return false; return true; } } 3、图的m着色问题 import java.util.Arrays; public class MainGraph_m_Color { public static void main(String[] args) { Coloring c = new Coloring(); int n = 4; System.out.println("图的顶点数:" + n); int m = 3; System.out.println("颜色数:" + m); boolean g[][] = new boolean[n + 1][n + 1]; g[1][2] = true; g[2][1] = true; g[1][3] = true; g[3][1] = true; g[2][3] = true; g[3][2] = true; g[2][4] = true; g[4][2] = true; g[3][4] = true; g[4][3] = true; c.mColoring(m, n, g); } } public class Coloring { static int n,m; static boolean [][]a; static int []x; static long sum; public static long mColoring(int mm,int nn,boolean [][]g){ m=mm; n=nn; a=g; x=new int[n+1]; sum=0; backtrack(1); return sum; } private static void backtrack(int t){ if(t>n){ System.out.println("解决方案："); sum++; for(int i=1;i<=n;i++) System.out.println("顶点"+i+"用颜色"+x[i]+" "); System.out.println(); } else for(int i=1;i<=m;i++){ x[t]=i; if(ok(t)) backtrack(t+1); x[t]=0; } } private static boolean ok(int k){ for(int j=1;j<=n;j++) if(a[k][j] && (x[j]==x[k])) return false; return true; } } 七、测试数据 1、装载问题 int n = 4; System.out.println("集装箱个数: " + n); int[] x = new int[n + 1]; String[] b = new String[n]; String a = "30 50 20 70"; System.out.println("集装箱重量: " + a); int[] w = new int[n + 1]; w[1] = 30; w[2] = 50; w[3] = 20; w[4] = 70; int c1 = 130; int c2 = 70; System.out.println("轮船载重量: " + c1 + "," + c2); 2、n后问题 nn = 4; 3、图的m着色问题 int n = 4; System.out.println("图的顶点数:" + n); int m = 3; System.out.println("颜色数:" + m); boolean g[][] = new boolean[n + 1][n + 1]; g[1][2] = true; g[2][1] = true; g[1][3] = true; g[3][1] = true; g[2][3] = true; g[3][2] = true; g[2][4] = true; g[4][2] = true; g[3][4] = true; g[4][3] = true; 测试结果 装载问题 集装箱个数: 4 集装箱重量: 30 50 20 70 轮船载重量: 130,70 轮船1装载的集装箱： 1 3 4 轮船2装载的集装箱： 2 最优装载--轮船1:120 轮船2:50 n后问题 方格数是：4 可行方案个数为：2 图的m着色问题 图的顶点数:4 颜色数:3 解决方案： 顶点1用颜色1 顶点2用颜色2 顶点3用颜色3 顶点4用颜色1 解决方案： 顶点1用颜色1 顶点2用颜色3 顶点3用颜色2 顶点4用颜色1 解决方案： 顶点1用颜色2 顶点2用颜色1 顶点3用颜色3 顶点4用颜色2 解决方案： 顶点1用颜色2 顶点2用颜色3 顶点3用颜色1 顶点4用颜色2 解决方案： 顶点1用颜色3 顶点2用颜色1 顶点3用颜色2 顶点4用颜色3 解决方案： 顶点1用颜色3 顶点2用颜色2 顶点3用颜色1 顶点4用颜色3 算法分析与设计实验报告第五次附加实验 附录： 完整代码（回溯法） //0-1背包问题回溯法求解 #include Typew c; //背包容量 int n; //物品数 Typew *w; //物品重量数组| Typep *p; //物品价值数组 Typew cw; //当前重量 Typep cp; //当前价值 Typep bestp; //当前最后价值 }; template 沈阳理工大学算法实践与创新论文 摘要 对于计算机科学来说，算法的概念是至关重要的，算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。为了更加的了解算法，本篇论文中，我们先研究一个算法---回溯法。 回溯法是一种常用的重要的基本设计方法。它的基本做法是在可能的范围之内搜索，适于解一些组合数相当大的问题。圆排列描述的是在给定n个大小不等的圆 C1,C2,…,Cn,现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。图着色问题用数学定义就是给定一个无向图G=（V, E），其中V为顶点集合，E为边集合，图着色问题即为将V分为K个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的 K值。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。 在本篇论文中，我们将运用回溯法来解决着图的着色问题，符号三角形问题，图排列问题，将此三个问题进行深入的探讨。 关键词: 回溯法图的着色问题符号三角形问题图排列问 题 目录 第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) 算法分析与设计实验报告第七次附加实验 } } 测试结果 当输入图如下时： 当输入图如下时： 1 2 3 4 5 1 2 3 4 5 当输入图如下时： 1 2 3 4 5 附录： 完整代码（回溯法） //最大团问题回溯法求解 #include cout<<"最大团：（"; for(int i=1;i 实验04 回溯法 班级：0920561 姓名：宋建俭学号：20 一、实验目的 1.掌握回溯法的基本思想。 2.掌握回溯法中问题的解空间、解向量、显式约束条件、隐式约束条件以及子 集树与排列树的递归算法结构等内容。 3.掌握回溯法求解具体问题的方法。 二、实验要求 1.认真阅读算法设计教材,了解回溯法思想及方法; 2.设计用回溯算法求解装载问题、n后问题、图的m着色问题的java程序 三、实验内容 1.有一批共n个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱 i的重量为wi，且∑wi≤C1+C2。装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。 2.在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则， 皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。 3.给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每 个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。 这个问题是图的m可着色判定问题。 四、算法原理 1、装载问题 用回溯法解装载问题时，用子集树表示其解空间是最合适的。可行性约束可剪去不满足约束条件(w1x1+w2x2+…+wnxn)<=c1的子树。在子集树的第j+1层结点Z处，用cw记当前的装载重量，即cw=(w1x1+w2x2+…+wjxj)，当cw>c1时，以结点Z为根的子树中所有结点都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪去。 解装载问题的回溯法中，方法maxLoading返回不超过c的最大子集和，但未给出达到这个最大子集和的相应子集。 算法maxLoading调用递归方法backtrack(1)实现回溯搜索。Backtrack(i)搜索 算法分析与设计实验报告第六次实验 附录： 完整代码（回溯法） //回溯算法递归回溯n皇后问题#include { friend int nQueen(int); //定义友元函数，可以访问私有数据 private: bool Place(int k); //判断该位置是否可用的函数 void Backtrack(int t); //定义回溯函数 int n; //皇后个数 int *x; //当前解 long sum; //当前已找到的可行方案数 }; int main() { int m,n; for(int i=1;i<=1;i++) { cout<<"请输入皇后的个数："; //输入皇后个数 cin>>n; cout<<"皇后问题的解为："< 数学与计算机学院实验报告 一、实验项目信息 项目名称：回溯法 实验时间： 2016/06/08 实验学时： 03 学时 实验地点：工科楼503 二、实验目的及要求 理解回溯法的深度优先搜索策略、 掌握用回溯法解题的算法框架、 掌握回溯法的设计策略 三、实验环境 计算机Ubuntu Kylin14.04 CodeBlock软件四、实验内容及实验步骤 排兵布阵问题 某游戏中，不同的兵种处在不同的地形上其攻击能力不一样，现有n个不同兵种的角色{1,2,...,n}，需安排在某战区n个点上，角色i在j点上的攻击力为A ij。试设计一个布阵方案，使总的攻击力最大。 数据： 防卫点 角 色 1 2 3 4 5 1 2 3 4 5 回溯法： 程序： #include if(check(k))break; else position[k]=position[k]+1; if(position[k]<=n && k==n-1) { for(i=0;i 应用数学学院信息安全专业班学号姓名 实验题目回溯算法 实验评分表 实验报告 一、实验目的与要求 1、理解回溯算法的基本思想； 2、掌握回溯算法求解问题的基本步骤； 3、了解回溯算法效率的分析方法。 二、实验内容 【实验内容】 最小重量机器设计问题：设某一个机器有n个部件组成，每个部件都可以m个不同供应商处购买，假设已知表示从j个供应商购买第i个部件的重量，表示从j个供应商购买第i个部件的价格，试用回溯法求出一个或多个总价格不超过c且重量最小的机器部件购买方案。 【回溯法解题步骤】 1、确定该问题的解向量及解空间树； 2、对解空间树进行深度优先搜索； 3、再根据约束条件（总价格不能超过c）和目标函数（机器重量最小）在搜索过程中剪去多余的分支。 4、达到叶结点时记录下当前最优解。 5、实验数据n,m, ] ][ [j i w,] ][ [j i c的值由自己假设。 三、算法思想和实现【实现代码】 【实验数据】 假设机器有3个部件，每个部件可由3个供应商提供（n=3，m=3）。总价不超过7（c<=7）。 部件重量表： 部件价格表： 【运行结果】 实验结果：选择供应商1的部件1、供应商1的部件2、供应商3的部件3，有最小重量机器的重量为4，总价钱为6。 四、问题与讨论 影响回溯法效率的因素有哪些？ 答：影响回溯法效率的因素主要有以下这五点： 1、产生x[k]的时间； 2、满足显约束得x[k]值的个数； 3、计算约束函数constraint的时间； 4、计算上界函数bound的时间； 5、满足约束函数和上界函数约束的所有x[k]的个数。 五、总结 这次实验的内容都很有代表性，通过上机操作实践与对问题的思考，让我更深层地领悟到了回溯算法的思想。 回溯算法的基本思路并不难理解，简单来说就是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯法的基本做法是深度优先搜索，是一种组织得井井 1.5 走迷宫(maze.pas)* 【问题描述】 有一个m * n格的迷宫（表示有m行、n列），其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这m * n个数据和起始点、结束点（起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号）。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向（搜索顺寻：左上右下）。如果一条路都不可行，则输出相应信息（用-1表示无路）。 【输入】 第一行是两个数据m，n（1 算法分析与设计实验报告第三次附加实验 附录： 完整代码（回溯法） //回溯算法递归回溯n皇后问题#include { friend int nQueen(int); //定义友元函数，可以访问私有数据 private: bool Place(int k); //判断该位置是否可用的函数 void Backtrack(int t); //定义回溯函数 int n; //皇后个数 int *x; //当前解 long sum; //当前已找到的可行方案数 }; int main() { int m,n; for(int i=1;i<=1;i++) { cout<<"请输入皇后的个数："; //输入皇后个数 cin>>n; cout<<"皇后问题的解为："< 大学计算机基础第五章 第五章软件技术基础 1.程序设计语言 （1）机器语言和汇编语言 由计算机硬件系统可以识别的指令组成的语言称为机器语言。汇编语言是将机器指令映射为一些可以被人读懂的助记符。由于计算机只能识别机器语言，所以汇编语言通常需要通过汇编程序翻译为机器语言。汇编语言的翻译软件称为汇编程序，它可以将程序员写的助记符直接转换为机器指令，然后由计算机去识别和执行。用机器语言编写的程序是计算机可以直接执行的程序。 用机器语言编写的程序，代码长度短，执行效率高。但是，这种语言的缺点也很明显。最主要的是编写机器语言程序必须要熟知CPU 的指令代码，编写程序既不方便，又容易出错，调试查错也非常困难。而且编写的程序只能在特定的机器上运行，没有通用性。 （2）高级语言 高级语言源程序翻译为指令代码有两种做法：编译或者解释。编译通过编译程序来完成。解释则是通过解释程序完成。解释的结果产生可以直接执行的指令。编译的结果是得到目标程序。目标程序也是要经过连接才会得到可执行程序目前应用比较广泛的几种高级语言由FORTRAN/BASIC/PASCAL/C等。 （3）面向对象的语言 （4）未来的语言 2、语言处理程序语言处理程序是把源程序翻译成机器语言的程序，可分为三种：汇编程序、编译程序和解释程序。 （1）汇编程序把汇编语言源程序翻译成机器语言程序的程序称为汇编程序，翻译的过程称为汇编。汇编程序在翻译源程序时，总是对源程序从头到尾一个符号一个符号地进行阅读分析，一般用两遍扫描完成对源程序的加工转换工作。汇编语言在翻译的同时，还对各种形式的错误进行检查和分析，并反馈给用户，以便修改。反汇编程序也是一种语言处理程序，它的功能与汇编程序相反，它能把机器语言程序转换成汇编语言程序。 （2）编译程序编译程序是把高级语言源程序（如Fortran、Pascal、C 等）翻译 八皇后问题的基本策略及其应用 郭洋洋王刚李晴孙佳 （陕西师范大学计算机科学学院09级计算机科学与技术，西安，710062） 摘要：针对八皇后问题，本文采用回溯法，给出递归与非递归两种算法的设计与分析，并通过实验验证两种算法的性能，得出最佳的算法。 关键词：八皇后；回溯法；递归算法；非递归算法 The Basic Algorithm Strategy For Eight Queens And Its Application Guo Yangyang,Wang Gang,Li Qing, Sun Jia (School of Computer Science ,Shanxi Normal University ,Xi’an ,710062 ) Abstract: Aiming at the problem of Eight Queens,this paper gives Backtracking , and Recursive algorithm and Non-recursive algorithm , and show the design and analysis of the two kinds of algorithms,and through the experiment ,verified the performance of them,getting the most suitable algorithm. Keywords: Eight Queens; Backtracking; Recursive; Non-Recursive 1 引言 八皇后问题由19 世纪著名的数学家高斯在1850 年提出:在8 ×8 格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法. 回溯算法是尝试搜索算法中最为基本的一种算法，其采用了一种“走不通就调头”的思想，作为其控制结构[1]。回溯法在用来求问题的所有解时，要回溯到根，且根节点的所有可行的子树都已被搜索遍才结束。而回溯法在用来求解问题任一解时，只要搜索到问题的一个解就可以结束。这就是以深度优先的方式系统的搜索问题解的回溯法，它适用于解决一些类似n皇后问题等就切方案问题，也可以解决一些最优化问题。 2 问题描述与模型 八皇后问题：在8 ×8 格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法. 例如图一所示： 实验报告 一、实验名称：回溯法求解N皇后问题（Java实现） 二、学习知识： 回溯法：也称为试探法，它并不考虑问题规模的大小，而是从问题的最明显的最小规模开始逐步求解出可能的答案，并以此慢慢地扩大问题规模，迭代地逼近最终问题的解。这种迭代类似于穷举并且是试探性的，因为当目前的可能答案被测试出不可能可以获得最终解时，则撤销当前的这一步求解过程，回溯到上一步寻找其他求解路径。 为了能够撤销当前的求解过程，必须保存上一步以来的求解路径，这一点相当重要。 三、问题描述 N皇后问题：在一个 N * N 的国际象棋棋盘中，怎样放置 N 个皇后才能使 N 个皇后之间不会互相有威胁而共同存在于棋局中，即在 N * N 个格子的棋盘中没有任何两个皇后是在同一行、同一列、同一斜线上。 深度优先遍历的典型案例。 四、求解思路 1、求解思路：最容易想到的方法就是有序地从第 1 列的第 1 行开始，尝试放上一个皇后，然后再尝试第 2 列的第几行能够放上一个皇后，如果第 2 列也放置成功，那么就继续放置第 3 列，如果此时第 3 列没有一行可以放置一个皇后，说明目前为止的尝试是无效的（即不可能得到最终解），那么此时就应该回溯到上一步（即第 2 步），将上一步（第 2 步）所放置的皇后的位置再重新取走放在另一个符合要求的地方…如此尝试性地遍历加上回溯，就可以慢慢地逼近最终解了。 2、需要解决的问题：如何表示一个 N * N 方格棋盘能够更有效？怎样测试当前所走的试探路径是否符合要求？这两个问题都需要考虑到使用怎样的数据结构，使用恰当的数据结构有利于简化编程求解问题的难度。 3、我们使用以下的数据结构： int column[col] = row 表示第 col 列的第 row 行放置一个皇后 boolean rowExists[i] = true 表示第 i 行有皇后 boolean a[i] = true 表示右高左低的第 i 条斜线有皇后（按→↓顺序从1~ 2*N -1 依次编号） boolean b[i] = true 表示左高右低的第 i 条斜线有皇后（按→↑顺序从1~ 2*N -1 依次编号） 五、算法实现 对应这个数据结构的算法实现如下： 第8章回溯法 (1) 8.1概述 (1) 8.1.1 问题的解空间树 (1) 8.1.2 回溯法的设计思想 (2) 8.1.3 回溯法的时间性能 (3) 8.1.4 一个简单的例子——素数环问题 (4) 8.2图问题中的回溯法 (5) 8.2.1 图着色问题 (5) 8.2.2 哈密顿回路问题 (8) 8.3组合问题中的回溯法 (10) 8.3.1 八皇后问题 (10) 8.3.2 批处理作业调度问题 (13) 习题8 (16) 第8章回溯法 教学重点回溯法的设计思想；各种经典问题的回溯思想教学难点批处理作业调度问题的回溯算法 教学内容 和 教学目标 知识点 教学要求 了解理解掌握熟练掌握问题的解空间树√ 回溯法的设计思想√ 回溯法的时间性能√ 图着色问题√ 哈密顿回路问题√ 八皇后问题√ 批处理作业调度问题√ 8.1 概述 回溯法（back track method）在包含问题的所有可能解的解空间树中，从根结点出发，按照深度优先的策略进行搜索，对于解空间树的某个结点，如果该结点满足问题的约束条件，则进入该子树继续进行搜索，否则将以该结点为根结点的子树进行剪枝。回溯法常常可以避免搜索所有的可能解，所以，适用于求解组合数较大的问题。 8.1.1 问题的解空间树 复杂问题常常有很多的可能解，这些可能解构成了问题的解空间（solution space），并且可能解的表示方式隐含了解空间及其大小。用回溯法求解一个具有n个输入的问题，一般情况下，将问题的可能解表示为满足某个约束条件的等长向量X=(x1, x2, …, x n)，其中分量x i（1≤i≤n）的取值范围是某个有限集合S i={a i,1, a i,2, …, a i,r i }，所有可能的解向量构成了问题的解空间。例如，对于有n个物品的0/1背包问题，其可能解由一个等长向量{x1, x2, …, x n}组成，其中x i=1（1≤i≤n）表示物品i装入背包，x i=0表示物品i没有装入背包，则解空间由长度为n的0/1向量组成。当n=3时，其解空间是： 回溯法：具有限界凼数的深度优先搜索法称为回溯法，具有“通用解题法”之称 两类问题：存在性问题：求满足某些条件的一个或全部元组，这些条件称为约束条件。如果不存在这样的元组，算法应返回No；优化问题：给定一组约束条件，在满足约束条件的元组中求使某目标函数达到最大（小）值的元组。满足约束条件的元组称为问题的可行解。 回溯法和分支限界法不同：每次只构造侯选解的一个部分，然后评估这个部分构造解，如果加上剩余的分量也不可能求得一个解,就绝对不会生成剩下的分量 问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。 显约束：对分量xi的取值限定。隐约束：为满足问题的解而对不同分量之间施加的约束。 解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界凼数来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。 解空间：子集树。可行性约束凼数：Σwixi≤C 上界凼数： Bound() 子集树回溯框架：void backtrack (int t){if(t>n) output(x);elsefor(int i=f(n,t);i<=g(n,t);i++) {x[t]=h(i);if (constraint(t)&&bound(t)) backtrack(t+1);}}//递归方法 void iterativeBacktrack(){int t=1;while(t>0){if(f(n,t)<=g(n,t)) for (int i=f(n,t);i<=g(n,t);i++) {x[t]=h(i);if(constraint(t)&&bound(t)) {if(solution(t)) output(x);elset++;}}elset--;}}//迭代方法 回溯法求解步骤1、针对所给问题，定义问题的解空间；2、确定易于搜索的解空间结构；3、以深度优先方式搜索解空间，并在搜索过程中用剪枝凼数避免无效搜索。 限界凼数(上界的计算方法) :r是当前尚未考虑的剩余物品价值总和,cp是当前价值,bestp是当前最优价值. 当cp+r<=bestp时,可剪去右子树贪心策略计算方法：将剩余物品按照单位重量价值排序,然后依次装入物品,直至装不下时,再装入该物品的一部分而装满背包.该价值是右子树中解的一个上界. Bound(int i){ Typew cleft=c-cw; Typep b=cp; while(i<=n&&w[i]<=cleft){cleft-=w[i]; b+=p[i]; i++;}if (i<=n) b+=p[i]/w[i]*cleft;return b;}//计算上界 实验4 回溯法解0-1背包问题 一、实验要求 1．要求用回溯法求解0-1背包问题； 要求交互输入背包容量，物品重量数组，物品价值数组；2．要求显示结果。3． 二、实验仪器和软件平台 仪器：带usb接口微机 软件平台：WIN-XP + VC++ 三、实验源码 #include \ #include { bag[i].flag=0; bag[i].kk=i; bag[i].fl=*bag[i].v/bag[i].w; } }void Backtrack(int i){cw+=bag[i].w;if(i>=n) <=c) lag=1; cp+=bag[i].v; Backtrack(i+1); cw-=bag[i].w; cp-=bag[i].v; } if(Bound(i+1)>bestp)lag=0; Backtrack(i+1); }}<=cleft){; b+=bag[i].v; i++; } /bag[i].w * cleft; return b; } void Knapsack() k]=bag[k].flag; lag*bag[k].v; //价值累加 } cout< 回溯法 回溯法也是搜索算法中的一种控制策略，但与枚举法不同的是，它是从初始状态出发，运用题目给出的条件、规则，按照深度优秀搜索的顺序扩展所有可能情况，从中找出满足题意要求的解答。回溯法是求解特殊型计数题或较复杂的枚举题中使用频率最高的一种算法。 一、回溯法的基本思路 何谓回溯法，我们不妨通过一个具体实例来引出回溯法的基本思想及其在计算机上实现的基本方法。【例题12.2.1】n皇后问题 一个ｎ×ｎ（1≤n≤100）的国际象棋棋盘上放置ｎ个皇后，使其不能相互攻击，即任何两个皇后都不能处在棋盘的同一行、同一列、同一条斜线上，试问共有多少种摆法？ 输入： n 输出： 所有分案。每个分案为n+1行，格式： 方案序号 以下n行。其中第i行（1≤i≤n）行为棋盘i行中皇后的列位置。 在分析算法思路之前，先让我们介绍几个常用的概念： 1、状态（state） 状态是指问题求解过程中每一步的状况。在ｎ皇后问题中，皇后所在的行位置i(1≤i≤n)即为其时皇后问题的状态。显然，对问题状态的描述，应与待解决问题的自然特性相似，而且应尽量做到占用空间少，又易于用算符对状态进行运算。 2、算符（operater） 算符是把问题从一种状态变换到另一种状态的方法代号。算符通常采用合适的数据来表示，设为局部变量。n皇后的一种摆法对应1．．ｎ排列方案（a1，…，a n）。排列中的每个元素a i对应ｉ行上皇后的列位置（1≤i≤n）。由此想到，在ｎ皇后问题中，采用当前行的列位置i(1≤i≤n)作为算符是再合适不过了。由于每行仅放一个皇后，因此行攻击的问题自然不存在了，但在试放当前行的一个皇后时，不是所有列位置都适用。例如(l，ｉ)位置放一个皇后，若与前1．．l-1行中的j行皇后产生对角线攻击(｜ｊ－l｜=｜a j －i｜)或者列攻击(ｉ≠a j)，那么算符ｉ显然是不适用的，应当舍去。因此，不产生对角线攻击和列攻击是ｎ皇后问题的约束条件，即排列（排列a1，…，a i，…，a j，…，a n）必须满足条件(｜ｊ－ｉ｜≠｜a j－a i｜) and (a i≠a j) (1≤i，j≤n)。 3、解答树（analytic tree） 现在让我们先来观察一个简单的ｎ皇后问题。设ｎ＝4，初始状态显然是一个空棋盘。 此时第一个皇后开始从第一行第一列位置试放，试放的顺序是从左至右、自上而下。每个棋盘由４个数据表征相应的状态信息（见下图）： （××××） 华南师范大学本科生实验报告 姓名＿黎国庄＿学号20062101247 院系＿计算机学院专业＿计算机科学与技术 年级2006级班级＿2班＿ 小组实验任务分工＿独立完成 实验时间2008 年＿6＿月 3 ＿日 实验名称回溯法的应用 指导老师及职称陈卫东老师 华南师范大学教务处编印 实验课程：算法分析与设计 实验名称：回溯法的应用（综设型实验） 第一部分实验内容 1．实验目标 （1）熟悉使用回溯法求解问题的基本思路。 （2）掌握回溯算法的程序实现方法。 （3）理解回溯算法的特点。 2. 实验任务 （1）从所给定的题目中选择一题，使用回溯法求解之。 （2）用文字来描述你的算法思路，包括解空间、限界函数、算法主要步骤等。 （3）在Windows环境下使用C/C++语言编程实现算法。 （4）记录运行结果，包括输入数据，问题解答及运行时间。 （5）分析算法最坏情况下时间复杂度和空间复杂度。 （6）谈谈实验后的感想，包括关于该问题或类似问题的求解算法的建议。 3. 实验设备及环境 PC；C/C++等编程语言。 4. 实验主要步骤 (1)根据实验目标，明确实验的具体任务； (2)设计求解问题的回溯算法，并编写程序实现算法； (3)设计实验数据并运行程序、记录运行的结果； (4)分析算法时空性能； (5)实验后的心得体会。 第二部分问题及算法 1.问题描述 给出一个8×8的棋盘，一个放在棋盘某个位置上的马（规定马的走法为走“日”）是否可以恰好访问每个方格一次，并回到起始位置上？ 2. 回溯法的一般思路 对于马所在其中一格时，它可以走的位置有以下8种情况： ⑧① ⑦② 马 ⑥③ ⑤④ 所以对于每一个马所在的格子里，马可以走对应的8个方向。 用满8叉树，每一个子树对应马可跳的方向 当要走下一子树（跳下一格）时，该子树可走（还没有走过并且在棋盘里边），即沿该方向走下去，当不可以走，即回溯到上一步，选择另一方向往下走；当该子树的8个子棋都遍历完了（即8个方向都走过了），则回溯到它父亲那里。 重复一直做下去，到棋盘每个格子都走过一遍，而且回到出发点或者找不到路径即结束。 3. 求解问题的回溯算法描述 算法如下： 输入：V（x,y）马开始的起点 输出：马从第一步到最后一步（64）的先后次序数字 1．v←（） 2.flag ← false 3．k ← 1 4．while k≥1 5． while X k 没有被穷举 6. x k ← X k 中的下一个元素；将x k 加入v 7． if v为最终解then set flag ← true，且从两个while循环退出 8. else if v是部分解then k ← k+1 {前进} 9. end while 10．重置X k ，使得下一个元素排在第一位 11． K ← k-1 {回溯} 12．end while 13．if flag then output v 14．else output “no solution” 4. 算法实现的关键技巧 回溯法概述 与穷举的“笨拙”搜索相比，回溯法则是一种“聪明”的求解效益更高的搜索法。 下面介绍回溯设计及其应用，体会回溯法相对于穷举的特点与优势。 回溯的概念 有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往使用回溯法。 回溯法是一种试探求解的方法：通过对问题的归纳分析，找出求解问题的一个线索，沿着这一线索往前试探，若试探成功，即得到解；若试探失败，就逐步往回退，换其他路线再往前试探。因此，回溯法可以形象地概括为“向前走，碰壁回头”。 回溯法的基本做法是试探搜索，是一种组织得井井有条的、能避免一些不必要搜索的穷举式搜索法。回溯法在问题的解空间树中，从根结点出发搜索解空间树，搜索至解空间树的任意一点，先判断该结点是否包含问题的解；如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其父结点回溯；否则，进入该子树，继续搜索。 从解的角度理解，回溯法将问题的候选解按某种顺序进行枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。倘若当前候选解除了不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。 与穷举法相比，回溯法的“聪明”之处在于能适时“回头”，若再往前走不可能得到解，就回溯，退一步另找线路，这样可省去大量的无效操作。因此，回溯与穷举相比，回溯更适宜于量比较大，候选解比较多的问题。 5.1.2 回溯描述 1．回溯的一般方法 下面简要阐述回溯的一般方法。 回溯求解的问题P，通常要能表达为：对于已知的由n元组(x1,x2,…,x n)组成的一个状态空间E={(x1,x2,…,x n)|x i∈s i,i=1,2,…,n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中s i是分量x i的定义域，且|s i|有限，i=1,2,…,n。称E中满足D的全部约束条件的任一n元组为问题P的一个解。 解问题P的最朴素的方法就是穷举法，上面已经作了介绍，即对E中的所有n元组逐一地检验其是否满足D的全部约束，若满足，则为问题P的一个解。显然，其计算量是相当大的。回溯法实验(0-1背包问题)
回溯法论文-回溯法的分析与应用
回溯法实验(最大团问题)
回溯法实验报告
回溯法实验(n皇后问题)
回溯法实验报告
算法设计与分析：回溯法-实验报告
第一章回溯法(习题二
回溯法实验(n皇后问题)(迭代法)
大学计算机基础第五章
回溯法及其应用
实验报告：回溯法求解N皇后问题(Java实现)
回溯法
算法设计与分析第五章重点
回溯法解0 1背包问题实验报告
回溯法
回溯法(马周游问题)——实验报告
回溯法的效率分析
- 算法_回溯法
- 算法分析与设计[回溯法]
- 算法分析与程序设计动态规划及回溯法解背包问题
- 算法分析复习题目及答案16-12-10
- 算法设计与分析：回溯法-实验报告
- 算法设计与分析第章回溯法
- 最新《算法分析与设计》期末考试复习题纲(完整版)
- 算法分析_回溯法(很不错)
- 算法设计与分析：第8章 回溯法
- 算法设计与分析-第8章-回溯法
- 算法设计与分析-第8章-回溯法PPT课件
- 算法分析与设计之回溯法
- 算法分析与设计实验三：回溯法
- 算法设计与分析-回溯法
- 算法分析与程序设计动态规划及回溯法解01背包问题
- 算法实验报告：回溯法(C语言)
- 算法分析复习题目及答案
- 算法分析期末试题集答案
- 算法设计与分析--回溯法
- 算法设计与分析：回溯法-实验报告