2011-程序设计-12-函数-4-递归与回溯

算法实验 递归回溯解八皇后问题

深圳大学实验报告 课程名称：算法分析与复杂性理论 实验项目名称：八皇后问题 学院：计算机与软件学院 专业：软件工程 指导教师：杨烜 报告人：学号：班级：15级软工学术型实验时间：2015-12-08 实验报告提交时间：2015-12-09 教务部制

一．实验目的 1.掌握选回溯法设计思想。 2.掌握八皇后问题的回溯法解法。 二．实验步骤与结果 实验总体思路： 根据实验要求，通过switch选择八皇后求解模块以及测试数据模块操作，其中八皇后模块调用摆放皇后函数模块，摆放皇后模块中调用判断模块。测试数据模块主要调用判断模块进行判断，完成测试。用一维数组保存每行摆放皇后的位置，根据回溯法的思想递归讨论该行的列位置上能否放置皇后，由判断函数Judge()判断，若不能放置则检查该行下一个位置。相应结果和过程如下所示（代码和结果如下图所示）。 回溯法的实现及实验结果： 1、判断函数 代码1： procedure BTrack_Queen(n) //如果一个皇后能放在第K行和X(k)列，则返回true，否则返回false。 global X(1:k);integer i,k i←1 while i0 do X(k)←X(k)+1 //移到下一个位置 while X(k)<=n and not Judge(k) do //判断能否放置皇后 X(k)←X(k)+1 repeat if X(k)<=n //找到一个位置 then if k=n //是一个完整的解吗

八皇后之递归算法、回溯算法、穷举算法

VAR CONT,I:INTEGER; A:ARRAY[1..N] OF BYTE;{存放正确的一组解} C:ARRAY[1..N] OF BOOLEAN;{存放某一列放皇后的情况，用于判断是否有同列的情况} L:ARRAY[1-N..N-1] OF BOOLEAN;{存放某一斜线上放皇后的情况，用于判断是否有同斜线的情况；斜线的方向为＼} R:ARRAY[2..2*N] OF BOOLEAN;{存放某一斜线上放皇后的情况，用于判断是否有同斜线的情况；斜线的方向为／} PROCEDURE PR; VAR I:INTEGER; BEGIN FOR I:=1 TO N DO WRITE(A[I]:4); INC(CONT); WRITELN(' CONT=',CONT); END; PROCEDURE TRY(I:INTEGER); VAR J:INTEGER; PROCEDURE ERASE(I:INTEGER); BEGIN C[J]:=TRUE; L[I-J]:=TRUE; R[I+J]:=TRUE; END; BEGIN FOR J:=1 TO N DO

IF C[J] AND L[I-J] AND R[I+J] THEN BEGIN A[I]:=J; C[J]:=FALSE; L[I-J]:=FALSE; R[I+J]:=FALSE; IF I

回溯法论文-回溯法的分析与应用

沈阳理工大学算法实践与创新论文

摘要 对于计算机科学来说，算法的概念是至关重要的，算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。为了更加的了解算法，本篇论文中，我们先研究一个算法---回溯法。 回溯法是一种常用的重要的基本设计方法。它的基本做法是在可能的范围之内搜索，适于解一些组合数相当大的问题。圆排列描述的是在给定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)

回溯法与分支限界法的分析与比较

回溯法与分支限界法的分析与比较 摘要：通过对回溯法与分支限界法的简要介绍，进一步分析和比较这两种算法在求解问题时的差异，并通过具体的应用来说明两种算法的应用场景及侧重点。 关键词：回溯法分支限界法n后问题布线问题 1、引言 1.1回溯法 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。这种以深度优先方式系统搜索问题解的算法称为回溯法。 1.2分支限界法 分支限界法是以广度优先或以最小耗费优先的方式搜索解空间树，在每一个活结点处，计算一个函数值，并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解，这种方法称为分支限界法。 2、回溯法的基本思想 用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少应包含问题的一个解。之后还应将解空间很好的组织起来，使得能用回溯法方便的搜索整个解空间。在组织解空间时常用到两种典型的解空间树，即子集树和排列树。确定了解空间的组织结构后，回溯法从开始结点出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法以这种工作方式递归的在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。 3、分支限界法的基本思想 用分支限界法解问题时，同样也应明确定义问题的解空间。之后还应将解空间很好的组织起来。分支限界法也有两种组织解空间的方法，即队列式分支限界法和优先队列式分支限界法。两者的区别在于：队列式分支限界法按照队列先进先出的原则选取下一个节点为扩展节点，而优先队列式分支限界法按照优先队列

枚举-递归-回溯

一、暴力求解法（枚举法/ 穷举法） 概念：什么是枚举法？ 在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这结论是可靠的，这种归纳方法叫做枚举法。即，把所要解决问题的所有可能性都列举出来，一一试验。 枚举应用简单举例：求1~100之间的素数；求水仙花数；鸡兔同笼问题；百元买百鸡问题；整数（分数）拆分问题；排列问题…… 枚举算法因为要列举问题的所有可能的答案，所有它具备以下几个特点： 1、得到的结果肯定是正确的； 2、可能做了很多的无用功，浪费了宝贵的时间，效率低下。 3、通常会涉及到求极值（如最大，最小，最重等）。 4、数据量大的话，可能会造成时间崩溃。 采用枚举算法解题的基本思路： （1）确定枚举对象、枚举范围和判定条件； （2）一一枚举可能的解，验证是否是问题的解 下面我们就从枚举算法的的优化、枚举对象的选择以及判定条件的确定，这三个方面来探讨如何用枚举法解题。 例1：百元买百鸡问题：有一个人有一百块钱，打算买一百只鸡。到市场一看，大鸡三块钱一只，小鸡一块钱三只，不大不小的鸡两块钱一只。现在，请你编一程序，帮他计划一下，怎么样买法，才能刚好用一百块钱买一百只鸡？ 算法分析： 我们以三种鸡的个数为枚举对象（分别设为x,y,z），以三种鸡的总数（x+y+z）和买鸡用去的钱的总数(x*3+y*2+z/3)为判定条件，穷举各种鸡的个数。 （1）基本算法： for (x=0;x<=100;x++) for (y=0;y<=100;y++) for(z=0;z<=100;z++) if(x+y+z==100 && z%3==0 && x*3+y*2+z/3==100)输出x,y,z （2）优化算法：只需要枚举2种鸡x（x<=33）和y（y<=50)，第3种根据约束条件100-x-y可得:

算法设计与分析：回溯法-实验报告

应用数学学院信息安全专业班学号姓名 实验题目回溯算法 实验评分表

实验报告 一、实验目的与要求 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优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 ○2缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 边界条件与递归方程是递归函数的二个要素 应用分治法的两个前提是问题的可分性和解的可归并性 以比较为基础的排序算法的最坏倩况时间复杂性下界为0(n·log2n)。 回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。 舍伍德算法设计的基本思想: 设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为 这显然不能排除存在x∈Xn使得的可能性。希望获得一个随机化算法B，使得对问题的输入规模为n的每一个实例均有 拉斯维加斯( Las Vegas )算法的基本思想: 设p(x)是对输入x调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x均有p(x)>0。 设t(x)是算法obstinate找到具体实例x的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x求解成功或求解失败所需的平均时间，则有： 解此方程可得：

蒙特卡罗(Monte Carlo)算法的基本思想: 设p是一个实数，且1/2

回溯搜索算法

补充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年代中期开始，国外一些学者致力于研究随机搜索求解困难的组合问题，将随机过程引入搜索； —选择规则是随机地从可选结点中取一个从而可以从统计角度分析搜选择规则是随机地从可选结点中取一个，从而可以从统计角度分析搜索的平均性能； —随机搜索的一个成功例子是：判定一个很大的数是不是素数，获得了第个多式时算法 第一个多项式时间的算法。

递归算法的优缺点

递归算法的优缺点： ○ 1优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 ○2缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 边界条件与递归方程是递归函数的二个要素 应用分治法的两个前提是问题的可分性和解的可归并性 以比较为基础的排序算法的最坏倩况时间复杂性下界为0(n·log2n)。 回溯法以深度优先的方式搜索解空间树T ，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T 。 舍伍德算法设计的基本思想: 设A 是一个确定性算法，当它的输入实例为x 时所需的计算时间记为tA(x)。设Xn 是算法A 的输入规模为n 的实例的全体，则当问题的输入规模为n 时，算法A 所需的平均时间为 这显然不能排除存在x ∈Xn B ，使得对问题的输入规模为n 拉斯维加斯( Las Vegas )算法的基本思想: 设p(x) 是对输入x 调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x 均有p(x)>0。 设t(x)是算法obstinate 找到具体实例x 的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x 蒙特卡罗(Monte Carlo)算法的基本思想: 设p 是一个实数，且1/2

搜索与回溯算法介绍

搜索与回溯算法介绍 一、概述： 计算机常用算法大致有两大类：一类叫蛮干算法，一类叫贪心算法。前者常使用的手段就是搜索，对全部解空间进行地毯式搜索，直到找到指定解或最优解。后者在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解。 二、搜索与回溯： 这里着重介绍搜索与回溯。当很多问题无法根据某种确定的计算法则来求解时可以利用搜索与回溯的技术求解。回溯是搜索算法中既带有系统性又带有跳跃性的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索。在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，然后继续向前探索，如此反复进行，直至得到解或证明无解。如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进。如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。 【建立解空间】 问题的解应该如何描述，如何建立呢？问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。借助图论的思想，可以用图来描述，图的定义为G，由顶点集和边集构成，顶点即实实在在的数据、对象，而边可以抽象为关系，即顶点间的关系，这种关系不一定非要在数据结构上表现出来，用数据结构的语言来描述，如果关系是一对一，则为线性表，如果关系是一对多，则为树，如果关系是多对多，则为图，如果完全没有关系，则为集合。但在数据结构中这种关系不一定非要在数据的存储性质上一开始就表现出来，譬如，你可以用一个数组表示一个线性表，也可以表示完全二叉树，同样也可以用邻接表表示一个图，对于关系的描述不是数据结构本身的描述，而是算法的描述，正如数据结构是离不开特定的算法一样，不可分开单独而谈。 确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向

回溯法

第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时，其解空间是：

回溯法

回溯法 回溯法也是搜索算法中的一种控制策略，但与枚举法不同的是，它是从初始状态出发，运用题目给出的条件、规则，按照深度优秀搜索的顺序扩展所有可能情况，从中找出满足题意要求的解答。回溯法是求解特殊型计数题或较复杂的枚举题中使用频率最高的一种算法。 一、回溯法的基本思路 何谓回溯法，我们不妨通过一个具体实例来引出回溯法的基本思想及其在计算机上实现的基本方法。【例题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，初始状态显然是一个空棋盘。 此时第一个皇后开始从第一行第一列位置试放，试放的顺序是从左至右、自上而下。每个棋盘由４个数据表征相应的状态信息（见下图）： （××××）

回溯法的效率分析

回溯法概述 与穷举的“笨拙”搜索相比，回溯法则是一种“聪明”的求解效益更高的搜索法。 下面介绍回溯设计及其应用，体会回溯法相对于穷举的特点与优势。 回溯的概念 有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往使用回溯法。 回溯法是一种试探求解的方法：通过对问题的归纳分析，找出求解问题的一个线索，沿着这一线索往前试探，若试探成功，即得到解；若试探失败，就逐步往回退，换其他路线再往前试探。因此，回溯法可以形象地概括为“向前走，碰壁回头”。 回溯法的基本做法是试探搜索，是一种组织得井井有条的、能避免一些不必要搜索的穷举式搜索法。回溯法在问题的解空间树中，从根结点出发搜索解空间树，搜索至解空间树的任意一点，先判断该结点是否包含问题的解；如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其父结点回溯；否则，进入该子树，继续搜索。 从解的角度理解，回溯法将问题的候选解按某种顺序进行枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。倘若当前候选解除了不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。 与穷举法相比，回溯法的“聪明”之处在于能适时“回头”，若再往前走不可能得到解，就回溯，退一步另找线路，这样可省去大量的无效操作。因此，回溯与穷举相比，回溯更适宜于量比较大，候选解比较多的问题。 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的一个解。显然，其计算量是相当大的。

递推-递归-分治-回溯

递推算法 在程序编辑过程中，我们可能会遇到这样一类问题，出题者告诉你数列的前几个数，或通过计算机获取了数列的前几个数，要求编程者求出第N项数或所有的数列元素（如果可以枚举的话），或求前N项元素之和。这种从已知数据入手，寻找规则，推导出后面的数的算法，称这递推算法。 典型的递推算法的例子有整数的阶乘，1，2，6，24，120…，a[n]=a[n-1]*n(a[1]=1)；前面学过的2n，a[n]=a[n-1]*2(a[1]=1)，菲波拉契数列：1，2，3，5，8，13…，a[n]=a[n-1]+a[n-2](a[1]=1,a[2]=2)等等。 在处理递推问题时，我们有时遇到的递推关系是十分明显的，简单地写出递推关系式，就可以逐项递推，即由第i项推出第i+1项，我们称其为显示递推关系。但有的递推关系，要经过仔细观察，甚至要借助一些技巧，才能看出它们之间的关系，我们称其为隐式的递推关系。 下面我们来分析一些例题，掌握一些简单的递推关系。 例如阶梯问题：题目的意思是：有N级阶梯，人可以一步走上一级，也可以一步走两级，求人从阶梯底走到顶端可以有多少种不同的走法。 这是一个隐式的递推关系，如果编程者不能找出这个递推关系，可能就无法做出这题来。我们来分析一下：走上第一级的方法只有一种，走上第二级的方法却有两种（两次走一级或一次走两级），走上第三级的走法，应该是走上第一级的方法和走上第二级的走法之和（因从第一级和第二级，都可以经一步走至第三级），推广到走上第i级，是走上第i-1级的走法与走上第i-2级的走法之和。很明显，这是一个菲波拉契数列。到这里，读者应能很熟练地写出这个程序。在以后的程序习题中，我们可能还会遇到菲波拉契数列变形以后的结果：如f(i)=f(i-1)+2f(i-2)，或f(i)=f(i-1)+f(i-2)+f(i-3)等。 我们再来分析一下尼科梅彻斯定理。定理内容是：任何一个整数的立方都可以写成一串连续的奇数和，如：43=13+15+17+19=64。 从键盘输入一个整数n，要求写出其相应的连续奇数。 我们不妨从简单入手，枚举几个较小的数据： 13=1 23=3+5 33=7+9+11 43=13+15+17+19 53=21+23+25+27+29 根据上面的例子，读者不难看出： （1）输入为n时，输出应有n项。 （2）输入分别为1，2，3…时，则输出恰好为连续奇数，1，3，5，7，9，11…即下一行的首项比上一行的末项大2。 经上面的分析，原本看不出递推关系的问题，呈现出递推关系。在趣的是，这个例子的递推过程，可以有多种算法。 算法一：将所有奇数逐项例举出来，然后将其分段，即: 1; 3 5; 7 9 11; 13 15 17 19; 21… 1 2 3 4 5… 算法二、设输入为n时的输出第一项为a[n]，则a[n]=a[n-1]-n+1; 于是我们推出首项后，则输出为a[n]+a[n]+2+…+a[n]+2(n-1) 算法三、进一步总结，不难得出，若输入为n时，首项a[n]=n2-n+1，其余同算法二。下面我们来分析两个与动物有关的趣题。

回溯算法的应用

回溯算法的应用 课程名称：算法设计与分析 院系：************************ 学生姓名：****** 学号：************ 专业班级：***************************** 指导教师：****** 2013年12月27日

回溯法的应用 摘要：回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 回溯法，其意义是在递归直到可解的最小问题后，逐步返回原问题的过程。而这里所说的回溯算法实际是一个类似枚举的搜索尝试方法，它的主题思想是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。 回溯算法是尝试搜索算法中最为基本的一种算法，其采用了一种“走不通就掉头”的思想，作为其控制结构。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。 全排列和求最优解问题是比较经典的问题，我们可以采用多种算法去求解此问题，比如动态规划法、分支限界法、回溯法。在这里我们采用回溯法来解决这个问题。 关键词：回溯法全排列最优值枚举

回溯算法的一些例题

回溯算法 搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。 递归回溯法算法框架[一] procedure Try(k:integer); begin for i:=1 to 算符种数 Do if 满足条件 then begin 保存结果 if 到目的地 then 输出解 else Try(k+1); 恢复：保存结果之前的状态{回溯一步} end; end; 递归回溯法算法框架[二] procedure Try(k:integer); begin if 到目的地 then 输出解 else for i:=1 to 算符种数 Do if 满足条件 then begin 保存结果 Try(k+1); end; end;

例 1：素数环：把从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。【算法分析】非常明显，这是一道回溯的题目。从1 开始，每个空位有 20（19）种可能，只要填进去的数合法：与前面的数不相同；与左边相邻的数的和是一个素数。第 20个数还要判断和第1个数的和是否素数。 〖算法流程〗1、数据初始化； 2、递归填数： 判断第J种可能是否合法； A、如果合法：填数；判断是否到达目标（20个已填完）：是，打印结果；不是，递归填下一个； B、如果不合法：选择下一种可能； 【参考程序】 program z74;框架[一] var a:array[0..20]of byte; b:array[0..20]of boolean; total:integer; function pd(x,y:byte):boolean; var k,i:byte; begin k:=2; i:=x+y; pd:=false; while (k<=trunc(sqrt(i)))and(i mod k<>0) do inc(k); if k>trunc(sqrt(i)) then pd:=true; end; procedure print; var j:byte; begin inc(total);write('<',total,'>:'); for j:=1 to 20 do write(a[j],' '); writeln; end; procedure try(t:byte); var i:byte; begin for i:=1 to 20 do if pd(a[t-1],i)and b[i] then begin a[t]:=i; b[i]:=false; if t=20 then begin if pd(a[20],a[1]) then print;end

回溯算法实验报告

本科学生综合性实验报告 姓名刘春云学号0103918＿＿＿ 专业软件工程班级＿软件103班＿＿ 实验项目名称＿n皇后问题的回溯算法实验 指导教师及职称＿赵晓平＿＿教授＿＿ 开课学期2011 至＿2012 学年＿三＿学期 上课时间2012 年 2 月20 日

学生实验报告（3） 一、问题描述 n后问题是指在一个n*n的棋盘上放置n个皇后，使得它们彼此不受攻击。而一个皇后可以攻击与它处在同一行或同一列或同一斜线上的任何棋子。故n后问题可以理解为：在一个n*n的棋盘内放置n个皇后，使任意两个皇后不处在同一行或同一列或同一斜线上。 在这个问题中，我用了一个n*n的数组来存储棋盘，由于n后问题的典型是8皇后问题，所以我做的是8皇后问题。得出的解以以下形式出现在文件中：8皇后问题 第1个解为: oxxxxxxx xxxxoxxx xxxxxxxo xxxxxoxx xxoxxxxx xxxxxxox xoxxxxxx xxxoxxxx 二、解题思路 根据条件可以知道皇后肯定是每行都有且只有一个所以我们创建一个数组c[cur]让数组角标表示八皇后的行，用这个角标对应的数组值来确定这个皇后在这行的那一列。 我用递归来做这问题。要求皇后所在的位置必须和其他皇后的位置不在同一行、列和斜线上，所以这个限定条件可以用来判断一个皇后是否能放在当前位置。既然是用递归来解决问题那就要把这个问题分成一个个相同的小问题来实现。 这小问题是什么呢？不难发现我们要在n*n的方格里放好n个皇后那我们就要知道在n（列）*n-1（行）是怎么放的，再有我们事先写好的判断条件放好最后行就搞定了。以此类推我们要知道8*7的怎么方的我们就要知道8*6是怎么样的就好了。所以我们是以一行怎么放作为一个单元，每一行有n个位置可以放，每一个位置我

用递归回溯解决迷宫问题

扬州大学试题纸 （2015－2016 学年第二学期） ACM竞赛辅导论文报告 学院：信息工程学院 班级：计科1302 学号：131404211 姓名：盛晓伟 指导老师：徐晓华

用递归回溯解决迷宫问题 盛晓伟（扬州大学计算机科学与技术系扬州225100） SHENG Xiao-Wei, School of Information Science and Technology, Yangzhou University, Yangzhou 225100, China) For many practical problems, the solution is to move along a series of orderly decision-making points, each of the choices made at each decision point will lead along a path. If the choice is correct, the problem will be resolved. On the other hand, if you go into a dead end or find that the choice at a certain point is wrong, then you must return to the previous decision point and try another route.. This algorithm is called backtracking algorithm.. If the backtracking algorithm is considered as a continuous process of trying to solve the problem, the process seems to be iterative. However, for most of this problem, the recursive method is more easily solved. The recursive principle point of view is very simple; for a backtracking problem, if and only if at least a word problem solutions can be solved, and these subproblems generated source in the initial of each a possible choice. Key words: backtracking algorithm: Recursive; Iterative；Maze 摘要：对许多实际问题而言，其解决过程就是沿着一系列有序的决策点前进，在每个决策点所做的每一个选择都会导向沿着某一路径前行。如果选择是正确的，问题将得到解决。从另一方面讲，如果走进了死胡同，或者发现在某个决策点的选择是错误的，那么必须返回到以前的决策点，尝试另一条路径。这中方式的算法称为回溯算法。 如果吧回溯算法看成是一个不断地进行各种尝试直至解决问题的过程，那么这个过程似乎具有迭代性。然而，对大多数这种形式的问题，采用递归方法更容易解决。采用递归原理的着眼点很简单；对于一个回溯问题而言，当且仅当至少有一个字问题有了解决方案后才可能得到解

实验四 回溯法的应用------跳马算法

实验四回溯法的应用------跳马算法 学号：012124345 姓名：梁文耀 一、实验目的 掌握使用回溯法求解问题的基本思路；理解其特点。 二、实验思想 算法的基本思路是： 定义结构体：struct PLACE{int x, int y}表示棋盘上的位置。 依题意，马每跳一步之后都可以从七个不同的方向选择下一步的跳马，当然，前提是跳的这一步在棋盘内且它前面的任何一步都没跳到这一格子上（限界），就可以认为这一步跳成功，否则跳马不成功。若跳马不成功，则找下一个方向尝试跳马，若七个方向都跳马不成功，则回溯。 假设棋盘的行（列）数为n。 在本算法中设置这样一个全局数组：c[8][2]={{2,1},{2,-1},{1,2},{1,-2},{-2,1},{-2,-1},{-1,2},{-1,-2}}; 来记录跳马的八个方向。 三、程序分析（主要算法） int map[12][12], status[12][12], kp; int start,finsh; int c[8][2]={{2,1},{2,-1},{1,2},{1,-2}, {-2,1},{-2,-1},{-1,2},{-1,-2}};

int flag = 0; void prt(int a[][12]) /* 打印棋盘状态*/ { int i,j; printf("\n"); for (i=2;i<=9;i++) { for (j=2;j<=9;j++) printf("%4d",a[i][j]); printf("\n"); } } void status2(void) /* 计算棋盘各点条件数*/ { int i,j,k,i2,j2,kz; for(i=0;i<12;i++) for(j=0;j<12;j++) status[i][j]=100; for(i=2;i<=9;i++) for(j=2;j<=9;j++) { kz=0;