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

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


一种回溯算法入门教学思路
摘 要:回溯法是信息学奥赛中学生必须掌握的重要算法思想,对 如何进行回溯法入门教学提出了一种新的思路。将基本回溯问题区 分为子集和排列两类问题,调整传统教学中的算法步骤为:(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.


相关文章:
一种回溯算法入门教学思路.doc
一种回溯算法入门教学思路 - 一种回溯算法入门教学思路 摘要:回溯法是信息学奥赛
回溯算法_图文.ppt
回溯算法2016冬令营第4讲 1 ?迷宫游戏 入口 回溯 回溯 回溯 回溯 出口 搜索算法对某些问题建立数学模型时,即使有一 定的数学模型,但采用数学方法解决有一定 ...
回溯算法入门及应用.doc
一、回溯算法的定义: 回溯算法也叫试探法,它是一种系统地搜索问题的解的方法...一种回溯算法入门教学思... 6页 免费 回溯算法设计与应用 4页 3下载券 ...
回溯算法备课用_图文.ppt
一、回溯的概念 ? 回溯算法一种有条不紊的搜索问题答案的 方法,是一种能避免不
基于回溯法的排课算法.pdf
该文利用回溯算法来解决排课问题,方法简单,易于软件实现。 关键词:回溯算法;排...让一个教师连续完成多个教学工作; 7) 一般在某个特定的时间段不要安排教学...
简单回溯法.ppt
简单回溯法_电脑基础知识_IT/计算机_专业资料。简单回溯法教案朱全民 搜索的本质...在N个皇后未放置完成前,摆放第i个皇后 和第i+1个皇后的试探方法是相同的,...
Pascal回溯算法入门_图文.ppt
这种不断“回溯”寻找 解的方法, 称作“ 回溯法”。 【举例】1.N皇后问题在...一种回溯算法入门教学思... 6页 免费 喜欢此文档的还喜欢 PASCAL...
回溯算法(一).ppt
一、回溯的概念回溯算法一种有条不紊的搜索问题答案的 方法,是一种能避免不必要搜
算法竞赛入门经典授课教案第7章 暴力求解法.doc
算法竞赛入门经典授课教案第7章 暴力求解法_IT/计算机_专业资料。第7章 暴力...“下 一个排列”枚举全排列的方法;理解子集树和排列树;熟练掌握回溯法框架;...
回溯算法_图文.ppt
回溯算法 - 回溯算法 奥赛暑假培训班专题之一 双十中学 庄晓芳 2006.7 回溯算法是所有搜索算法中最为基本的一种算法,是一种 能避免不必要搜索的穷举式的搜索...
回溯算法的应用.doc
所说的回溯算法实际是一个类似枚举的搜索尝试方法, ...“0/1 背 包问题” ,这只是在教学阶段中的运用,...回溯算法入门及应用 暂无评价 10页 免费 第5章回溯...
_算法设计与分析_课程中_回溯法_教学探讨_图文.pdf
课堂教学及实践教学两个环节分别对 的教学方法进行了...1 回溯法的课堂教学 算法是程序的灵魂。要培养学生...当学生初学 回溯 法时, 要让学生在充分理解的基础...
回溯算法的应用.doc
的搜索尝试方法,是一种系统地搜索 问题的解的方法...这只是在教学阶段中的运用,在实际运用中回溯法也能...回溯算法入门及应用 暂无评价 10页 免费 回溯算法...
算法设计与分析--回溯法.doc
回溯算法的应用 课程名称: 院系: 算法设计与分析 ...实际上是一个类似于枚举的搜索尝 试方法,他的主题...“0/1 背 包问题” ,这只是在教学阶段中的运用,...
基于回溯算法的智能排课系统.doc
回溯法就其算法的逻辑思路可表示为一棵树,根结点是初始状态, 每搜索到一个...目标就是使得各类冲突为零,并 且尽可能满足教师、学生的要求,达到较好的教学...
回溯算法.doc
回溯法的基本思想; 2、 掌握回溯法解题的基本算法...(搜索到一种方法) IF 搜索方法有效 THEN 试探产生...在教学中一方面可以借助动画模拟软 件帮助学生理解,...
回溯法.doc
回溯法 - 第 1回溯法 课程教学的基本要求 理解回溯法的基本思路算法框架 掌握 2~3 回溯法求解的程序实现方法 掌握这些算法的时间分析方法 相关知识_...
C语言回溯算法_图文.ppt
第五讲 回溯算法 从问题的某一种可能出发, 搜索从...xn∈Sn 基本思路: 若已有满足约束条件的部分解, 不...c语言教案回溯法 21页 1下载券 一种无回溯的自然...
算法设计与分析--回溯法.doc
1 页共 20 页 回溯算法的应用摘 要:回溯法是一...实际上是一个类似于枚举的搜索尝 试方法,他的主题...“0/1 背 包问题” ,这只是在教学阶段中的运用,...
回溯方法.ppt
回溯方法_数学_自然科学_专业资料。回溯法 ? 一般方法:回溯法的基本策略是搜索(按深度 优先进行)。 ? 回溯法将问题的解表示成一个n元式 (x1,x2,…,xn),...
更多相关标签: