Pascal回溯算法入门.pps

第六讲回溯算法入门信息学竞赛的试题一般有两种类型:1、简明的数学模型提示问题本质,对于这一类试题,我们尽量用解析法求解。2、对给定的问题建立数学模型,或即使有一定的数学模型,但采用数学方法解决有一定困难。对于这一类试题,我们只好用模拟或搜索求解。导入在一些问题求解进程中,有时发现所选用的试探性操作不是最佳选择,需退回一步,另选一种操作进行试探,这就是回溯算法。例[]中国象棋半张棋盘如下,马自左下角往右上角跳。现规定只许往右跳,不许往左跳。比如下图所示为一种跳行路线。编程输出所有的跳行路线,打印格式如下:<1>(0,0)—(1,2)—(3,3)—(4,1)—(5,3)—(7,2)—(8,4)解:按象棋规则,马往右跳行的方向如下表和图所示:解:按象棋规则,马往右跳行的方向如下表和图所示:水平方向用x表示;垂直方向用y表示。右上角点为x=8,y=4,记为(8,4);用数组tt存放x方向能成行到达的点坐标;用数组t存放y方向能成行到达的点坐标;①以(tt(K),t(k))为起点,按顺序用四个方向试探,找到下一个可行的点(x1,y1);②判断找到的点是否合理(不出界),若合理,就存入tt和t中;如果到达目的就打印,否则重复第⑴步骤;③如果不合理,则换一个方向试探,如果四个方向都已试过,就退回一步(回溯),用未试过的方向继续试探。重复步骤⑴;④如果已退回到原点,则程序结束。Pascal程序:ProgramExam66; Constxx:array[1..4]of1..2=(1,2,2,1); yy:array[1..4]of-2..2=(2,1,-1,-2); Varp:integer; t,tt:array[0..10]ofinteger; procedurePrn(k:integer); Vari:integer; Begin inc(p);write(‘<‘,p:2,’>‘,’‘:4,’0,0’); fori:=1tokdo write(‘—(‘,tt[I],’,’,t[I],’)’); writeln End; ProcedureSub(k:integer); Varx1,y1,i:integer; Begin forI:=1to4do Begin x1:=tt[k-1]+xx[i];y1:=t[k-1]+yy[i]; ifnot((x1>8)or(y1<0)or(y1>4))then Begin tt[k]:=x1;t[k]=y1; if(y1=4)and(x1=8)thenprn(k); sub(k+1); end; end; end; Begin p:=0;tt[0]:=0;t[0]:=0; sub(1); writeln(‘From0,0to8,4Allofthewaysare’,p); readln 、回溯法从问题的某一种可能出发,搜索从这种情况出发所能达到的所有可能,当这一条路走到“尽头”的时候,再倒回出发点,从另一个可能出发,“回溯”寻找解的方法,称作“回溯法”。【举例】×N(≥4)的棋盘里放置N个皇后,使得看彼此不能相互攻击。〖问题分析〗: 所谓N个皇后不能相互攻击,即N个皇后不能同行、不能同列、不能在同一对角线上。(1)不同行:由于是一行只排一个皇后,所以肯定不同行。 不同列:设置一个数组:MARK0,当J列已安排皇后时,MARK0[J]:=FALSE。不允许再安排皇后。 不在同一对角线: * 任意一条红色左斜线上的方格坐标都有一个规律:I+J相等,只要标记MARK1[I+J]:=FALSE,该条红色左斜线都将不可安排。 红色的斜线从最左边1+1,2+1或1+2到N+N条。 * 任意一条绿色的右斜线上的方格坐标也有一个规律:I-J相等,也只要定义MARK2[I-J]=FALSE,则所有该右斜线都将不可安排。 绿色的斜线从最右边1-N到N-1条。最后的条件是:当皇后准备安排在第J列时,必须符合下列条件,才能安排: IfMARK0[J]ANDMARK1[I+J]andMARK2[I-J]Then Begin A[I]:=J;安排皇后 MARK0[J]:=FALSE; MARK1[I+J]:=FALSE; MARK2[I-J]:=FALSE;设置约束条件,让其他皇后无法再放置 End;最后的条件是:当皇后准备安排在第J列时,必须符合下列条件,才能安排: IfMARK0[J]ANDMARK1[I+J]andMARK2[I-J]ThenBegin A[I]:=J;安排皇后 MARK0[J]:=FALSE; MARK1[I+J]:=FALSE; MARK2[I-J]:=FALSE;设置约束条件,让其他皇后无法再放置 End