搜索算法——比较

《搜索算法——比较》由会员分享，可在线阅读，更多相关《搜索算法——比较（53页珍藏版）》请在金锄头文库上搜索。

1、搜索算法搜索算法搜索算法的基本思想 n搜索是计算机解题中常用的方法，它实质上是 枚举法的应用。由于它相当于枚举法，所以其 效率是相当地低。因此，为了提高搜索的效率 ，人们想出了很多剪枝的方法，如分枝定界， 启发式搜索等等。在竞赛中，我们不仅要熟练 掌握这些方法，而且要因地制宜地运用一些技 巧，以提高搜索的效率。n定义：Function ExpendNode(Situation:Tsituation;ExpendWay No:Integer):TSituation;表示对给出的节点状态 Sitution采用第ExpendWayNo种扩展规则进行 扩展，并且返回扩展后的状态。 基本搜索算法一【回溯

2、算法】n回溯算法是采用了一种“走不通就掉头”思想 作为其控制结构，用先根遍历的方法来构造 解答树，可用于找所有解以及最优解。n回溯算法对空间的消耗较少，当其与分枝定 界法一起使用时，对于所求解在解答树中层 次较深的问题有较好的效果。但应避免在后 继节点可能与前继节点相同的问题中使用， 以免产生循环。基本搜索算法一【回溯算法】n n Node(节点类型)Record Situtation:TSituation（当前节点状态） ; Way-NO:Integer（已使用过的扩展 规则的数目）; nEnd基本搜索算法一【回溯算法】递归算法 Procedure BackTrack(Situation:T

3、Situation;deepth:Integer); Var i:Integer; Begin If deepthMax then (空间达到极限,跳出本过程); If Situation=Target then (找到目标);For I:=1 to TotalExpendMethod do Begin BackTrack(ExpendNode(Situation,I),deepth+1); End-For; End;构造字串生成长度为n的字串，其字符从26个英文字母的 前p(p26)个字母中选取，使得没有相邻的子序列相 等。例如p=3，n=5时a b c b a满足条件 a b c b c不

4、满足条件输入：n，p输出：所有满足条件的字串分析状态：待扩展的字母序号at。实际上字串s亦参与了递归运算，但是由于该变 量的存储量太大，因此我们将s设为全局变量；n 边界条件和目标状态：产生了一个满足条件的字串，即at=n+1； 搜索范围：第at位置可填的字母集a. chr(ord(a)+p-1)； 约束条件：当前字串没有相邻子串相等的情况nvarn n，p：integer；字串长度和可选字母的个数n tl：longint； 满足条件的字串数n ed：char； 可选字母集中的最大字母n s：string； 满足条件的字串procedure solve(at：integer)；递归扩展第at

5、个字母varch：char； i：integer；beginif at=n+1 若产生了一个满足条件的字串， 则输出，满足条件的字串数+1then beginwriteln(f，s)； inc(tl)；exit回溯 end；thenfor cha to ed do 搜索每一个可填字母 beginss+ch；i1；检查当前字串是否符合条件 while(icopy(s，length(s)-2*i+1，i) do inc(i)； if iat div 2 then solve(at+1)；若当前 字串符合条件，则递归扩展下一个字母delete(s，length(s)，1)恢复填前的字 串endfor

6、end；solvebeginreadln(n，p)；输入字串长度和前缀长 短edchr(ord(a)+p-1)；计算可选字母 集中的最大字母s； tl0；满足条件的字串初始化 为空，字串数为0solve(1)；从第1个字母开始递归计算所 有满足条件的字串writeln(Total：，tl)；输出满足条 件的字串数end.main基本搜索算法深度搜索与广度搜索n深度搜索与广度搜索的区别：深度搜索下一 次扩展的是本次扩展出来的子节点中的一个 ，而广度搜索扩展的则是本次扩展的节点的 兄弟节点。n在具体实现上为了提高效率,所以采用了不同 的数据结构。n广度搜索是求解最优解的一种较好的方法， 而深度搜索

7、多用于只要求解，并且解答树中 的重复节点较多并且重复较难判断时使用， 但往往可以用A*或回溯算法代替。搜索策略n综合数据库 与问题相关的所有数据元素构成的集合 ，用来表述问题 状态或有关事实 。n产生式规则 构建了综合数据库以后，还需要研究问题的移动规则，称 为产生式规则。 n搜索策略 搜索策略的实质是确定如何选取规则的方式。有两种基本 方式：一种是不考虑给定问题所具有的特定知识，系统根 据事先确定好某种固定顺序，依次调用规则或随机调用规 则，这实际上是盲目搜索的方法。另一种是考虑问题领域 可应用的知识，动态地确定规则的排列次序，优先调用较 合适的规则使用，这就是通常所说的启发式搜索策略。一些

8、基本概念n节点：记录扩展的状态。n弧/边：记录扩展的路径。n搜索树：描述搜索扩展的整 个过程。n节点的耗散值 令C(i,j)为从节点ni到nj的这 段路径（或者弧）的耗散值, 一条路径的耗散值就等于连 接这条路径各节点间所有弧 的耗散值总和。可以用递归 公式描述如下： C(ni ,t)= C(ni , nj)+ C(nj , t)4搜索树根节点叶子节 点 4,5,6,7,88123567八数码问题 n在3*3组成的九宫格棋盘上，摆有八个将牌，每一个将牌都 刻有18中的某一个数码。棋盘中留有一个空格，允许其 周围的某一个将牌向空格中移动，如右图所示。这样通过 移动将牌就可以不断改变的布局结构，给

9、出一个初始布局 （称初始状态）和一个目标布局（称目标状态），问如何 移动将牌，才能实现从初始状态到目标状态的转换。综合数据库nPxy，其中1=1 then begin Pm, n:=Pm,n -1 ; Pm,n -1 :=0 end; if m - 1=1 then begin Pm, n:=Pm-1, n ; Pm-1, n :=0 end; if n + 1Bi,j then exit;n Same:=true;n End;n function not_Appear(new : tList):boolean; 判断new是否在List中出现 n var i : integer;n begi

10、nn not_Appear:=false;n for i:=1 to open do if Same(new.State,Listi.State) then exit;n not_Appear:=true;n end;n procedure Move(n : tList;d : integer;var ok : boolean;var new : tList);n 将第d条规则作用于n得到new,OK是new是否可行的标志 n var x,y : integer;n beginn X := n.x0 + Dird,1;n Y := n.y0 + Dird,2;n 判断new的可行性n if n

11、ot (X 0) and ( X 0 ) and ( Y =open) or Found;n if Found then GetOutInfo 存在解n else Writeln(no answer); 无解n end;nBeginn Assign(Input,input.txt);ReSet(Input);n Assign(Output,Output.txt);ReWrite(Output);n GetInfo;n Initialize;n Main;n Close(Input);Close(Output);nEnd.深度优先搜索框架PROCEDURE DFS-SEARCH;(算法2) 1.

12、 G:=G0; 2. open:=(Source) ; 3. closed:=nil; 4. Repeat 5. IF OPEn=nil then Exit(Fail); 6. n:=FIRST(open);Remove(n,open); 7. Add(n,closed); 8. if n=Goal then Exit(Success); 9. mi:=Expand(n); 10. 将图中未出现的mi加入到open表的表头(压栈) 11. Add(mi,G); 12. Until false;深度优先搜索递归形式procedure DFS_ recursive(i); (算法3)if n=ta

13、rget then 更新当前最优值并保存路径;for r:=1 to 规则数 do new:=Expand(n,r)if 值节点new符合条件 then 产生的子节点new压入栈;DFS_recursive(i+1);栈顶元素出栈;program DFS;初始化;DFS_recursive(1);八数码问题的递规搜索PROCEDURE Recursive(step);if step =best then exit ; 最优化剪枝if (Liststep=Goal) and (step6，则该车 一次旅程中必含有一条子路径。先到，再到。编程由文件读入道路分布的领接矩阵，然后对要求完 成的若干任务

14、，寻找一条旅行路线，使得在完成任务最多 的前提下，经过的城市总次数最少。如上例中经过城市总 次数为，城市和各经过次均以次计（起点不计 ）， ，则一条完成全部 任务的路径是 。【分析分析】如果考虑从城市i出发，搜索所有相邻的 城市，再根据当前所处的城市，确定任务的完成 情况，从中找到最优解。这种搜索的效率极低。n我们只需到达上货和下货的城市，其它的城市 仅作为中间过程。因此，首先必须确定可能和不 可能完成的任务，然后求出任意两城市间的最短 路径。在搜索时，就只需考虑有货要上的城市， 或者是要运到该城市的货全在车上两种情况。同 时，还可以设定两个简单的槛值。如果当前费用 +还需达的城市=当前最优解，或当前费用+返 回城市1的费用=当前最优解，则不需继续往下 搜索。搜索剪枝应用举例搜索剪枝应用举例 例题3：（多处理机调度问题）有n相同的处理机P1,P2Pn,和m个独立的作业 J1,J2jm,处理机以互不相关的方式处理作业，现约定 任何作业可以在任何一台处理机上运行，但未完工之前 不允许中断作业，作业也不能拆分成更小的作业，已知 作业Ji需要处理机处理的时间为Ti（i=1,2m）。编程 完成以下两个任务：任务一：己知n、m和Ti（i=1,2m），求解一个 调度方案，使得完成这