搜索教案.ppt

搜索教案
朱全民
搜索的本质
一、两种题型:
。对于这一类试题,我们尽量用解析法求解。
,或即使有一定的数学模型,但采用数学方法解决有一定困难。对于这一类试题,我们只好用模拟或搜索求解。
二、搜索的本质:
搜索的本质就是逐步试探,在试探过程中找到问题的解。三、搜索问题考察的范围


简单回溯法
N皇后问题
背包问题
寻找国都名
……
N皇后问题
在N*N的棋盘上放置N个皇后而彼此不受攻击(即在棋盘的任一行,任一列和任一对角线上不能放置2个皇后),编程求解所有的摆放方法。
八皇后的两组解
基本思想
由于皇后的摆放位置不能通过某种公式来确定,因此对于每个皇后的摆放位置都要进行试探和纠正,这就是“回溯”的思想。
在N个皇后未放置完成前,摆放第i个皇后和第i+1个皇后的试探方法是相同的,因此完全可以采用递归的方法来处理。
算法基本框架
Procedure Try(I:integer);
{搜索第I行皇后的位置}
var
j:integer;
begin
if I=n+1 then 输出方案;
for j:=1 to n do
if 皇后能放在第I行第J列的位置 then begin
放置第I个皇后;
对放置皇后的位置进行标记;
Try(I+1)
对放置皇后的位置释放标记;
end;
end;
细节处理
怎样判断某列放置了皇后
A:array [1..MaxN] of Boolean;
{竖线被控制标记}
怎样判断某对角线上放置了皇后
B:array [2..MaxN * 2] of Boolean;
{左上到右下斜线被控制标记}
C:array [1–MaxN..MaxN–1] of Boolean;
{左下到右上斜线被控制标记}
0,1背包问题
已知一个容量大小为M重量的背包和N种物品,每种物品的重量为Wi。若将物品放入背包将得到Pi的效益,求怎样选取物品将得到效益最大
算法分析
本题可以用递归求解:设当前有N个物品,容量为M;因为这些物品要么选,要么不选,我们假设选的第一个物品编号为I(1~I-1号物品不选),问题又可以转化为有N-I个物品(即第I+1~N号物品),容量为M-Wi的子问题……如此反复下去,然后在所有可行解中选一个效益最大的便可。
另外,为了优化程序,我们定义一个函数如下:
F[I]表示选第I~N个物品能得到的总效益。不难推出:
F[N]=Pn
F[I]=F[I+1]+Pi (I=1…N-1)
假设当前已选到第I号物品,如果当前搜索的效益值+F[I+1]的值仍然比当前的最优值小,则没有必要继续搜索下去。
算法框架
Procedure Search(I:Integer; J:Byte); {递归求解}
Var K :Byte;
Begin
If Now+F[J]<=Ans Then Exit; {如果没有必要搜索下去}
If Now>Ans Then Begin {修改最优解}
Ans:=Now;
Out:=Ou;
End;
For K:=J To N Do {选取物品}
If W[K]<=I Then Begin
Now:=Now+P[K];
Ou[K]:=True;
Search(I-W[K],K+1);
Now:=Now-P[K];
Ou[K]:=False;
End;
End;