回溯法及其在程序设计中的应用，本文主要内容关键词为：程序设计论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
在中学计算机教学中，程序设计教学是一个很重要的内容，培养学生程序设计的能力是中学计算机教学的重要任务之一。计算机知识引入我国中小学教育，虽然只有短短的十几年时间，但已取得了可喜的成绩。特别在程序设计的方法上已有了较深入的研究。本文就回溯法及其应用在教学中作些初探。
有些问题在编写程序时往往感到很难下手，因为很难把它归纳成一个公式或是一个简单的算法。而又不能盲目地去瞎碰，这时只能从某一点线索出发先试一试，如果试不成功就返回到问题的出发点换一种方法去试，直到找出解决问题的方案。这类似于闯迷宫。
1 一个问题求解的启示
问题一：求满足下列条件的各种结果
分析：这是一个1-5的数字中间运用加、减、乘、除四种运算后使其结果为10的选择运算顺序的问题。这问题并不复杂，找出一种方案是不难的。如(1+2+3-4)* 5=10。但要找出全部方案就不能瞎碰，因为可能性有4*4*4*4=256种，而我们要在这256种方案中找出结果为10的方案。具体探索是在1-5之间的各种运算都先取“+”运算看结果是否等于10，若等于10这算一种方案。否则在4-5之间用“－”去试探，若等于10就算一种。否则再用“*”运算去试。直到4种运算都试完。然后再退到3-4之间改用“－”运算，再从4-5之间试完四种运算。再退到3-4之间改为“*”运算，再从4-5之间试完四种运算…。如此反复使用这种退回再前进的方法就能得出满足条件的所有方案。
算法：我们把上面考虑问题的方法构成一种程序设计的算法如下：
令I…表示试探步骤的变量。
A(I)…表示第I步试探的运算顺序号（+、－、*、/）
(1)先从第1步的第1种运算试起，令I=1，A(I)=1
(2)再试下一步，令I=I+1。若＞4 则转(4)，否则转(3)。
(3)进行第I步试探的下一顺序运算：A(I)=A(I)+1，若(I)＞4转(7)，否则转(2)。
(4)检验运算的结果是否等于10，如是则转(6)，否则转(5)。
(5)退一步转(3)。
(6)打印一种结果等于10的算式。然后转(5)。
(7)取消第A(I)种运算：令A(I)=0，再令=I-1（退回到前一步再试）。
(8)若=0（退至到头）则结束，否则转(3)。
由上述算法用BASIC语言编写如下的程序：
10 FORI=1 TO 4：READ A＄ (I)：NEXT
20 DATA“+”，“-”，“*”，“/”
30 I=0
40 I=I+1:IF I＞4 THEN 80
50 A(I)=A(I)+1:IF A(I)<=4 THEN 40
60 A(I)=0:I=I-1:IF I=0 THEN END
70 GOTO 50
80 X=1:FOR I=2 TO 5
85 X=(X+1)*(-(A(I-1)=1))+(X-1)*(-(A(I-1)=2))+(X*I)*(-(A(A(I-1)=3))+(X/I)*(-(I-1)=4)):NEXT
90 IF X＜＞10 THEN 110
100 PRINT"((((1";:FOR I=1 TO 4：PRINT A＄(A(I);I+1;"):;:NEXT:PRINT"=10"
110 I+I-1:GOTO 50
RUN
((((1+2)+3)-4)* 5)=10
((((1+2)*3-4)+5)=10
((((1+2)/3)+4)+5)=10
((((1*2)*3)-4)*5)=10
2什么是回溯法
从问题一的解决中，我们看到解决问题的思路是先选择某一可能的线索进行试探，每一步试探都有多种方式，将每一方式都一一试探，如有问题就返回纠正，反复进行这种试探再返回纠正，直到得出全部符合条件的答案或是问题无解为止。这种解决问题的方法就是回溯法。
回溯法是程序设计的一种很重要的方法，应用它可以解决许多难题，近年来在竞赛中常用这种方法解题。学生学起来困难较大，我在教学中总结出一种应用回溯法的模式，大大提高了学生的编程能力。
回溯法的应用模式：
(1)设置初始化的方案（给变量赋初值，读入已知数据等）。
(2)变换方式去试探，若全部试完则转(7)。
(3)判断此法是否成功，不成功则转(2)。
(4)试探成功则前进一步再试探。
(5)正确方案还未找到则转(2)。
(6)已找到一种方案则记录并打印。
(7)退回一步（回溯），若未退到头则转(2)。
(8)已退到头则结束或打印无解。
用上述模式来解著名的“八皇后”问题：
问题二：在国际象棋盘上摆放八个皇后，使其不在同行、同列，也不在同一对角线上。
当年高斯只给出了三十种方案，实际上要有九十二种方案。现在给出这个问题的回溯法模式和程序(1)初始化：令I──表示行变量，A(I)──表示列变量，I=1.A(I)=1
(2)放下一个，I=I+1，A(I)=A(I)+1，若I＞8，则转(6)，A(I)＞8则转(7)
(3)判断该放法是否合条件？若A(I)-A(J)=SNG(A(I)-A(J)*(I-J)成立，则转(2)。
(4)方法成功再放下一个。
(5)方案尚未找出，则转(2)
(6)已找出一个方案(I=8)，则记录并打印。
(7)退回一步(I=I-1)，若未退到头(I＜＞0)则转(2)
(8)若退到头(I=0)则结束或打印无解。
程序 10 DIM A(8):N=0
20 I=1:A(I)=+1
30 I=I+1:IFI＞8 THEN 80
40 A(I)=A(I)+1:IF A(I)＞8 THEN 100
50 FORJ=I-1 TO 1 STEP-1
60 IF A(I)-A(J)=SGN(A(I)-A(J)*(I-J) THEN 40
70 NEXT：GOYO 30
80 N=N+1:FOR K=1 TO 8
85 PRINT K;",";A(K);" ";:NEXT:PRINT"…";N:PRINT
90 I=I-1：GOTO 40
100 A(I)=0:I=I-1
110 IF I=0 THEN END
120 GOTO 40
3带有深度优先搜索的回朔法
有的问题单用回溯是不能解决的，在回溯的过程中为了不重复已经使用过的试探，还得记住已用过的探索──深度搜索。下面的问题需要记住每步搜索的深度。
问题三：在中国象棋半张盘上，马自左下向右上角跳，今规定：不许往左跳，如图(1)所示为一种跳行路线，编程序计算共有多少种跳行路线，并将所经路线打印出来。
打印格式为：0,0-1,2-2,4-4,3-5,1-6,3-8,4 …〈方案号〉
算法分析：以图(2)画出棋盘上处于(3，2)位置上的一只马，可能的跳步方向有四个方向，分别称为方向1，方向2，方向3，方向4。用变量T标记。往方向1跳时水平方向的增量DX=1，垂直方向的增量DY=2；往方向2跳时，水平方向增量DX=2，垂直方向的增量DY=1；往方向3跳时水平方向的增量DX=2，垂直方向增量DY=-1；往方向4跳时水平方向的增量DX=1，垂直方向的增量DY=-2，另用数组C(T)，D(T)表示四个方向上要搜索的增量， T=1，2，3，4。用数组X(10)，Y(10)来记录马在水平方向和垂直方向上的位置。数组A(10)记录在搜索马的跳步方向时已搜索过的方向号。
I……记录马在棋盘上跳过步数的变量。
A(I)……第I步跳行的方向号（搜索深度）
X，Y……表示马在棋盘上要跳的位置。在跳第I步时的水平位置和垂直位置分别为：
X=X(I-1)+C(T)；Y=Y(I-1)+D(T)（T为跳行方向号）
若第I步T方向跳行成功，则要把X、Y、T存入X(I)，Y(I)，A(T)中，即X(I)=X，Y(I)=Y，A(I)=T以备搜索时查寻。当跳下一步时，即I=I+1，若越界(X＜0 OR X＞8 OR Y＜0 OR Y＞4)则换下一方向搜索，即T=T+1。若四个方向都已试过仍不成功，则要沿原来的跳行路线退回一步（回溯），即I=I-1。取出方向号A(I)存入T中，即T-A(I)。然后换下一方向再试，即T=T+1。这样试跳，返回，再试跳再返回，直到X=8，Y=4才完成一条跳行路线转入打印。回溯，再试跳再返回直到退到头(I=0)。
将前面的算法套用模式：
(1)初始化（读入方向增量）。
(2)从下一步试跳，令I=I+1，方向从头开始，令T=0。
(3)从下一方向试跳，T=T+1，若T＞4，则转(7)回溯。
(4)在第I步T方向要跳的位置：X=X(I-1)+C(T)，Y=Y(I-1)，+D(T)。
(5)若第I步越界，则要换下一方向试跳。否则记下第I步的位置和方向：X(I)=X，Y(I)=Y，A(I)=T然后转(2)。
(6)若X=8，Y=4打印成功方案。
(7)回溯，I=I-1。
(8)若I=0 则结束，否则T=A(I)（取出已试方向）再试下一方向。
程序：
5
DLM A(10)，X(10)，Y(10)，C(4)，D(4)
10
FOR I=1 TO 4 READ C(I)，D(I)：NEXT：DATA 1，2，2，1，2，-1，1，-2
15
I=0
20
I=I+1:T=0
30
T=T+1：IF T＞4 THEN 110
40
X=X(I-1)+C(T)：Y=Y(I-1)+D(T)
50
IF X＜0 OR X＞8 OR Y＜0 OR Y＞4 THEN 30
60
IF X=8 AND Y=4 THEN 30
70
IF X=8 AND y=4 THEN 90
80
X(I)=X：Y(I)=Y：A(I)=T：GOTO 20
90
S=S+1
100 FOR P=0 TO I-1：PRINT X(P)；“，”；Y(P)；“ ”；：NEXT
105 PRINT“8，4”；“…”；S
110 I=I-1：IF I=0 THEN END
120 T=A(I)：GOTO 30
运行结果有三十七种跳行路线。
（本文中的程序均在PC机上通过，PC机的逻辑真值为-1）
标签：回溯法论文;