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

摘要:回溯法是信息学奥赛中学生必须掌握的重要算法思想,对如何进行回溯法入门教学提出了一种新的思路。将基本回溯问题区分为子集和排列两类问题,调整传统教学中的算法步骤为:(1)确定问题类型;(2)写出固定回溯算法;(3)根据问题进行优化。避免了回溯法教学中相对模糊的概念和步骤,有利于学生掌握回溯法的基本思想。
关键词:信息学奥赛回溯算法入门教学教学思路
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;
这看上去和排列问题很像,还可把排列问题转成子集问题,但会导致问题复杂化,不利于对算法的掌握。
排列问题
给定一组数据元素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)添加约束、剪枝进行优化。
确定类型
首先抛开题目约束和目标,将问题简化抓本质:变的是元素还是位置?下面通过3个典型例子说明:
例1:0-1背包问题:给出装背包方案,使得背包物品总价值最大。不关心物品装入顺序,因此是子集类。
例2:八皇后问题:n*n的棋盘上放n个皇后,使皇后间互不攻击。看上去和位置有关,但交换两个皇后的位置不产生新方案,因此也是子集问题。
例3:哈密尔顿回路问题:选一条从驻地出发,经过每个城市一遍最后回到驻地的路线,使总旅费最小。显然是排列问题。
一般而言,难判定的往往是子集问题。
所有可能解。
问题类型决定解空间表示法:通常是一维数组。但元素取值范围要根据题