492763
post:492763
陈明 与学生一起携手前行
- 发布时间：2011-09-01 10:31
- 作者：陈明
- 点击量:
与学生一起携手前行
--回溯算法及其应用
南京师范大学附属小学 陈明
一、游戏导入
出示老鼠走迷宫游戏，教师和学生一起玩游戏。
师：请学生说一说你玩迷宫游戏有什么技巧？
生1：能走就走，不能走就回头，找没有走的路再走。
生2：在岔路口选择路时按一定的规律来走不容易走重复路。
生3：像老鼠一样每走一条路都打了标记就能加快速度。
师：大家走迷宫的秘笈都很实用，今天我们学习利用程序设计来走迷宫，用的方法也是上面的一样，按照一个规律来找方向走，当发现走不通的时候回到前面走另一个可以走的方向，直到找到目的地，我们把这种方法称为回溯算法也叫尝试法。（出示课题）
二、迷宫问题
1、出示迷宫问题(图A)
|
入口 |
|
出口 |
图A 图B
2、迷宫的存储
这样的一个迷宫在我们的程序中怎么存储的呢？我们把这个迷宫画成一个一个的小方格，白色方格表示可以通行，黑色方格表示不能通过，整个迷宫就变成了一个二维数组a（出示图B，没有蓝线），在这个10行9列的二维数组中用1表示不能通行，用0表示可以通行，数组的赋值通过read/data完成。
出示完整的题目。
迷宫问题：有一迷宫(如图)，可用一个10行9列的0～1矩阵表示，其中0表示无障碍(白色)，1表示有障碍(黑色)。设入口位置的坐标为(2，1)，出口为(9，9)，规定每次移动中只能从一个无障碍的单元移到其周围四个方向上任一无障碍的单元。试编程给出通过迷宫的一条路径或报告一个“无法通过”的信息。
3、方向
师：请一位学生画一下走这个迷宫的线路，为什么选择这样的走法？
生：图B有蓝色的线。因为我看到出口在右下方，而且就只有这一条路可以到达出口。
师：这样走的方向规律是什么？
生：先下再右。
师：有没有其它方向了？
生：还需要向左和向上。
师：在这里我们一共有4个方向，走的规律是先向下，再向右，再向上，最后向左。
|
i-1,j |
| |
|
i,j-1 |
i,j |
i,j+1 |
|
|
i+1,j |
|
v数组存放四个方向行、列的变化：
|
方向 |
1 |
2 |
3 |
4 |
|
行 |
1 |
0 |
-1 |
0 |
|
列 |
0 |
1 |
0 |
-1 |
4、标识状态
(1)指名学生按上面讨论的方向顺序模拟走迷宫。（教师板书模拟过程）
师：在模拟的过程中为什么会形成死循环？
生：在第7步走2号方向到第8步，在第8步走4号方向又回到了第7步，但在这里程序并不知道第7步已经走过了，它把这一步看成是第9步，再按方向从1开始走，从2号方向我们又回到了原来的第8步，从而在这里形成了一个死循环。
师：怎么解决死循环问题呢？
生：对走过的路进行标识，走过的方向也不能再走。
师：我们把走过的每一步都进行标识，给它们赋值为2，在第8步4个方向都走不通，所以应该回到第7步，并从3号方向继续搜索能走的路。在这里我们把4个方向都不能走的位置标识为1，因为是死胡同防止下次再次走进。
师：当我们从第8步返回到第7步时，我们需要知道那些数据才能让我们正确的继续往下搜索呢？
生：第7步的行标和列标，还有第7步到第8步的方向。
师：那也就是说我们每走一步就要记录下每一步的位置和走向下一步的方向。在这我们使用一个二维数组b存放行标和列标，一个一维数组c存放方向。
（2）师生共同再次模拟，并记录好过程数据。每走一步的位置和方向如下表：
|
步数 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
|
行 |
2 |
2 |
3 |
4 |
4 |
5 |
6 |
6 |
7 |
8 |
8 |
8 |
9 |
9 |
9 |
9 |
9 |
9 |
|
列 |
1 |
2 |
2 |
2 |
3 |
3 |
3 |
2 |
2 |
2 |
3 |
4 |
4 |
5 |
6 |
7 |
8 |
9 |
|
方向 |
2 |
1 |
1 |
3 |
1 |
1 |
4 |
1 |
1 |
2 |
2 |
1 |
2 |
2 |
2 |
2 |
2 |
|
5、完善程序练习
Dim As Integer a(10,9),v(2,4),b(2,100),c(100),i,j,p,k
For i=1 To 10:For j=1 To 9:Read a(i,j):Next i:Next j
Data 1,1,1,1,1,1,1,1,1
Data 0,0,0,0,0,0,0,0,1
Data 1,0,1,0,0,1,1,0,1
Data 1,0,0,1,0,1,0,0,1
Data 1,1,0,1,0,0,1,0,1
Data 1,0,0,0,1,0,1,0,1
Data 1,0,1,1,0,0,1,0,1
Data 1,0,0,0,1,1,0,1,1
Data 1,0,1,0,0,0,0,0,0
Data 1,1,1,1,1,1,1,1,1
For i= 1 To 4:Read v(1,i), v(2,i):Next I
Data 1,0,0,1,0,-1,-1,0
i= （1） : j= （2） : p=1 : b(1,p)=i : b(2,p)=j : （3）
k=0
Do
k=k+1
If k<=4 Then
i=i+ （4） : j=j+ （5）
If i>=1 And i<=10 And j>=1 And j<=9 Then
If （6） Then
（7） : p=p+1 : （8） : （9） : a(i,j)=2 : （10）
Else
i= （11） :j=b(2,p)
End If
Else
i=b(1,p) : j= （12）
End If
Else
（13） : （14） : i=b(1,p):j=b(2,p): （15）
End If
Loop Until p=0 Or （16）
If （17） Then
For k=1 To p:Print b(1,k); b(2,k), : Next k
Else
Print "Not find"
End If
Sleep
当堂批改，全对打名次。指名学生回答，并说出理由。
6、程序调试
在程序中加入一个过程printA打印每走一步的A数组值的变化，让学生体会程序的执行过程。
Sub printA
Dim As Integer i,j
For i=1 To 10
For j=1 To 9
Print a(i,j);
Next j
Next i:Print
Sleep
End Sub
7、小结
回溯算法的框架如下：
构造一个初始当前局部解，解的个数统计为p,k为搜索方法指针
p=1:k=0
Do
k=k+1（搜索到一种方法）
If 搜索方法有效Then
产生一个临时局部解
If 是一个候选局部解Then
If候选解满足要求Then
是一个局部解，p=p+1，新局部解记录，k=0，再全方位搜索
Else
返回当前局部解继续搜索
End If
Else
返回当前局部解继续搜索
End If
Else
搜索方法无效，p=p-1，回溯到上一个局部解，恢复方法指针k继续搜索
End If
Loop Until p=0 Or 到达终点
If 到达终点 Then
输出结果
Else
无解
End If
三、递归回溯介绍
师：在回溯算法的搜索过程中，你觉得什么操作比较麻烦？
生：记录数据和回溯时的数据恢复比较麻烦。
师：如果我们像孙悟空一样，每走一步再变一个孙悟空守在那里，我们就不需要用数组来记录位置和方向了，能很方便的找到最终结果。其实我们也可以用程序做到，想一想以前我们学过那一种算法具有这种自己再变一个自己出来的功能？
生：递归算法。
师：阅读下面的程序，注意back()过程的递归调用。
Declare Sub back(i As Integer,j As Integer)
Declare Sub printRoad
Dim Shared a(10,9) As Integer
For i=1 To 10
For j=1 To 9
Read a(i,j)
Next j
Next i
Data 1,1,1,1,1,1,1,1,1
Data 0,0,0,0,0,0,0,0,1
Data 1,0,1,0,0,1,1,0,1
Data 1,0,0,1,0,1,0,0,1
Data 1,1,0,1,0,0,1,0,1
Data 1,0,0,0,1,0,1,0,1
Data 1,0,1,1,0,0,1,0,1
Data 1,0,0,0,1,1,0,1,1
Data 1,0,1,0,0,0,0,0,0
Data 1,1,1,1,1,1,1,1,1
back(2,1)
Print "no"
Sleep:End
Sub printRoad
Dim As Integer i,j
For i=1 To 10
For j=1 To 9
If a(i,j)=2 Then Print i;j,
Next j
Next i
End Sub
Sub back(i As Integer,j As Integer)
If i>=1 And i<=10 And j>=1 And j<=9 Then
If a(i,j)=0 Then
a(i,j)=2
If i=9 And j=9 Then printRoad:Sleep:End
back(i+1,j)
back(i,j+1)
back(i-1,j)
back(i,j-1)
a(i,j)=1
End If
End If
End Sub
指名学生说一说程序的执行过程。
加入过程printA调试程序。
四、上机题
1、迷宫问题。
|
3、求长度为素数的路径个数
对于正整数n (3≤n<20)，可以画出n阶的回形矩阵。 n=3
如n=3时，路径及长度有：
长度=5 |
长度=6
|
长度=6
|
长度=5
|
长度=6
|
长度=6
|
因此说，3阶回形矩阵有2条路径的长度为素数。
【输入输出】
输入： 一个自然数n (3≤n<20，不必判错)。
输出： 一个正整数，即n阶回形矩阵中长度为素数的路径的个数。
【样例】
输入：3
输出：2
设计意图：
与学生一起携手前行
一、通过游戏导入，让学生从已有经验认识回溯算法
与学生一起玩老鼠走迷宫游戏，让学生快速的进入状态，激发学生对本节课知识的探索。学生从玩迷宫游戏中总结走迷宫的技巧，学生很乐意思考怎样快速通过迷宫，通过大家共同分享走迷宫的秘笈，很快就会总结出行之有效的方法，而这一种方法就是今天我们要学习的内容回溯算法，学生对于他们自己总结出来的回溯算法就会很容易接受并且乐于使用这种方法来解决问题。
二、通过反复模拟走迷宫，让学生真正理解回溯算法
回溯算法对于小学五年级的学生来说还是比较困难的，在教学过程中我通过多次模拟走迷宫让学生一步一步的理解回溯算法。
第一次模拟走迷宫让学生画出正确的路线，通过画路线学生理解搜索方向的顺序性，从而对于回溯算法搜索路径的时候必需按照一定的规律来进行搜索有了直客的认识。
第二次模拟走迷宫学生知道了搜索方向的顺序后严格按照搜索方向一步一步的搜索，会发现一个死循环，在第7步和第8步循环走，从而让学生理解在使用回溯算法时一定要打标记。
通过前面二次模拟走迷宫学生已经对回溯算法有了大体的理解，在走不通需要回溯时我们要还原前一步的位置和方向，也就是说我们需要记录下每一步走的位置和方向，这需要通过数组来记录。所以我们再通过第三次共同模拟走迷宫把所有的标记打上，把所有需要记录的数据记录好，完整模拟走迷宫全过程，为学生完成完善程序练习，自己写出回溯算法程序打下坚实的基础。
其实在理解回溯算法的整个过程中，学生反复多次的模拟走迷宫，除了上面三次外，学生在做完善程序时他们也需要边模拟边填空，在说填空理由时也需要在模拟的过程中去寻找。
三、通过形象的比喻，让学生抓住递归回溯的关键
对于一般的回溯算法学生在应用的过程中总是会出一些小问题，在我的教学过程的最后会让学生读递归回溯，在读之前会让学生想一想回溯算法什么操作比较烦人，从而提示学生如果我们的程序像孙悟空一样，每走一步再变一个孙悟空那么我们就不需要那些复杂的数据记录与恢复了，学生很容易就会想到递归算法。通过一般回溯算法的学习，学生很容易就会理解递归回溯，他们在应用回溯算法的过程中也会更多的选择递归回溯算法，在学生写的程序中递归回溯算法的正确率高于一般回溯算法。
四、通过指导学生调试程序，帮助学生理清回溯算法的思想
在完善程序后和读递归回溯之后，在程序中增加一个打印过程printA，然后运行程序。在这个过程中既指导学生如何调试程序，又让学生在执行程序的过程中进一步的理解回溯算法。
回溯算法是一个重要的算法，学生在学习的过程中会遇到很多的困难，教师要和学生一起携手前行，帮助他们轻装上阵，引导学生快乐的前行，从而走向远方。
下一篇：姜玲 科学 《小数据大心得》