图 3
分析:每人选择五项工作中的一项，在各种选择的组合中，找到效益最高的的一种组合输出。 算法步骤: ⒈数据库：用数组ｆ构成堆栈存放产生的结点；数组ｇ存放当前最高效益结点的组合；数组ｐ作为结点是否选择过的标志位。 ⒉结点的产生：
(1)选择ｐ(i)=0的结点；
(2)判断效益是否高于ｇ记录结点的效益，是高于则更新ｇ数组及最高效益值。 ⒊搜索策略: 深度优先搜索。 源程序如下: program exam1; const
data: array [1..5,1..5] of integer
=((13,11,10,4,7),(13,10,10,8,5),(5,9,7,7,4), (15,12,10,11,5),(10,11,8,8,4)); var
i,max: integer;
f,g: array [1..5] of integer; p: array [1..5] of integer;
procedure go(step,t: integer); {选择最佳效益结点的组合} var
i: integer; begin
for i:=1 to 5 do
if p[i]=0 then begin f[step]:=i; p[i]:=1;
t:=t+data[step,i];
if step<5 then go(step+1,t) else
if t>max then begin max:=t; g:=f; end;
t:=t-data[step,i]; p[i]:=0; end; end; begin
max:=0;
for i:=1 to 5 do p[i]:=0; go(1,0); writeln;
for i:=1 to 5 do write(chr(64+i),':J',g[i],'':3);
- 26 -
writeln;
writeln('supply: ',max); end.
【例3】再探马的遍历
中国象棋半张棋盘如图4（a）所示。马自左下角往右上角跳。今规定只许往右跳，不许往左跳。比如图4（a）中所示为一种跳行路线，并将所经路线打印出来。打印格式为： 0，0->2,1->3,3->1,4->3,5->2,7->4,8…
4 3 2 1
1 4 马 3 2 0 1 2 3 4 5 6 7 8
图4
（a） （b） 分析：如图4（b）,马最多有四个方向，若原来的横坐标为j、纵坐标为i,则四个方向的移动可表示为：
1： （i,j）→（i+2,j+1）； (i<3,j<8) 2: （i,j）→（i+1,j+2）； (i<4,j<7) 3: （i,j）→（i-1,j+2）； (i>0,j<7) 4: （i,j）→（i-2,j+1）； (i>1,j<8) 搜索策略： S1:Ａ[１]:=(0,0);
S2:从Ａ[1]出发，按移动规则依次选定某个方向，如果达到的是（4,8）则转向S3,否则继续搜索下一个到达的顶点；
S3:打印路径。
源程序范例： program exam2; const
x:array[1..4,1..2] of integer=((2,1),(1,2),(-1,2),(-2,1)); {四种移动规则} var
t:integer; {路径总数}
a:array[1..9,1..2] of integer; {路径}
procedure print(ii:integer); {打印} var
i:integer; begin inc(t);
for i:=1 to ii-1 do
write(a[i,1],',',a[i,2],'-->');
- 27 -
writeln('4,8',t:5); readln; end;
procedure try(i:integer); {搜索} var
j:integer; begin
for j:=1 to 4 do
if (a[i-1,1]+x[j,1]>=0) and (a[i-1,1]+x[j,1]<=4) and (a[i-1,2]+x[j,2]>=0) and (a[i-1,2]+x[j,2]<=8) then begin
a[i,1]:=a[i-1,1]+x[j,1]; a[i,2]:=a[i-1,2]+x[j,2];
if (a[i,1]=4) and (a[i,2]=8) then print(i)
else try(i+1); {搜索下一步} a[i,1]:=0;a[i,2]:=0 end; end;
begin {主程序} try(2); end.
【例4】 选书
学校放寒假时，信息学竞赛辅导老师有A，B，C，D，E五本书，要分给参加培训的张、王、刘、孙、李五位同学，每人只能选一本书。老师事先让每个人将自己喜欢的书填写在如下的表格中。然后根据他们填写的表来分配书本，希望设计一个程序帮助老师求出所有可能的分配方案，使每个学生都满意。 学生书本张同学 王同学 刘同学 孙同学 李同学 A Y B Y Y Y C Y Y D Y Y E Y Y 分析：
可用穷举法，先不考虑“每人都满意” 这一条件，这样只剩“每人选一本且只能选一本”这一条件。在这个条件下，可行解就是五本书的所有全排列，一共有5！=120种。然后在120种可行解中一一删去不符合“每人都满意”的解，留下的就是本题的解答。
为了编程方便，设1，2，3，4，5分别表示这五本书。这五个数的一种全排列就是五本书的一种分发。例如54321就表示第5本书（即E）分给张，第4本书（即D）分给王，……，第1本书（即A）分给李。“喜爱书表”可以用二维数组来表示，1表示喜爱，0表示不喜爱。
算法设计：
S1：产生5个数字的一个全排列；
S2：检查是否符合“喜爱书表”的条件，如果符合就打印出来；
- 28 -
S3：检查是否所有的排列都产生了，如果没有产生完，则返回S1； S4：结束。
上述算法有可以改进的地方。比如产生了一个全排列12345，从表中可以看出，选第一本书即给张同学的书，1是不可能的，因为张只喜欢第3、4本书。这就是说，1××××一类的分法都不符合条件。由此想到，如果选定第一本书后，就立即检查一下是否符合条件，发现1是不符合的，后面的四个数字就不必选了，这样就减少了运算量。换句话说，第一个数字只在3、4中选择，这样就可以减少3/5的运算量。同理，选定了第一个数字后，也不应该把其他4个数字一次选定，而是选择了第二个数字后，就立即检查是否符合条件。例如，第一个数选3，第二个数选4后，立即检查，发现不符合条件，就应另选第二个数。这样就把34×××一类的分法在产生前就删去了。又减少了一部分运算量。
综上所述，改进后的算法应该是：在产生排列时，每增加一个数，就检查该数是否符合条件，不符合，就立刻换一个，符合条件后，再产生下一个数。因为从第I本书到第I+1本书的寻找过程是相同的，所以可以用递归方法。算法设计如下：
procedure try(i); begin
for j:=1 to 5 do begin
if 第i 个同学分给第j本书符合条件 then begin
记录第i 个数3
if i =5 then 打印一个解 else try(i+1); 删去第i 个数字 end; end; end;
源程序：
program exam3; type five=1..5; const
like:array[five,five] of 0..1=((0,0,1,1,0),(1,1,0,0,1), (0,1,1,0,0),(0,0,0,1,0),(0,1,0,0,1));
name:array[five] of string[6]=('zhang','wang','liu','sun','li'); var
book:array[1..5] of 0..5; flag:set of five; c:integer;
procedure print; var i:integer; begin
inc(c);writeln('answer',c,':'); for i:=1 to 5 do
writeln(name[i]:10,':',chr(64+book[i])); end;
procedure try(i:integer); var j:integer; begin
- 29 -
for j:=1 to 5 do
if not(j in flag) and (like[i,j]>0) then begin
flag:=flag+[j];book[i]:=j; if i=5 then print
else try(i+1); flag:=flag-[j];book[i]:=0; end; end;
begin
flag:=[];c:=0;try(1); readln end.
输出结果：
zhang: C wang: A liu: B sun: D li: E
六、 回溯与深度优先搜索10大典型例题 ①. 农夫过河 ②. 1—8不连续的数字 ③. 迷宫问题 ④. 地图着色 ⑤. 一笔画问题 ⑥. 城市遍历问题 ⑦. 马的遍历问题 ⑧. 分解自然数N之积 ⑨. 分解自然数N之和 ⑩. N皇后问题
1.【题目】
农夫过河。一个农夫带着一只狼，一只羊和一些菜过河。河边只有一条一船，由于船太小，只能装下农夫和他的一样东西。在无人看管的情况下，狼要吃羊，羊 要吃菜，请问农夫如何才能使三样东西平安过河。 【算法分析】
将问题数字化。用１代表狼，２代表羊，３代表菜。则在河某一边物体的分布有以下 ８种情况。 ┏━━━━┯━┯━━━━━┯━━━━━━━━┯━━━┓ ┃物体个数│０│ １ │ ２ │ ３ ┃ ┠────┼─┼─┬─┬─┼──┬──┬──┼───┨ ┃分布情况│０│１│２│３│1,2 │1,3 │2,3 │1,2,3 ┃ ┠────┼─┼─┼─┼─┼──┼──┼──┼───┨ ┃代码之和│０│１│２│３│３ │ ４ │ ５ │ ６ ┃ ┠────┼─┼─┼─┼─┼──┼──┼──┼───┨ ┃是否相克│ │ │ │ │相克│ │相克│ ┃ ┗━━━━┷━┷━┷━┷━┷━━┷━━┷━━┷━━━┛
- 30 -