搜索算法——比较讲解.ppt
文本预览下载声明
;搜索算法的基本思想 ;基本搜索算法一【回溯算法】;基本搜索算法一【回溯算法】;基本搜索算法一【回溯算法】;构造字串
生成长度为n的字串，其字符从26个英文字母的前p(p≤26)个字母中选取，使得没有相邻的子序列相等。例如p=3，n=5时
‘a b c b a’满足条件
‘a b c b c’不满足条件
输入：n，p
输出：所有满足条件的字串; 分析;procedure solve(at：integer)；{递归扩展第at个字母}
var
ch：char； i：integer；
begin
if at=n+1 {若产生了一个满足条件的字串，则输出，满足条件的字串数+1}
then begin
writeln(f，s)； inc(tl)；exit{回溯}
end；{then}
for ch←a to ed do {搜索每一个可填字母}
begin
s←s+ch；i←1；{检查当前字串是否符合条件}
while(i=at div 2)and(copy(s，length(s)-i+1，i)copy(s，length(s)-2*i+1，i)) do inc(i)；
;基本搜索算法;搜索策略;一些基本概念;八数码问题 ;综合数据库;产生式规则;控制策略 ;宽度优先搜索;八数码问题扩展过程 ;八数码搜索的主框架;八数码问题宽度优先算法框架;八数码参考程序（宽度优先）;procedure Initialize; {初始化}
var x,y : integer;
begin
Found:=false;
Closed:=0;open:=1;
with List[1] do begin
State:=Source;dep:=0;Father:=0;
For x:=1 to 3 do
For y:=1 to 3 do
if State[x,y]=0 then Begin x0:=x;y0:=y; End;
end;
end;
Function Same(A,B : T8no):Boolean; {判断A,B状态是否相等 }
Var i,j : integer;
Begin
Same:=false;
For i:=1 to 3 do for j:=1 to 3 do if A[i,j]B[i,j] then exit;
Same:=true;
End;
function not_Appear(new : tList):boolean; {判断new是否在List中出现 }
var i : integer;
begin
not_Appear:=false;
for i:=1 to open do if Same(new.State,List[i].State) then exit;
not_Appear:=true;
end;
procedure Move(n : tList;d : integer;var ok : boolean;var new : tList);
{将第d条规则作用于n得到new,OK是new是否可行的标志 }
var x,y : integer;
begin
X := n.x0 + Dir[d,1];
Y := n.y0 + Dir[d,2];
{判断new的可行性}
if not ((X 0) and ( X 4 ) and ( Y 0 ) and ( Y 4 )) then begin ok:=false;exit end;
OK:=true;;new.State:=n.State; {new=Expand(n,d)}
new.State[X,Y]:=0;
new.State[n.x0,n.y0]:=n.State[X,Y];
new.X0:=X;new.Y0:=Y;
end;
procedure Add(new : tList); {插入节点new}
begin
if not_Appear(new) then Begin {如果new没有在List出现 }
Inc(open);
显示全部