下载此文档

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


文档分类:IT计算机 | 页数:约6页 举报非法文档有奖
1/6
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/6 下载此文档
文档列表 文档介绍
一种回溯算法入门教学思路.doc一种回溯算法入门教学思路摘要:回溯法是信息学奥赛中学生必须掌握的重要算法思想,对如何进行回溯法入门教学提出了一种新的思路。将基本回溯问题区分为子集和排列两类问题,调整传统教学中的算法步骤为:(1)确定问题类型;(2)写出固定回溯算法;(3)根据问题进行优化。避免了回溯法教学中相对模糊的概念和步骤,有利于学生掌握回溯法的基本思想。关键词:信息学奥赛回溯算法入门教学教学思路1两类基本问题回溯算法的本质就是深度优先遍历解空间树,根据解空间树生成方式的不同可以将问题分为子集问题和排列问题两类。,…rn,生成所有可能的子集,稍作推广:第i个元素的选择范围为s[1..ni],算法如下:proceduresubset(r:元素数组,i:integer);//r[i..n]所有子集varpos:integer;//循环变量beginifi>nthen//递归边界,已生成1子集……elseforpos:=1tonidobegin//第i个元素有ni个选择r[i]:=s[pos];subset(r,i+1);//递归end;end;这看上去和排列问题很像,还可把排列问题转成子集问题,但会导致问题复杂化,不利于对算法的掌握。,…rn,生成可能的排列。很多实现算法采用访问数组记录选择情况,这需要反复检查原始是否已被选择,大大影响算法效率。合理的是通过交换元素位置来实现:procedureperm(r:元素数组,i:integer);//r[i..n]全排列varpos:integer;//循环变量beginifi>nthen//递归边界,已生成1全排列……elseforpos:=itondobegin//可以放在位置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:哈密尔顿回路问题:选一条从驻地出发,经过每个城市一遍最后回到驻地的路线,使总旅费最小。显然是排列问题。一般而言,难判定的往往是子集问题。。问题类型决定解空间表示法:通常是一维数组。但元素取值范围要根据题目灵活设计。生成所有可能解,直接套用前述perm或subset即可:例1:r[i]=0或1表示第i件物品是否选中。例2:r[i]=1,…,n表示第i列皇后放在第r[i]行。例3:r[i]=1,…,

一种回溯算法入门教学思路 来自淘豆网www.taodocs.com转载请标明出处.

非法内容举报中心
文档信息
  • 页数6
  • 收藏数0 收藏
  • 顶次数0
  • 上传人dyx110
  • 文件大小35 KB
  • 时间2020-01-03