回溯算法实验
中南大学
《算法设计与分析》实验报告
姓名：
专业班级：
学号：
指导教师：
完成日期：20010.1
一．实验名称
回溯算法实验
二．实验目的
1. 掌握回溯算法思想
2. 掌握回溯递归原理
3. 了解回溯法典型问题
三．实验内容
1. 编写一个简单的程序，解决8皇后问题
2. 批处理作业调度
3. 数字全排列问题
四．算法思想分析
1. 编写一个简单的程序，解决8皇后问题
在Ｎ*Ｎ的棋盘上，放置Ｎ个皇后，要求每一横行，每一列，每一对角线上均只能放置一个皇后，求可能的方案及方案数。问题的状态即棋盘的布局状态，状态空间树的根为空棋盘，每个布局的下一步可能布局为该布局结点的子结点；任意两个王后不放在同一行或同一列或同一斜线。因此为了简化状态空间树，采用逐行布局的方式，即每个布局有n个子结点
回溯过程分析：
（1）从空棋盘起，逐行放置棋子。
（2）每在一个布局中放下一个棋子，即推演到一个新的布局。
（3）如果当前行上没有可合法放置棋子的位置，则回溯到上一行，重新布放上一行的棋子。
2. 批处理作业调度
给定n个作业的集合J=(J1, J2, … , Jn)。每一个作业Ji都有两项任务需要分别在2台机器上完成。每一个作业必须先由机器1处理，然后再由机器2处理。作业Ji需要机器i的处理时间为tji，i=1,2, … ,n; j=1,2。对于一个确定的作业调度，设Fji是作业i在机器i上完成处理的时间。则所有作业在机器2上完成处理的时间和成为该作业调度的完成时间和。
批处理作业调度问题要求对于给定的n个作业，制定一个最佳的作业调度方案，使其完成时间和达到最小。
要求输入： a.作业数 b.每个作业完成时间表：
要求输出： a.最佳完成时间 b.最佳调度方案
3. 数字全排列问题
任意给出从1到N的N个连续的自然数，求出这N个自然数的各种全排列。如N=3时，共有以下6种排列方式：123，132，213，231，312，321。
注意：数字不能重复，N由键盘输入（N<=9）。
五．算法源代码及用户屏幕
1. 八皇后问题
（备注：语言：c；编译环境：c-free3.5；共1个文件）
#include
#define N 8
int count=0;
int M[N]={0},L[2*N]={0},R[2*N]={0};
int A[N][N]={0};
void print(int A[N][N]);
void main()
{
int mytry(int i,int M[N],int L[2*N],int R[2*N],int A[N][N]);
int n=mytry(0,M,L,R,A);
cout<<"\n count="< } int mytry(int i,int M[N],int L[2*N],int R[2*N],int A[N][N]) { for(int j=0; j if(!M[j]&&!L[i-j+N]&&!R[i+j]) { A[i][j]=1; M[j]=L[i-j+N]=R[i+j]=1; if(i==N-1) { print(A);cout< } else mytry(i+1,M,L,R,A); A[i][j]=0; M[j]=L[i-j+N]=R[i+j]=0; } return count; } void print(int A[N][N]) { int i,j; for(i=0;i { for(j=0;j cout<<" "< cout< } } 用户屏幕（部分）： 2. 批处理作业调度 （备注：语言JAVA；编译环境：Eclipse SDK 3.2.0；共1个文件）////FlowShop.java //////////////////////////// import java.util.*; public class FlowShop { static int n; static int f1; static int f; static int bestf; static int[][] m; static int[] x; static int[] bestx; static int[] f2; public static void trackback(int i) { if (i == n) { for (int j = 0; j < n; j++) { bestx[j] = x[j]; } bestf = f; } else { for (int j = i; j < n; j++) { f1 += m[x[j]][0]; if (i > 0) { f2[i] = ((f2[i - 1] > f1) ? f2[i - 1] : f1) + m[x[j]][1]; } else { f2[i] = f1 + m[x[j]][1]; } f += f2[i]; if (f < bestf) { swap(x, i, j); trackback(i + 1); swap(x, i, j); } f1 -= m[x[j]][0]; f -= f2[i]; } } } private static void swap(int[] x, int i, int j) { int temp = x[i]; x[i] = x[j]; x[j] = temp; } private static void test() { n = 3; int[][] testm = {{2, 1}, {3, 1}, {2, 3}}; m = testm; int[] testx = {0, 1, 2}; x = testx; bestx = new int[n]; f2 = new int[n]; f1 = 0; f = 0; bestf = Integer.MAX_VALUE; trackback(0); System.out.println(Arrays.toString(bestx)); System.out.println(bestf); } public static void main(String[] args) { test(); System.out.println("Hello World!"); } } 用户屏幕： 3. 数字全排列问题 （备注：语言C，编译器：C-free3.5；共1个文件）#include using namespace std; int num,cont=0; main() { void perm(int* b, int i); int i,n,a[10]; cout<<"enter N :"; cin>>num; for(i=1;i<=num;i++) a[i]=i; cout<<"result:\n"; perm(a,1); cout<<'\n'<<"amount:"< void perm(int* b, int i) { int k,j,temp; if(i==num) { for(k=1;k<=num;k++) cout< cout<<'\t'; cont++; }//ENDIF else { for(j=i;j<=num;j++) { temp=b[i];b[i]=b[j];b[j]=temp; perm(b,i+1); temp=b[i];b[i]=b[j];b[j]=temp; } }//ENDESLE }//END 测试数据：4 用户屏幕： 六．实验过程分析 这几个实验都是回溯法的典型例子，通过实验，对回溯算法的思想和回溯递归的原理有了进一步的了解，算法有点难，通过多次调试，充分理解了其中的核心。 语法方面采用Java和使用Eclipse，类似的强大编译器在写程序的时候可以带来很多的方便，可以提高我们的学习工作效率。 设计四 子集和数的回溯算法 班级通信08-2BF 学号1408230929 姓名杨福 成绩 分 一、 设计目的 1.掌握回溯法解题的基本思想； 2.掌握子集和数问题的回溯算法； 3.进一步掌握子集和数问题的回溯递归算法、迭代算法的基本思想和算法设计方法； 二、 设计内容 a) 任务描述 1）子集和数问题简介 子集和数问题是假定有n 个不同的正数（通常称为权），要求找出这些数中所有事的某和数为M 的组合。 2）设计任务简介 设计、编程、测试求解子集和数问题的回溯算法。 1． 子集和数问题的表示方案 本设计利用大小固定的元组来研究回溯算法，在此情况下，解向量的元素X （i ）取1或0值，它表示是否包含了权数W （i ）. 生成图中任一结点的儿子是很容易的。对于i 级上的一个结点，其左儿子对应于X （i ）=1，右儿子对应于X(i)=0。对于限界函数的 一种简单选择是，当且仅当∑∑+==≥+ n k i k i M i W i X i W 11)()()(时，B(X(1),〃〃〃，X （k ）)=true 。 显然，如果这个条件不满足，X(1),〃〃〃，X （k ）就不能导致一个答案结点。如果假定这些W （i ）一开始就是按非降次序列排列的，那么这些限界函数可以被强化。在这种情 况下，如果M k W i X i W k i >++∑=)1()()(1 ,则X(1),〃〃〃，X （k ）就不能导致一个答案结 点。因此，将要使用的限界函数是B k （X （1），〃〃〃，X （k ））=true,当且仅当 M i W i X i W n k i k i =+∑∑+==11)()()(。 2． 主要数据类型与变量 int M ; // 表示要求得到的子集和； int s; // 表示所选当前元素之前所选的元素和； 算法分析与设计实验报告第五次附加实验 附录： 完整代码（回溯法） //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 补充2 回溯法 解回溯法的深度优先搜索策略 z理解回溯法的深度优先搜索策略。 z掌握用回溯法解题的算法框架 （1）递归回溯 （2）迭代回溯 （3）子集树算法框架 （4）排列树算法框架 通过应用范例学习回溯法的设计策略 z通过应用范例学习回溯法的设计策略。 Sch2-1z Sch2-1 方法概述搜索算法介绍 （1）穷举搜索 （2）盲目搜索 —深度优先(DFS)或回溯搜索( Backtracking); —广度优先搜索( BFS ); (Branch &Bound) —分支限界法(Branch & Bound)；—博弈树搜索( α-βSearch) （3）启发式搜索 —A* 算法和最佳优先( Best-First Search ) —迭代加深的A*算法 —B*AO*SSS*等算法B , AO , SSS 等算法 —Local Search, GA等算法 Sch2-1z Sch2-1 方法概述搜索空间的三种表示： —表序表示：搜索对象用线性表数据结构表示； —显示图表示：搜索对象在搜索前就用图（树）的数据结构表示； —隐式图表示：除了初始结点，其他结点在搜索过程中动态生成。缘于搜索空间大，难以全部存储。 z 搜索效率的思考：随机搜索 —上世纪70年代中期开始，国外一些学者致力于研究随机搜索求解困难的组合问题，将随机过程引入搜索； —选择规则是随机地从可选结点中取一个从而可以从统计角度分析搜选择规则是随机地从可选结点中取一个，从而可以从统计角度分析搜索的平均性能； —随机搜索的一个成功例子是：判定一个很大的数是不是素数，获得了第个多式时算法 第一个多项式时间的算法。 实验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)搜索 数学与计算机学院实验报告 一、实验项目信息 项目名称：回溯法 实验时间： 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 中原工学院信息商务学院 实验报告 实验项目名称回溯划算法的应用 课程名称算法设计与分析 学院(系、部)中原工学院信息商务学院学科专业计算机科学与技术系班级学号计科132班17号姓名程一涵 任课教师邬迎 日期2014年12月9日 实验五回溯算法的应用 一、实验目的 1．掌握回溯算法的基本概念 2．熟练掌握回溯算法解决问题的基本步骤。 3．学会利用回溯算法解决实际问题。 二．问题描述 题目一：N皇后问题 要在n*n的国际象棋棋盘中放n个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。求所有的解要求：键盘输入皇后的个数n (n ≤ 13) 输出有多少种放置方法 输入输出实例： 三．算法设计 首先，确定第一行皇后的位置，再确定第二行的位置，并且要注意不能同行同列同对角线，若是发现有错则返回上一层，继续判断。满足约束条件时，则开始搜索下一个皇后的位置，直到找出问题的解。 四.程序调试及运行结果分析 五.实验总结 通过这次试验，使得我们面对问题时的解题思路变得更加灵活和多变，并且使我们的编写能力稍稍的提高一些。初步了解了回溯算法，回溯算法实际是一个类似枚举的搜索尝试方法，他的主题思想是在搜索尝试的过程中寻找问题的解，当发现已不满足求解条件时，就回溯返回，尝试别的路径。他特别适用于求解那些涉及到寻求一组解的问题或者求满足某些约束条件的最优解的问题。此算法具有结构清晰，容易理解且可读性强等优点，并且通过稍加变通也可以适用于其他类似问题 附录：程序清单（程序过长，可附主要部分） #include 应用数学学院信息安全专业班学号姓名 实验题目回溯算法 实验评分表 实验报告 一、实验目的与要求 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]的个数。 五、总结 这次实验的内容都很有代表性，通过上机操作实践与对问题的思考，让我更深层地领悟到了回溯算法的思想。 回溯算法的基本思路并不难理解，简单来说就是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯法的基本做法是深度优先搜索，是一种组织得井井 回溯法 回溯法也是搜索算法中的一种控制策略，但与枚举法不同的是，它是从初始状态出发，运用题目给出的条件、规则，按照深度优秀搜索的顺序扩展所有可能情况，从中找出满足题意要求的解答。回溯法是求解特殊型计数题或较复杂的枚举题中使用频率最高的一种算法。 一、回溯法的基本思路 何谓回溯法，我们不妨通过一个具体实例来引出回溯法的基本思想及其在计算机上实现的基本方法。【例题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，初始状态显然是一个空棋盘。 此时第一个皇后开始从第一行第一列位置试放，试放的顺序是从左至右、自上而下。每个棋盘由４个数据表征相应的状态信息（见下图）： （××××） 实验四 回溯法 实验目的 1. 掌握回溯法的基本思想方法； 2. 了解适用于用回溯法求解的问题类型，并能设计相应回溯法算法； 3. 掌握回溯法算法复杂性分析方法，分析问题复杂性。 预习与实验要求 1. 预习实验指导书及教材的有关内容，掌握回溯法的基本思想； 2. 严格按照实验内容进行实验，培养良好的算法设计和编程的习惯； 3. 认真听讲，服从安排，独立思考并完成实验。 实验设备与器材 硬件：PC 机 软件：C++或Java 等编程环境 实验原理 回溯法是最常用的解题方法，有“通用的解题法”之称。当要解决的问题有若干可行解时，则可以在包含问题所有解的空间树中，按深度优先的策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，继续查找该结点的兄弟结点，若它的兄弟结点都不包含问题的解，则返回其父结点——这个步骤称为回溯。否则进入一个可能包含解的子树，继续按深度优先的策略进行搜索。这种以深度优先的方式搜索问题的解的算法称为回溯法。它本质上是一种穷举法，但由于在搜索过程中不断略过某些显然不合适的子树，所以搜索的空间大大少于一般的穷举，故它适用于解一些组合数较大的问题。 回溯法也可以形式化地描述如下：假设能够用n 元组()n i x x x x ,,,,,21 表示一个给定问题P 的解，其中i i S x ∈。如果n 元组的子组()i x x x ,,,21 ()n i <满足一定的约束条件，则称为部分解。如果它已经是满足约束条件的部分解，则添加11++∈i i S x 形成新的子组()121,,,,+i i x x x x ，并检查它是否满足约束条件，若仍满足则继续添加22++∈i i S x ，并以此类推。如果所有的11++∈i i S x 都不满足约束条件，那么去掉1+i x ，回溯到i x 的位置，并去掉当前的i x ，另选一个i i S x ∈'，组成新的子组()i x x x ',,,21 ，并判断其是否满足约束条件。如此反复下去，直到得到解或者证明无解为止。 算法分析与设计实验报告第三次附加实验 附录： 完整代码（回溯法） //回溯算法递归回溯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<<"皇后问题的解为："< 八皇后问题的基本策略及其应用 郭洋洋王刚李晴孙佳 （陕西师范大学计算机科学学院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 格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法. 例如图一所示： 【问题】填字游戏 问题描述：在3×3个方格的方阵中要填入数字1到N（N≥10）内的某9个数字，每个方格填一个整数，似的所有相邻两个方格内的两个整数之和为质数。试求出所有满足这个要求的各种数字填法。 可用试探发找到问题的解，即从第一个方格开始，为当前方格寻找一个合理的整数填入，并在当前位置正确填入后，为下一方格寻找可填入的合理整数。如不能为当前方格找到一个合理的可填证书，就要回退到前一方格，调整前一方格的填入数。当第九个方格也填入合理的整数后，就找到了一个解，将该解输出，并调整第九个的填入的整数，寻找下一个解。 为找到一个满足要求的9个数的填法，从还未填一个数开始，按某种顺序（如从小到大的顺序）每次在当前位置填入一个整数，然后检查当前填入的整数是否能满足要求。在满足要求的情况下，继续用同样的方法为下一方格填入整数。如果最近填入的整数不能满足要求，就改变填入的整数。如对当前方格试尽所有可能的整数，都不能满足要求，就得回退到前一方格，并调整前一方格填入的整数。如此重复执行扩展、检查或调整、检查，直到找到一个满足问题要求的解，将解输出。 回溯法找一个解的算法： { int m=0,ok=1; int n=8; do{ if (ok) 扩展; else 调整; ok=检查前m个整数填放的合理性; } while ((!ok||m!=n)&&(m!=0)) if (m!=0) 输出解; else 输出无解报告； } 如果程序要找全部解，则在将找到的解输出后，应继续调整最后位置上填放的整数，试图去找下一个解。相应的算法如下： 回溯法找全部解的算法： { int m=0,ok=1; int n=8; do{ if (ok) { if (m==n) { 输出解； 调整； } else 扩展; } else 调整; ok=检查前m个整数填放的合理性; } while (m!=0); } 实验报告 一、实验名称：回溯法求解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 依次编号） 五、算法实现 对应这个数据结构的算法实现如下： 算法分析与设计实验报告第二次附加实验 ）用可行性约束函数可剪去不满足约束条件 附录： 完整代码（贪心法） //回溯法递归求最优装载问题#include int n, //集装箱数 *x, //当前解 *bestx; //当前最优解 Type *w, //集装箱重量数组 c, //第一艘轮船的载重量 cw, //当前载重量 bestw, //当前最优载重量 r; //剩余集装箱重量 }; template子集和数的回溯算法
回溯法实验(0-1背包问题)
回溯法论文-回溯法的分析与应用
回溯法实验(最大团问题)
回溯搜索算法
回溯法实验报告
回溯法实验报告
回溯算法实验
算法设计与分析：回溯法-实验报告
回溯法
算法分析与设计实验四回溯法
回溯法实验(n皇后问题)(迭代法)
回溯法及其应用
回溯算法实例一
实验报告：回溯法求解N皇后问题(Java实现)
回溯法实验(最优装载)