2024年5月11日发(作者：win7防火墙无法更改设置)

深度优先搜索算法教程

[例1] 有A、B、C、D、E五本书，要分给张、王、刘、赵、钱五位同学，每人只能选

一本。事先让每个人将自己喜爱的书填写在下表中。希望你设计一个程序，打印分书的所有

可能方案，当然是让每个人都满意。（如下图所示）

[分析] 这个问题中喜爱的书是随机的，没有什么规律，所以用穷举法比较合适。

为编程方便，用1、2、3、4、5分别表示这五本书。这五本书的一种全排列就是五本书

的一种分法。例如54321表示第5本书（即E）分给张，第4本书（即D分给王，）……第1

本书（即A分给钱）。“喜爱书表”可以用二维数组来表示，1表示喜爱，0表示不喜爱。

[算法设计]：

1、 产生5个数字的一个全排列；

2、 检查是否符合“喜爱书表”的条件，如果符合就打印出来。

3、 检查是否所有排列都产生了，如果没有产生完，则返回1。

4、 结束。

[算法改进]：因为张只喜欢第3、4本书，这就是说，1* * * *一类的分法都不符合条件。

所以改进后的算法应当是：在产生排列时，每增加一个数，就检查该数是否符合条件，不符

合，就立即换一个，符合条件后，再产生下一个数。因为从第i本书到第i+1本书的寻找过

程是相同的，所以可以用递归算法。算法如下：

procedure try(i); {给第I个同学发书}

begin

for j:=1 to 5 do

begin

if 第i个同学分给第j本书符合条件 then

begin

记录第i个数; {即j值}

if i=5 then 打印一个解 else try(i+1);

删去第i个数字

end