回溯算法入门及应用.docx

回溯算法入门及应用
广东省东莞市东华高级中学 杨光文 难易指数:★★★
在求解一些问题(如马的遍历、选书、八皇后问题、自然数的拆分等问题)时，题目的要求可能是求 出原问题的一种或所有可能的解决方案。这类问题的解往往是由一个一个的步骤或状a[i,2]=8) then print(i)
else try(i+l); ｛搜索下一步｝
a[i,1]:=0;a[i,2]:=0
end;
end;
begin
try(2);
end.
例 2 ：选书
学校放寒假时，信息学竞赛辅导老师有A, B, C, D, E五本书，要分给参加培训的张、王、刘、孙、 李五位同学，每人只能选一本书。老师事先让每个人将自己喜欢的书填写在如下的表格中。然后根据他们 填写的表来分配书本,希望设计一个程序帮助老师求出所有可能的分配方案,使每个学生都满意。
A
B
C
□
E
张同学
Y
¥
王同学
Y
¥
Y
刘同学
¥
Y
孙同学
Y
李同学
Y
Y
输出结果：
zhang: C
wang: A
liu: B
sun: D
li: E
【算法分析】
可用穷举法,先不考虑“每人都满意” 这一条件,这样只剩“每人选一本且只能选一本”这一条件 在这个条件下,可行解就是五本书的所有全排列,一共有5！=120种。然后在120种可行解中一一删去不符 合“每人都满意”的解,留下的就是本题的解答。
为了编程方便,设1, 2, 3, 4, 5分别表示这五本书。这五个数的一种全排列就是五本书的一种分发 例如54321就表示第5本书（即E）分给张，第4本书（即D）分给王，……，第1本书（即A）分给李。“喜 爱书表”可以用二维数组来表示, 1表示喜爱, 0表示不喜爱。
【算法设计】
S1：产生5个数字的一个全排列；
S2：检查是否符合“喜爱书表”的条件，如果符合就打印出来；
S3 :检查是否所有的排列都产生了，如果没有产生完，则返回S1；
S4：结束。
上述算法有可以改进的地方。比如产生了一个全排列12345，从表中可以看出，选第一本书即给张同 学的书，1是不可能的，因为张只喜欢第3、4本书。这就是说，1XXXX—类的分法都不符合条件。由 此想到，如果选定第一本书后，就立即检查一下是否符合条件，发现1是不符合的，后面的四个数字就不 必选了，这样就减少了运算量。换句话说，第一个数字只在3、 4中选择，这样就可以减少3/5的运算量。 同理，选定了第一个数字后，也不应该把其他4个数字一次选定，而是选择了第二个数字后，就立即检查 是否符合条件。例如，第一个数选3，第二个数选4后，立即检查，发现不符合条件，就应另选第二个数。 这样就把34XXX一类的分法在产生前就删去了。又减少了一部分运算量。
综上所述，改进后的算法应该是:在产生排列时，每增加一个数，就检查该数是否符合条件，不符合， 就立刻换一个，符合条件后，再产生下一个数。因为从第I本书到第1+1本书的寻找过程是相同的，所以可 以用回溯算法。算法设计如下:
procedure try（i）;
begin
for j:=1 to 5 do
begin
if第i个同学分给第j本书符合条件then
b