当前位置:首页 >> 计算机软件及应用 >>

回溯算法的应用


回溯算法的应用

课程名称: 院 系:

算法设计与分析 ************************ ****** ************

学生姓名: 学 号:

专业班级: ***************************** 指导教师: ******

2013 年 12 月 27 日

1

第 1 页 共 19 页

回溯法的应用
摘 要:回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到

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

关键词:回溯法 全排列 最优值 枚举

2

第 2 页 共 19 页





第 1 章 绪论 ...................................................4 1.1 回溯法的背景知识 ........................................4 1.2 回溯法的前景意义 ........................................4 第 2 章 回溯法的理论知识 .......................................5 2.1 问题的解空间树 ..........................................5 2.2 回溯法的一般性描述 ......................................6 第 3 章 n 的全排列 .............................................7 3.1 问题描述 ................................................7 3.2 问题分析 ................................................7 3.3 算法设计 ................................................7 3.4 测试结果与分析 ..........................................9 第 4 章 最优化问题 ............................................11 4.1 问题描述 ...............................................11 4.2 问题分析 ...............................................11 4.3 算法设计 ...............................................11 4.4 测试结果与分析 .........................................14 第 5 章 结论 ..................................................15 参考文献......................................................16 附件..........................................................16

3

第 3 页 共 19 页

第 1 章 绪论

1.1 回溯法的背景知识
回溯算法是尝试搜索算法中最为基本的一种算法,其采用了一种“走不通就掉头” 的思想,作为其控制结构。在递归算法中,其存在的意义是在递归知道可解的最小问题 后,逐步返回原问题的过程。实际上是一个类似于枚举的搜索尝试方法,他的主题思想 是在搜索尝试的过程中寻找问题的解, 当发现不满足条件时就回溯返回, 尝试别的路径。 简单的说就是:从问题的某一种初始状态出发,依次搜寻每一种可能到达的情况, 当走到这条路的“尽头”时, 回过头到上一个情况, 看这个情况是否还有没有走过的路, 依次进行下去,直到遍历完所有的情况。 回溯法实际上是一种深度优先搜索的方式。对于回溯法解决的问题,通常将其解空 间组织成图或者树的形式。对于用回溯法求解的问题,首先要将问题进行适当的转化, 得出状态空间树。这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这 棵树,枚举每种可能的解的情况;从而得出结果。但是,回溯法中通过构造约束函数, 可以大大提升程序效率,因为在深度优先搜索的过程中,不断的将每个解与约束函数进 行对照从而删除一些不可能的解, 这样就不必继续把解的剩余部分列出从而节省部分时 间。

1.2 回溯法的前景意义
在做题时,有时会遇到这样一类题目,它的问题可以分解,但是又不能得出明确的 动态规划或是递归解法,此时可以考虑用回溯法解决此类问题。回溯法的优点在于其程 序结构明确,可读性强,易于理解,而且通过对问题的分析可以大大提高运行效率。 通过运用回溯法,可以解决很多问题,譬如我们所熟知的“八皇后问题” 、 “0/1 背 包问题” ,这只是在教学阶段中的运用,在实际运用中回溯法也能起到很大的作用。 回溯法适用于解决难以归纳一般规律解法的问题,其适用范围广,灵活性大,在解 一些列举方法的问题时尤其可用。但是,其缺点也是明显的,即时间复杂度较大;因此 在采用时我们应该因情况的不同而做出不同的选择。

4

第 4 页 共 19 页

第 2 章 回溯法的理论知识

2.1 问题的解空间树
对于全排列问题。 对 n 位数进行全排列,知道了这个数的位数就知道有多少种排列方法,在 n 位数 中选定一个数为首位就可以进行下面的排列。当 n=4 时,我们要从一个数开始排列,再 进行其他两位数。假设排列从 1 开始出发,则可能的路径如下图 2.1。

图 2.1

选择的路径

活结点:不是叶结点,满足约束条件,使目标函数有所改善,儿子结点有尚未访问 的(可继续搜索下去) 。否则为死结点。 E-结点:扩展结点,当前正在搜索的活结点。 死结点:即如果取了这个结点,将不会有可行解。

5

第 5 页 共 19 页

2.2 回溯法的一般性描述
回溯法的一般描述 可用回溯法求解的问题 P,通常要能表达为:对于已知的由 n 元组(x1,x2,?,xn) 组成的一个状态空间 E={(x1,x2,?,xn)∣xi∈Si ,i=1,2,?,n},给定关于 n 元 组中的一个分量的一个约束集 D,要求 E 中满足 D 的全部约束条件的所有 n 元组。其中 Si 是分量 xi 的定义域,且 |Si| 有限,i=1,2,?,n。我们称 E 中满足 D 的全部约束条 件的任一 n 元组为问题 P 的一个解。 解问题 P 的最朴素的方法就是枚举法, 即对 E 中的所有 n 元组逐一地检测其是否满 足 D 的全部约束,若满足,则为问题 P 的一个解。但显然,其计算量是相当大的。 我们发现,对于许多问题,所给定的约束集 D 具有完备性,即 i 元组(x1,x2,?, xi)满足 D 中仅涉及到 x1,x2,?,xi 的所有约束意味着 j(j<=i)元组(x1,x2,?, xj)一定也满足 D 中仅涉及到 x1,x2,?,xj 的所有约束,i=1,2,?,n。换句话说, 只要存在 0≤j≤n-1,使得(x1,x2,?,xj)违反 D 中仅涉及到 x1,x2,?,xj 的约束 之一,则以(x1,x2,?,xj)为前缀的任何 n 元组(x1,x2,?,xj,xj+1,?,xn)一 定也违反 D 中仅涉及到 x1,x2,?,xi 的一个约束,n≥i≥j。因此,对于约束集 D 具有 完备性的问题 P,一旦检测断定某个 j 元组(x1,x2,?,xj)违反 D 中仅涉及 x1,x2,?, xj 的一个约束,就可以肯定,以(x1,x2,?,xj)为前缀的任何 n 元组(x1,x2,?, xj,xj+1,?,xn)都不会是问题 P 的解,因而就不必去搜索它们、检测它们。回溯法正 是针对这类问题,利用这类问题的上述性质而提出来的比枚举法效率更高的算法。

6

第 6 页 共 19 页

第 3 章 n 的全排列

3.1 问题描述
输出自然数 1 到 n 所有不重复的全排列。

3.2 问题分析
在 n 的全排列是一组 n 元一维向量, (x1,x2,x3,…,xn),搜索空间是: 1<=xi<=n 约束条件很简单,xi 互不相同。 i=1,2,3…,n

3.3 算法设计
1、算法介绍 本例题采用“数组记录状态信息”的方法检查在搜索过程中是否满足约束条件。一 般的方法是用 cheak( )函数进行判断, cheak( )函数中当前元素与前面的元素进行逐个

比较。而在这个算法中用的是 try( void TRY(int k)//找第 k 个数 {int j; for(j=1;j<=n;j++)

)函数,是搜索的过程更加快。

{if(d[j]==0)//判断第 k 个数是否可用 {a[k]=j; d[j]=1;} else continue;//第 k 个数不可用 if(k<n) TRY(k+1);//找第 k+1 个数 else{ p++; output() ; } //输出元素
7 第 7 页 共 19 页

d[a[k]]=0;//将数组中的数设为未使用 } } 具体方式为: 设置 n 个元素的一维数组 d, 在该算法中的一维数组 d 用于记录数组 中的元素的状态(是否被搜索过) ,其中的 n 个元素用来记录数据 1~n 的使用情况,已 使用置 1,未使用置 0。直到所有元素的已使用,输出结果;然后循环进行,直到输出 所有排列。 在该算法中最重要的一个函数就是 d[a[k]]=0,这是回溯的核心,用以上回溯法搜索 算法完成算法的全排列问题的复杂度为 O(n^n),不是最佳算法。如果在算法中运用 try ()函数自身之间的交换,for 循环语句 for(j=t;j<=n;j=j+1),而且 for 循环体中的第二 个 swap()调用,是用来恢复原顺序的,在每次回溯时,都要恢复本次操作前的原始 操作。这个全排列算法的复杂度为 O(n! ) ,其结果可以为搜索排列树所用。 2、流程图

8

第 8 页 共 19 页

开始

输入 n, 初始化数组 d[]为 0

调用递归函数 try 进行 全排列,并输出排列

Try 函数开始 Y

d[j]==0
N N p=p++ output( ) k<n Y TRY(k+1) a[k]=j d[j]=1

d[a[k]]=0

输出排列中 记录的结果

Try 函数结束

结束

3.4 测试结果与分析
(1)测试结果:

9

第 9 页 共 19 页

图 3.1 全排列问题的解

图 3.2 全排列问题的解

(2)对测试结果的分析: 从图 3.1、3.2 中可以看出全排列的排列方法,当 n=2 时有两种排列,当 n=3 时有六 种排列,所以对于 n 的全排列有 n!种排列方法。

10

第 10 页 共 19 页

第 4 章 最优化问题

4.1 问题描述
一个有趣的高精度数据:构造一个尽可能大的数,使其从高到低满足前一位能被 1 整除,前 2 位能被 2 整除,……,前 n 位能被 n 整除。 数学模型:记高精度数据为 a1,a2,…,an,题目很明确有两个要求: (1) a1 能被 1 整除且(a1*10+a2)能被 2 整除且……(a1*10^n-1+a2*10^n-2+…+an)能 被能整除; (2)求最大的这样的数。 a1 能被 1 整除且(a1*10+a2)能被 2 整除且……(a1*10^n-1+a2*10^n-2+…+an)能被 能整除;

4.2 问题分析
此数只能用从高位到低位逐位尝试,失败回溯的算法策略求解,生成的高精度数据 用数组从高位到低位存储,1 号元素开始存储最高位。此数的大小无法估计不妨为数组 开辟 100 个空间。

4.3 算法设计
1、算法介绍 算法中数组 A 位当前求解的高精度数据的暂存处, 数组 B 为当前最大的满足条件的 数。算法的首位 A[1](最高位)从 1 开始枚举。以后各位从 0 开始枚举。所以求解出的满 足条件的数据之间只须比较位数就能确定大小。 n 为当前满足条件的最大数据的位数, i 为当前满足条件数据的位数,当 i>=n 就认为找到了更大的解。当 i>n 不必解释,位数 多数据一定大;i=n 时,由于尝试是由小到大进行的,虽然位数相等,但后来满足条件 的数据一定比前面的大。 (1) 从 A[1]=1 开 始 , 每 增 加 一 位 A[i]( 初 值 为 0) 先 计 算 r=

(A[1]*10^i-1+A[2]*10^i-2+…+A[i]) ,再测试 r=r mod i 是否。 (2) r=0 表示增加第 i 位后,满足条件,与原有满足条件的数(存在数组 B 中)比
11 第 11 页 共 19 页

较,若前者大,则更新后者(数组 B) ,继续增加下一位。 (3) r ! 0 表示增加 i 位不满足整除条件, 接下来算法中并不是继续尝试 A[i]=A[i]+1, 而 是 继 续 尝 试 A[i]=A[i]+i-r , 因 为 若 A[i]=A[i]+i-r<=9 时 ,

(A[1]*10^i-1+A[2]*10^i-2+…+A[i]-r+i)mod i 肯定为 0.这样可以减少尝试次 数。如:17 除 5 余 2,17-2+5 肯定能被 5 整除。 (4) 同理,当 A[i]-r+i>9 时,要进位也不能满足条件。这时,只能将此恢复初值 0 且回退到前一位(i=i-1)尝试 A[i]=A[i]+1,以此类推……。这正是算法中最后 一个 while 循环所做的工作。 (5) 当回溯到 i=1 时,A[1]加 1 开始尝试首位为 2 的情况,最后直到将 A[1]=9 的情 况尝试完毕,算法结束。 主要的函数及功能 while(A[1]<=9) {if(i>=n) { n=i; for(k=1;k<=n;k=k+1) B[k]=A[k];} i=i+1; r=0; for(j=1;j<=i;j=j+1) {r=r*10+A[j]; r=r % i;} if(r!=0) { A[i]=A[i]+i-r; while (A[i]>9 && i>1) {A[i]=0; i=i-1; A[i]=A[i]+i; } 2、流程图 //第 i 位可能的解 //搜索完第 i 位的解,回溯到前一位 //第 i 位是否满足条件 //判断 i 的值 //转存到数组 B 中

12

第 12 页 共 19 页

开始 A 数组首位赋为 1,其它位为 0. i = 1; n = 1; N

A[1] <= 9 ? Y Y i >= n ?

n=i; k = 1; k <= n? Y B[k]=A[k] k++; N N

i ++;r = 0; j = 1;

r = 10 * r +A[j]; r = r %i; j++;

Y

j <= i N N r != 0? Y

A[i] = A[i] + i –r; N

A[i]>9&&i>i Y A[i]=0;i--; A[i]=A[i]+i;

结束

13

第 13 页 共 19 页

4.4 测试结果与分析
(1)测试结果:

图 4.1 最优值

(2)对测试结果的分析: 对输出的数据进行检验,例如 3 能被 1 整除,36 能被 2 整除,360 能被 3 整除, 3608 能被 4 整除??检查完输出结果的所有数位发现满足题意,说明结果是正确的, 该算法使用与此类问题的求解。

14

第 14 页 共 19 页

第 5 章 结论
通过本次课程设计,我对回溯法有了更为深入的理解,学会了用回溯法解决相关问 题的思路。在本次课程设计的过程中,小组遇到了一些问题,比如:开始时,对于深度 优先搜索知识的欠缺,在查找时产生错误;回溯函数放错了地方等。对于其中出现的问 题经过我们的讨论以及查阅相关的资料都得到了解决, 并在讨论的过程中对知识的理解 更为深刻。 回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想 是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。用回溯算法解决问 题的一般步骤为: 1、定义一个解空间,它包含问题的解。 2、利用适于搜索的方法组织解空间。 3、利用深度优先法搜索解空间。 4、利用限界函数避免移动到不可能产生解的子空间。 问题的解空间通常是在搜索问题的解的过程中动态产生的, 这是回溯算法的一个重 要特性。 具体来说:确定了解空间的组织结构后,回溯法就从开始结点(根结点)出发,以 深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点,同时也成为当前的 扩展结点。在当前的扩展结点处,搜索向纵深方向移至一个新结点。这个新结点就成为 一个新的活结点,并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移 动,则当前扩展结点就成为死结点。此时,应往回移动(回溯)至最近的一个活结点处, 并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜 索,直至找到所要求的解或解空间中已没有活结点时为止。

15

第 15 页 共 19 页

参考文献
[1] 算法设计与分析(第二版) 吕国英 主编

附件
全排列问题源程序: #include<stdio.h> int p=0,n,a[100],d[100]; void output() { int j; printf("%d\n",p);//p 为第几组排列 for(j=1;j<=n;j++) printf("%d",a[j]);//输出排列 printf("\n"); } void TRY(int k)//找第 k 个数 { int j; for(j=1;j<=n;j++) { if(d[j]==0)//判断第 k 个数是否可用 { a[k]=j; d[j]=1; } else continue;//第 k 个数不可用

16

第 16 页 共 19 页

if(k<n) TRY(k+1);//找第 k+1 个数 else { p++; output();//输出元素 } d[a[k]]=0;//将数组中的数设为未使用 } } int main() { int j; printf("Input n=");//输入 n scanf("%d",&n); for(j=1;j<=n;j++)//函数完成初始化 d[j]=0; TRY(1); return ; } 最优化问题源程序: #include<stdio.h> int main(){ int A[101],B[101]; int i,j,k,n,r; A[1]=1; for(i=2;i<=100;i=i+1) A[i]=0; n=1; i=1;
17 第 17 页 共 19 页

//置初值:首位为 1,其余为 0

while(A[1]<=9) { if(i>=n) { n=i; for(k=1;k<=n;k=k+1) B[k]=A[k]; } i=i+1; r=0; for(j=1;j<=i;j=j+1) { r=r*10+A[j]; r=r % i; } if(r!=0) { A[i]=A[i]+i-r; while (A[i]>9 && i>1) { A[i]=0; i=i-1; A[i]=A[i]+i; } } } printf("max is:"); for(i>0;i<=n;i++){ printf("%d",B[i]); } }
18 第 18 页 共 19 页

//判断 i 的值

//转存到数组 B 中

//第 i 位是否满足条件

//第 i 位可能的解 //搜索完第 i 位的解,回溯到前一位

指导教师评语: 1、文档: a、内容: 不完整□ □ 完整 合理 □ □ 详细 □

b、方案设计: 较差 c、实现:

非常合理□ 全部实现□ 规范 □

未实现□

部分实现□ 基本规范□

d、文档格式: 不规范□ 2、答辩:

a、未能完全理解题目,答辩情况较差 b、部分理解题目,部分问题回答正确

□ □

c、理解题目较清楚,问题回答基本正确 □ d、理解题目透彻,问题回答流利 □

文档成绩: 答辩成绩: 总 成 绩:

,占总成绩比例: ,占总成绩比例:

40% 60%

指导教师签字: 年 月 日

19

第 19 页 共 19 页


相关文章:
回溯算法实验
回溯算法实验 - 算法设计分析实验: 素数环问题和n皇后问题... 回溯算法实验_计算机软件及应用_IT/计算机_专业资料。算法设计分析实验: 素数环问题和n皇后问题 ...
实验3._回溯法的应用-0-1背包等问题
实验3._回溯法的应用-0-1背包等问题 - 实验 4. 回溯法的应用- 0-1 背包等问题 实验内容 本实验要求基于算法设计与分析的一般过程(即待求解问题的描述、算法...
算法设计与分析--回溯法
算法设计与分析--回溯法 - 回溯算法的应用 课程名称: 院系: 算法设计与分析 学生姓名: 学号: 专业班级: 指导教师: 2013 年 12 月 27 日 回溯算法的应用 ....
01背包问题回溯算法
01背包问题回溯算法 - 假设有 7 个物品,它们的重量和价值如下表所示。若这些物品均不能 被分割,且背包容量 M=150,使用回溯方法求解此背包问题。请写 出状态...
回溯法的应用(实验报告)
回溯法的应用(实验报告) - 算法分析与设计课程实验报告... 年_6_月回溯法的应用 2班 _ 小组实验任务分工_ 实验时间 实验名称 指导老师及职称 2010 1 _日 陈振...
回溯法论文-回溯法的分析与应用
回溯法论文-回溯法的分析与应用 - 算法创新与实践论文 沈阳理工大学 算法实践与创新论文 题目 回溯法的分析与应用 学生姓名: 学号: 学生姓名: 学生姓名: 学号: ...
回溯算法的应用
回溯算法的应用 - 回溯算法的应用 课程名称: 院系: 算法设计与分析 计算机科学与信息工程学院 *** *** 学生姓名: 学号: 专业班级: 计算机科学与技术...
回溯法的效率分析
回溯法的效率分析 - 回溯法概述 与穷举的“笨拙”搜索相比,回溯法则是一种“聪明”的求解效益更高的搜索法。 下面介绍回溯设计及其应用,体会回溯法相对于穷举的...
lab6_回溯算法设计与应用
lab6_回溯算法设计与应用 - 实验六 回溯算法设计与应用 一.基本原理的概括 DFS+剪枝(在状态空间树上作带剪枝的 DFS 搜索)?剪枝:若搜索到某结点,其对应 的部...
回溯算法解决0-1背包问题
回溯算法解决0-1背包问题_计算机软件及应用_IT/计算机_专业资料。《算法分析与设计》 实验报告 2015-2016 年第 2 学期 实验班级: 学生姓名: 学号: 指导老师: ...
更多相关标签: