搜索算法-比较

搜索算法搜索算法的基本思想

搜索是计算机解题中常用的方法，它实质上是枚举法的应用。由于它相当于枚举法，所以其效率是相当地低。因此，为了提高搜索的效率，人们想出了很多剪枝的方法，如分枝定界，启发式搜索等等。在竞赛中，我们不仅要熟练掌握这些方法，而且要因地制宜地运用一些技巧，以提高搜索的效率。定义：Function

ExpendNode(Situation:Tsituation;ExpendWayNo:Integer):TSituation;表示对给出的节点状态Sitution采用第ExpendWayNo种扩展规则进行扩展，并且返回扩展后的状态。基本搜索算法一【回溯算法】回溯算法是采用了一种“走不通就掉头”思想作为其控制结构，用先根遍历的方法来构造解答树，可用于找所有解以及最优解。回溯算法对空间的消耗较少，当其与分枝定界法一起使用时，对于所求解在解答树中层次较深的问题有较好的效果。但应避免在后继节点可能与前继节点相同的问题中使用，以免产生循环。基本搜索算法一【回溯算法】<Type>

Node(节点类型)＝Record

Situtation:TSituation（当前节点状态）;Way-NO:Integer（已使用过的扩展规则的数目）;End基本搜索算法一【回溯算法】[递归算法]Procedure

BackTrack(Situation:TSituation;deepth:Integer);Var

i:Integer;Begin

If

deepth>Maxthen(空间达到极限,跳出本过程);IfSituation=Targetthen(找到目标);

ForI:=1to

TotalExpendMethod

do

Begin

BackTrack(ExpendNode(Situation,I),deepth+1);End-For;End;构造字串

生成长度为n的字串，其字符从26个英文字母的前p(p≤26)个字母中选取，使得没有相邻的子序列相等。例如p=3，n=5时

‘abcba’满足条件

‘abcbc’不满足条件输入：n，p输出：所有满足条件的字串

分析状态：待扩展的字母序号at。实际上字串s亦参与了递归运算，但是由于该变量的存储量太大，因此我们将s设为全局变量；

边界条件和目标状态：产生了一个满足条件的字串，即at=n+1；搜索范围：第at位置可填的字母集{‘a’..chr(ord(‘a’)+p-1)}；约束条件：当前字串没有相邻子串相等的情况varn，p：integer；{字串长度和可选字母的个数}

tl：longint；{满足条件的字串数}ed：char；{可选字母集中的最大字母}s：string；{满足条件的字串}proceduresolve(at：integer)；{递归扩展第at个字母}

var

ch：char；

i：integer；

beginifat=n+1{若产生了一个满足条件的字串，则输出，满足条件的字串数+1}thenbegin

writeln(f，s)；inc(tl)；exit{回溯}end；{then}forch←'a'toeddo{搜索每一个可填字母}begins←s+ch；i←1；{检查当前字串是否符合条件}

while(i<=atdiv2)and(copy(s，length(s)-i+1，i)<>copy(s，length(s)-2*i+1，i))doinc(i)；ifi>atdiv2thensolve(at+1)；{若当前字串符合条件，则递归扩展下一个字母}

delete(s，length(s)，1){恢复填前的字串}

end{for}end；{solve}begin

readln(n，p)；{输入字串长度和前缀长短}ed←chr(ord('a')+p-1)；{计算可选字母集中的最大字母}s←''；tl←0；{满足条件的字串初始化为空，字串数为0}solve(1)；{从第1个字母开始递归计算所有满足条件的字串}

writeln('Total：'，tl)；{输出满足条件的字串数}

end.{main}基本搜索算法[深度搜索与广度搜索]深度搜索与广度搜索的区别：深度搜索下一次扩展的是本次扩展出来的子节点中的一个，而广度搜索扩展的则是本次扩展的节点的兄弟节点。在具体实现上为了提高效率,所以采用了不同的数据结构。广度搜索是求解最优解的一种较好的方法，而深度搜索多用于只要求解，并且解答树中的重复节点较多并且重复较难判断时使用，但往往可以用A*或回溯算法代替。搜索策略综合数据库

与问题相关的所有数据元素构成的集合，用来表述问题状态或有关事实。产生式规则 构建了综合数据库以后，还需要研究问题的移动规则，称为产生式规则。搜索策略 搜索策略的实质是确定如何选取规则的方式。有两种基本方式：一种是不考虑给定问题所具有的特定知识，系统根据事先确定好某种固定顺序，依次调用规则或随机调用规则，这实际上是盲目搜索的方法。另一种是考虑问题领域可应用的知识，动态地确定规则的排列次序，优先调用较合适的规则使用，这就是通常所说的启发式搜索策略。一些基本概念节点：记录扩展的状态。弧/边：记录扩展的路径。搜索树：描述搜索扩展的整个过程。节点的耗散值 令C(i,j)为从节点ni到nj的这段路径（或者弧）的耗散值,一条路径的耗散值就等于连接这条路径各节点间所有弧的耗散值总和。可以用递归公式描述如下：

C(ni,t)=C(ni,nj)+C(nj,t)4搜索树根节点叶子节点4,5,6,7,88123567八数码问题

在3*3组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1—8中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格中移动，如右图所示。这样通过移动将牌就可以不断改变的布局结构，给出一个初始布局（称初始状态）和一个目标布局（称目标状态），问如何移动将牌，才能实现从初始状态到目标状态的转换。综合数据库{Pxy}，其中1<=x,y<=3，Pxy∈{0,1,2,3,4,5,6,7,8}，且Pxy互不相等

用Pascal语言描述如下：typeT8no=array[1..3,1..3]ofinteger;{棋盘状态}

TList=record{描述一个节点}Father:integer;

{父指针}

dep:byte;

{深度}x,y:byte; {空格的位置}state:T8no;

end;constMax=10000;vars,t:T8no;{s为初始状态，t为目标状态}List:array[0..max]ofTList;{综合数据库}产生式规则if条件then规则；设Pxy表示将牌第x行第y列的数码，m,n表示数码空格所在的行列值，记Pm,n=0,则可以得到如下四条规则：

①ifn-1>=1thenbeginPm,n:=Pm,n-1­

;Pm,n-1­

­:=0end;②ifm-1>=1thenbeginPm,n:=Pm-1,n;Pm-1,n:=0end;③ifn+1<=3thenbeginPm,n:=Pm,n+1;Pm,n+1:=0end;④ifm+1<=3thenbeginPm,n:=Pm+1­,n;Pm+1­,n:=0end;ConstDir:array[1..4,1..2]ofinteger{对应四种产生式规则}=((1,0),(-1,0),(0,1),(0,-1));控制策略

PROCEDUREProduction-System；DATA初始化数据库Repeat

在规则集中选择某一条可作用于DATA的规则R

DATAR作用于DATA后得到的结果

UntilDATA满足结束条件宽度优先搜索PROCEDUREBFS-SEARCH;(算法1)1.

G:=G0;2.

open:=(Source);3.

closed:=nil;4.

Repeat5.

IFOPEn=nilthenExit(Fail);6.

n:=FIRST(OPEn);Remove(n,open);7.

Add(n,closed);8.

ifn=GoalthenExit(Success);9.

mi:=Expand(n);10.

对mi，舍去在G中已经出现的节点；11.

将图中未出现的mi加入到open表的表尾12.

Add(mi,G);13.

Untilfalse;

八数码问题扩展过程

八数码搜索的主框架

List[1]=source;closed:=0;open:=1;{初始化open,closed,List}

Repeat

closed:=closed+1;n:=List[closed];{取出closed对应的节点}

Forx:=1to4do[

new:=Move(n,4);{按第x条规则扩展，得到new}

ifnot_Appear(new,List)then{判重}

[open:=open+1;List[open]:=new;{加入新节点到open}

List[open].Father:=closed;{修改指针}

ifList[open]=GoalthenGetOut;

];

]

Untilclosed<open;八数码问题宽度优先算法框架List[1]=source;closed:=0;open:=1;{加入初始节点,List为扩展节点的表}Repeatclosed:=closed+1;n:=List[closed];{取出closed对应的节点}Forx:=1to4do[new:=Move(n,4);{对n节点使用第x条规则，得到new}ifnot_Appear(new,List)then[{如果new没有在List中出现}open:=open+1;List[open]:=new;{加入新节点到open}

List[open].Father:=closed;{修改指针}ifList[open]=GoalthenGetOut;];]Untilclosed<open;八数码参考程序（宽度优先）program8no_bfs;{八数码的宽度优先搜索算法}ConstDir:array[1..4,1..2]ofinteger

{四种移动方向，对应产生式规则}=((1,0),(-1,0),(0,1),(0,-1));n=10000;TypeT8no=array[1..3,1..3]ofinteger;

TList=recordFather:integer;

{父指针}

dep:byte;

{深度}X0,Y0:byte; {0的位置}State:T8no;

{棋盘状态}end;Var

Source,Target:T8no;List:array[0..10000]ofTList;{综合数据库}

Closed,open,Best:integer{Best表示最优移动次数}Answer:integer;{记录解}Found:Boolean;{解标志}procedureGetInfo;{读入初始和目标节点}

var

i,j:integer;beginfori:=1to3doforj:=1to3doread(Source[i,j]);fori:=1to3doforj:=1to3doread(Target[i,j]);end;procedureInitialize;{初始化}

var

x,y:integer;beginFound:=false;Closed:=0;open:=1;withList[1]dobeginState:=Source;dep:=0;Father:=0;Forx:=1to3doFory:=1to3doifState[x,y]=0thenBeginx0:=x;y0:=y;End;end;end;FunctionSame(A,B:T8no):Boolean;{判断A,B状态是否相等}

Var

i,j:integer;BeginSame:=false;Fori:=1to3doforj:=1to3doifA[i,j]<>B[i,j]thenexit;Same:=true;End;functionnot_Appear(new:tList):boolean;{判断new是否在List中出现}

vari:integer;begin

not_Appear:=false;fori:=1toopendoifSame(new.State,List[i].State)thenexit;

not_Appear:=true;end;procedureMove(n:tList;d:integer;varok:boolean;varnew:tList);{将第d条规则作用于n得到new,OK是new是否可行的标志}

var

x,y:integer;beginX:=n.x0+Dir[d,1];Y:=n.y0+Dir[d,2];{判断new的可行性}ifnot((X>0)and(X<4)and(Y>0)and(Y<4))thenbeginok:=false;exitend;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;procedureAdd(new:tList);{插入节点new}beginifnot_Appear(new)thenBegin{如果new没有在List出现}

Inc(open);{new加入open表}

List[open]:=new;end;end;procedureExpand(Index:integer;varn:tList);{扩展n的子节点}

vari:integer;new:tList;OK:boolean;BeginifSame(n.State,Target)thenbegin{如果找到解}Found:=true;Best:=n.Dep;Answer:=Index;Exit;end;Fori:=1to4dobegin{依次使用４条规则}

Move(n,i,OK,new);ifnotokthencontinue;new.Father:=Index;

new.Dep:=n.dep+1;

Add(new);end;end;

procedureGetOutInfo;{输出}procedureOutlook(Index:integer);{递归输出每一个解}

var

i,j:integer;beginifIndex=0thenexit;

Outlook(List[Index].Father);withList[Index]dofori:=1to3dobeginforj:=1to3dowrite(State[i,j],'');

writeln;end;

writeln;end;begin

Writeln('Total=',Best);

Outlook(Answer);end;procedureMain;{搜索主过程}beginRepeat

Inc(Closed);

Expand(Closed,List[Closed]);{扩展Closed}Until(Closed>=open)orFound;ifFoundthenGetOutInfo{存在解}elseWriteln('noanswer');{无解}end;Begin

Assign(Input,'input.txt');ReSet(Input);

Assign(Output,'Output.txt');ReWrite(Output);

GetInfo;Initialize;Main;

Close(Input);Close(Output);End.深度优先搜索框架PROCEDUREDFS-SEARCH;(算法2)1.

G:=G0;2.

open:=(Source);3.

closed:=nil;4.

Repeat5.

IFOPEn=nilthenExit(Fail);6.

n:=FIRST(open);Remove(n,open);7.

Add(n,closed);8.

ifn=GoalthenExit(Success);9.

mi:=Expand(n);10.

将图中未出现的mi加入到open表的表头(压栈)11.

Add(mi,G);12.

Untilfalse;

深度优先搜索递归形式procedureDFS_recursive(i);(算法3)

ifn=targetthen更新当前最优值并保存路径;

forr:=1to规则数

do[

new:=Expand(n,r)

if值节点new符合条件

then[

产生的子节点new压入栈;

DFS_recursive(i+1);

栈顶元素出栈;

]

]

programDFS;

初始化;

DFS_recursive(1);八数码问题的递规搜索PROCEDURERecursive(step);ifstep>=bestthenexit;{最优化剪枝}if(List[step]=Goal)and(step<best)thenbest=step; {记录当前最少步骤}forx:=1to4do[ {对使用第x条规则扩展} new:=expand(List[step],4);ifnot_Appear(new,List)then{判重}

List[step]:=new;{插入当前节点}

对new进行标号;

Recursive(step); {递归搜索下一层}

清除new的标号;]PROCEDUREDFSList[1]:=Source;Best:=maxint;Recursive(1);

输出递归与非递归方式的比较两种方式本质上是等价，但两者也时有区别的。递归方式实现简单，非递归方式较之比较复杂；递归方式需要利用栈空间，如果搜索量过大的话，可能造成栈溢出，所以在栈空间无法满足的情况下，选用非递归实现方式较好。启发式搜索启发式搜索是利用问题拥有的启发信息来引导搜索，达到减少搜索范围，降低问题复杂度的目的。这种利用启发信息的搜索过程称为启发式搜索方法。评价函数 为了提高搜索效率，引入启发信息来进行搜索，在启发式搜索过程中，要对open表进行排序，这就需要有一种方法来计算待扩展节点有希望通向目标节点的程度，我们总希望能找到最有希望通向目标节点的待扩展节点优先扩展。一种常用的方法就是定义评价函数f(evaluationfuntion)对各个节点进行计算，其目的就是估算出“有希望”的节点来。“不在位奖牌个数”作为启发信息的搜索过程双向宽度优先搜索双向宽度优先搜索注意的方面规则必须可逆随时判重交叉扩展搜索算法的优化一、双向广度搜索二、分支定界三、A*算法搜索算法的优化一、双向广度搜索从正反两个方向进行广度搜索，理想情况下可以减少二分之一的搜索量，从而提高搜索速度。从初始状态和目标状态两个方向同时进行扩展，如果两棵解答树在某个节点第一次发生重合，则该节点所连接的两条路径所拼成的路径就是最优解。搜索算法的优化添加一张节点表，作为反向扩展表。在正向扩展出一个节点后，需在反向表中查找是否有重合节点。反向扩展时与之相同。搜索算法的优化对双向广度搜索算法的改进：略微修改一下控制结构，每次while循环时只扩展正反两个方向中节点数目较少的一个，可以使两边的发展速度保持一定的平衡，从而减少总扩展节点的个数，加快搜索速度。搜索算法的优化例题1：(最短编号序列)

表A和表B各含k(k<=20)个元素，元素编号从1到k。两个表中的每个元素都是由0和1组成的字符串。（不是空串）字符串的长度<=20。例如下表的A和B两个表，每个表都含3个元素（k=3）。

元素编号

字符串11210111310

元素编号

字符串111121030表B表A搜索算法的优化

对于表A和表B，存在一个元素编号的序列2113，分别用表A中的字符串和表B中的字符串去置换相应的元素编号，可得相同的字符串序列101111110，见下表。具有上述性质的元素编号序列称之为S(AB)。对于上例S(AB)=2113。编写程序：从文件中读入表A和表B的各个元素，寻找一个长度最短的元素编号序列S(AB)。（若找不到长度<=100的编号序列，则输出“NoAnswer”。

元素编号序列2113

用表A的字符串替换101111110

用表B的字符串替换101111110【分析】由于表Ａ和表Ｂ不确定，所以不可能找到一种数学的方法。因为是求最优解，不适合用深度优先搜索，所以必须采用广度优先搜索的方法。但是当表Ａ和表Ｂ中的元素过多时，直接搜索会超时。必须对搜索的算法加以改进。此题的规则既可以正向使用，又可以逆向使用，因此可以采用双向搜索。搜索算法的优化在大方法确定后，算法的框架就已经基本形成，再对算法进行适当地改进：

1、存储当前的Ａ串和Ｂ串是很费空间的，但因为Ａ串和Ｂ串的大部分相同，故只需记录不同部分，并作个标记。

2、为了保证两个方向扩展结点的速度相对平衡，可以采取每次扩展结点数较少的方向，而不是两方向轮流扩展。搜索算法的优化二、分支定界分支定界实际上是A*算法的一种雏形，其对于每个扩展出来的节点给出一个预期值，如果这个预期值不如当前已经搜索出来的结果好的话，则将这个节点(包括其子节点)从解答树中删去，从而达到加快搜索速度的目的。

搜索算法的优化二、分支定界解题过程：１、添加一个全局变量BestAnswer，记录当前最优解。２、在每次生成一个节点时，计算其预期值，并与BestAnswer比较。如果不好，则调用回溯过程。搜索算法的优化三、A*算法A*算法中更一般的引入了一个估价函数f,其定义为f=g+h。其中g为到达当前节点的耗费，而h表示对从当前节点到达目标节点的耗费的估计。其必须满足两个条件：１、h必须小于等于实际的从当前节点到达目标节点的最小耗费h*。２、f必须保持单调递增。搜索算法的优化三、A*算法

A*算法的控制结构与广度搜索的十分类似，只是每次扩展的都是当前待扩展节点中f值最小的一个，如果扩展出来的节点与已扩展的节点重复，则删去这个节点。如果与待扩展节点重复，如果这个节点的估价函数值较小，则用其代替原待扩展节点。当A*算法出现数据溢出时，从待扩展节点中取出若干个估价函数值较小的节点，然后放弃其余的待扩展节点，从而可以使搜索进一步的进行下去。搜索算法的优化搜索剪枝应用举例

例题2：（任务安排）

Ｎ个城市，若干城市间有道路相连，一辆汽车在城市间运送货物，总是从城市１出发，又回到城市１。该车每次需完成若干个任务，每个任务都是要求该车将货物从一个城市运送至另一个。例如若要完成任务２－>6，则该车一次旅程中必含有一条子路径。先到２，再到６。编程由文件读入道路分布的领接矩阵，然后对要求完成的若干任务，寻找一条旅行路线，使得在完成任务最多的前提下，经过的城市总次数最少。如上例中经过城市总次数为８，城市１和２各经过２次均以２次计（起点不计），Ｎ<60。 搜索剪枝应用举例

如下图所示，如果要求的任务是２－>３，２－>４，３－>１，２－>５，６－>４，则一条完成全部任务的路径是１－>２－>３－>１－>２－>５－>６－>４－>１。

【分析】如果考虑从城市i出发，搜索所有相邻的城市，再根据当前所处的城市，确定任务的完成情况，从中找到最优解。这种搜索的效率极低。我们只需到达上货和下货的城市，其它的城市仅作为中间过程。因此，首先必须确定可能和不可能完成的任务，然后求出任意两城市间的最短路径。在搜索时，就只需考虑有货要上的城市，或者