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

一种回溯算法入门教学思路摘 要:回溯法是信息学奥赛中学生必须掌握的重要算法思想,对如何进行回溯法入门教学提出了一种新的思路。将基本回溯问题区分为子集和排列两类问题,调整传统教学中的算法步骤为:(1)确定问题类型;(2)写出固定回溯算法;(3)根据问题进行优化。避免了回溯法教学中相对模糊的概念和步骤,有利于学生掌握回溯法的基本思想。关键词:信息学奥赛 回溯算法 入门教学 教学思路1 两类基本问题回溯算法的本质就是深度优先遍历解空间树,根据解空间树生成方式的不同可以将问题分为子集问题和排列问题两类。1.1 子集问题给定n个元素r1,rn,生成所有可能的子集,稍作推广:第i个元素的选择范围为s1.ni,算法如下:procedure subset(r:元素数组,i:integer);/ri.n所有子集varpos:integer;/循环变量beginif in then/递归边界,已生成1子集elsefor pos:=1 to ni do begin/第i个元素有ni个选择ri:=spos;subset(r,i+1);/递归end;end;这看上去和排列问题很像,还可把排列问题转成子集问题,但会导致问题复杂化,不利于对算法的掌握。1.2 排列问题给定一组数据元素r1,rn,生成可能的排列。很多实现算法采用访问数组记录选择情况,这需要反复检查原始是否已被选择,大大影响算法效率。合理的是通过交换元素位置来实现:procedure perm(r:元素数组,i:integer);/ri.n全排列varpos:integer;/循环变量beginif in then/递归边界,已生成1全排列elsefor pos:=i to n do begin/可以放在位置i的元素swap(ri,rpos);/放到位置i上perm(r,i+1,n);/递归调用swap(ri,rpos);/恢复ri.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:ri=0或1表示第i件物品是否选中。例2:ri=1,n表示第i列皇后放在第ri行。例3:ri=1,n,表示第i次访问城市ri。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间的旅费为cij,初始化mc为-1(表无穷大),cc为0。在递归边界检查是否需更新mc。递归前后同样需更新、恢复cc的值,并在递归前进行该剪枝检查。3 结语本文提出的回溯法教学思路采用了相对明确、简单的解题步骤,有一定局限性,因此只适用于入门教学。但学生一旦掌握回溯算法的基本思想后,可进一步引导其思考如何突破排列问题和子集问题的局限性。突破局限的关键在于如何生成当前所有可能的选择,这要根据具体问题进行。显然,不论在