当前位置:首页 >> 其它课程 >> 一种回溯算法入门教学思路

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


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


更多相关文档:

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

一种回溯算法入门教学思路摘 要:回溯法是信息学奥赛中学生必须掌握的重要算法思想,对 如何进行回溯法入门教学提出了一种新的思路。将基本回溯问题区 分为子集和...

回溯算法的应用

回溯算法入门及应用 暂无评价 10页 免费 迷宫机器人...的搜索尝试方法,是一种系统地搜索 问题的解的方法...“最优 化问题” ,这只是在教学阶段中的运用,在...

回溯算法的应用

所说的回溯算法实际是一个类似枚举的搜索尝试方法, ...“0/1 背 包问题” ,这只是在教学阶段中的运用,...回溯算法入门及应用 暂无评价 10页 免费 第5章回溯...

《入门四问》教学思路

入门四问》教学思路 教学参考 0830 1237 《入门四问》教学思路 教学目标 1.了解中国古代文化典籍的概况,掌握四部法,回顾并梳理自己了解的中 国古代文化著作。 ...

算法设计与分析--回溯法

1 页共 20 页 回溯算法的应用摘 要:回溯法是一...实际上是一个类似于枚举的搜索尝 试方法,他的主题...“0/1 背 包问题” ,这只是在教学阶段中的运用,...

算法设计与分析--回溯法

回溯算法的应用 课程名称: 院系: 算法设计与分析 ...实际上是一个类似于枚举的搜索尝 试方法,他的主题...“0/1 背 包问题” ,这只是在教学阶段中的运用,...

edu_ecologychuanke183344

理解回溯算法的基本概念,并通过几案例的讲解,学习回溯的基本应用。视频教程,NOIer全套教学,在线学习高中其他课程,NOIP算法入门——回溯视频下载

中南大学2014算法试卷及答案分析

在当前的扩展结点处,搜索向纵深方向移至一个新 结点。这个新结点就成为新的活...在一般情况下用递归方法实现回溯法的基本框架如下: void backtrack (int t) {...

算法设计入门教学内容

八大基础算法对下列基本算法重点强调各算法的适用条件,算法思想,解决算法思路。...(4) 把子问题的解局部最优解合成原求解问题的一个解。 7) 回溯(含分支定...

算法竞赛入门经典授课教案第5章基础题目选解

第5章 基础题目选解 第 2 部分第5章 算法基础题目选解 【教学内容相关...方法很简单, 使用一个标志变量即可。 完整的程序如下: #include <stdio.h> ...
更多相关标签:
回溯算法 | 回溯算法经典 | 回溯算法 java | 递归回溯算法 | 马步遍历问题回溯算法 | 回溯算法 背包问题 | c语言回溯算法 | 回溯搜索算法 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com