当前位置:首页 >> 其它课程 >>

一种回溯算法入门教学思路


一种回溯算法入门教学思路
摘 要:回溯法是信息学奥赛中学生必须掌握的重要算法思想,对 如何进行回溯法入门教学提出了一种新的思路。将基本回溯问题区 分为子集和排列两类问题,调整传统教学中的算法步骤为:(1)确定 问题类型;(2)写出固定回溯算法;(3)根据问题进行优化。避免了回 溯法教学中相对模糊的概念和步骤,有利于学生掌握回溯法的基本 思想。 关键词:信息学奥赛 1 两类基本问题 回溯算法的本质就是深度优先遍历解空间树,根据解空间树生成 方式的不同可以将问题分为子集问题和排列问题两类。 1.1 子集问题 给定 n 个元素 r1,?rn,生成所有可能的子集,稍作推广:第 i 个元 素的选择范围为 s[1..ni],算法如下: procedure subset(r:元素数组,i:integer);//r[i..n]所有子集 var pos:integer;//循环变量 begin if i>n then//递归边界,已生成 1 子集 ?? else 回溯算法 入门教学 教学思路

for pos:=1 to ni do begin//第 i 个元素有 ni 个选择 r[i]:=s[pos]; subset(r,i+1);//递归 end; end; 这看上去和排列问题很像,还可把排列问题转成子集问题,但会导 致问题复杂化,不利于对算法的掌握。 1.2 排列问题 给定一组数据元素 r1,?rn,生成可能的排列。很多实现算法采用 访问数组记录选择情况,这需要反复检查原始是否已被选择,大大 影响算法效率。合理的是通过交换元素位置来实现: procedure perm(r:元素数组,i:integer);//r[i..n]全排列 var pos:integer;//循环变量 begin if i>n then//递归边界,已生成 1 全排列 ?? else for pos:=i to n do begin//可以放在位置 i 的元素 swap(r[i],r[pos]);//放到位置 i 上 perm(r,i+1,n);//递归调用

swap(r[i],r[pos]);//恢复 r[i..n]原状 end; end; 2 回溯解题步骤 回溯法解题步骤通常为 3 步[2]:(1)定义解空间包含问题的解;(2) 适合的方式组织解空间;(3)构造约束函数,搜索解空间,用约束函 数杀死不可能产生解的节点。其中第(1)、(2)步描述含糊,又将这 两个密切相关步骤割裂开,学生很容易变得困惑;且活结点概念也 较难理解。 本文提出解题步骤为:(1)确定是排列问题还是子集问题;(2)用对 应算法生成所有可能解;(3)添加约束、剪枝进行优化。 2.1 确定类型 首先抛开题目约束和目标,将问题简化抓本质:变的是元素还是位 置?下面通过 3 个典型例子说明: 例 1:0-1 背包问题:给出装背包方案,使得背包物品总价值最大。 不关心物品装入顺序,因此是子集类。 例 2:八皇后问题:n*n 的棋盘上放 n 个皇后,使皇后间互不攻击。 看上去和位置有关,但交换两个皇后的位置不产生新方案,因此也 是子集问题。 例 3:哈密尔顿回路问题:选一条从驻地出发,经过每个城市一遍最 后回到驻地的路线,使总旅费最小。显然是排列问题。

一般而言,难判定的往往是子集问题。 2.2 所有可能解。 问题类型决定解空间表示法:通常是一维数组。但元素取值范围要 根据题目灵活设计。 生成所有可能解,直接套用前述 perm 或 subset 即可: 例 1:r[i]=0 或 1 表示第 i 件物品是否选中。 例 2:r[i]=1,?,n 表示第 i 列皇后放在第 r[i]行。 例 3:r[i]=1,?,n,表示第 i 次访问城市 r[i]。r 初值为 [1,2,?,n]。 注意:从例中看到子集问题每个元素取值范围不一定通过数组给 定,可以采用灵活手段来生成。如,棋盘“马步”有关问题马前进的 下一位置无法事先确定,要根据当前位置结合马步动态生成。这也 是子集方法解决排列问题的途径。但入门教学时建议不要涉及。 2.3 优化算法 生成所有可能解后,只要检查每个可能的解是否满足题目要求即 可,但这样算法效率很低,因此需要优化。基本思想是:尽量提前发 现正在生成的可能解是否符合要求。通过两个手段:(1)根据题意约 束;(2)根据目标剪枝。这样入门时可绕过“活节点”“扩展结点” 、 等较抽象、复杂的概念。 添加约束就是在递归调用前,添加 if 语句检查当前选择是否符合 题目限定,否则无需递归:

例 1:背包物品总量不能超过容量。设变量 cw 记录当前背包容量, 只有背包容量不超限额时才递归。 例 2:需考虑新加皇后和已有皇后间是否冲突。可单独写检查函数 返回新加皇后是否满足约束,递归前调用该函数检查。 例 3:任两城市间互通,故无约束。 剪枝用于求最优解时,也在递归前用 if 检查当前选择是否不可能 优于已知最优解,若是则无需递归。为此,需进行两点修改:(1)到达 递归边界时记录当前最优解;(2)当前选定后计算需付出的最少代 价。前者可用全局变量来记录;后者可设立变量 cost,例如: 例 1:设当前最高价值为 mv,背包物品总价值 cv,剩余尚未决定的所 有物品总价值 rv,则若剪枝检查有 cv+rv=mc,显然无须递归。为此 设任两城市 i 和 j 间的旅费为 c[i][j],初始化 mc 为-1(表无穷 大),cc 为 0。 在递归边界检查是否需更新 mc。 递归前后同样需更新、 恢复 cc 的值,并在递归前进行该剪枝检查。 3 结语 本文提出的回溯法教学思路采用了相对明确、简单的解题步骤,有 一定局限性,因此只适用于入门教学。但学生一旦掌握回溯算法的 基本思想后,可进一步引导其思考如何突破排列问题和子集问题的 局限性。突破局限的关键在于如何生成当前所有可能的选择,这要 根据具体问题进行。显然,不论在什么情况下,本文提出的解题框架 仍是非常有用的。

参考文献 [1] 杨兴旺.基于回溯法的排课算法[j].电脑知识与技 术,2009(19):5196~5197,5209. [2] 黄丽华.在信息学奥赛中“回溯算法”教学的探究[j].福 建电脑,2005(8):158~159.


赞助商链接
相关文章:
回溯算法原理和几个常用的算法实例
回溯算法思想:回溯(backtracking)是一种系统地搜索问题解答的方法。为了实现回溯, 首先需要为问题定义一个解空间(solution space),这个空间必须至少包含 问题的一个...
回溯算法实验
这种方法适用于解一些组合数相当大的问题。而回溯的指导思想就 是走不通,就掉头。所以我也感觉到这是一种很高效的算法,但在本次实验中我 还不能够熟练的应用,...
算法设计与分析--回溯法
回溯算法的应用 课程名称: 院系: 算法设计与分析 ...实际上是一个类似于枚举的搜索尝 试方法,他的主题...“0/1 背 包问题” ,这只是在教学阶段中的运用,...
算法--回溯法
回溯法 实验学时 2 指导教师 实验时间 张怡婷 2017-5-24 一、 实验目的和任务目的:学习编程实现深度优先搜索状态空间树求解实际问题的方法,着重体会求解 第一个...
回溯算法的实验报告
算法分析 姓名 何星佑 学号 20154340220 专业 树媒 班级 2 地点 教师 罗江琴 一、 实验目的: 通过分析求符号三角形问题的回溯法并编程实现, 掌握回溯法算法...
实验六 回溯算法
实验六 回溯算法(2 学时)一、实验目的与要求 1、掌握装载问题的回溯算法; 2、初步掌握回溯算法; 二、实验题 有一批共 n 集装箱要装上 2 艘载重量分别为...
算法设计与分析--回溯法
1 页共 20 页 回溯算法的应用摘 要:回溯法是一...实际上是一个类似于枚举的搜索尝 试方法,他的主题...“0/1 背 包问题” ,这只是在教学阶段中的运用,...
搜索与回溯算法
二、实现要点由于回溯法一种搜索方法,而且是一种深度优先式的搜索算法,在搜索过程中,前进和回退交织进 行,因而,必须有适当的手段和机制来已经走过的状态,以便...
算法设计与分析-回溯法
实验报告 -1- 一 实验目的和要求填空,使得每一行,一列,每一个 3x3 的方格...具体的解决方法、还没有解决的问题、实验 收获等)回溯法能够以较快的速度将...
回溯算法讲解
回溯算法与递归算法实现方法完全相同, 所用的自定义...1、4,这时,再展开第 3 个皇后,可放在第 三 2 ...教学总结精品范文 小学五年级英语教学工作总结 大学教师...
更多相关标签: