2022年常用搜索算法 .pdf

《2022年常用搜索算法 .pdf》由会员分享，可在线阅读，更多相关《2022年常用搜索算法 .pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、常用搜索算法面试笔试中经常会问到一些搜索算法，现在总结如下：搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。 搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。所有的搜索算法从其最终的算法实现上来看，都可以划分成两个部分控制结构和产生系统，而所有的算法的优化和改进主要都是通过修改其控制结构来完成的。现在主要对其控制结构进行讨论，因此对其产生系统作如下约定：Function ExpendNode(Situation:Tsituation;ExpendWayNo:Integer):TSituation; 表示对

2、给出的节点状态Sitution采用第 ExpendWayNo种扩展规则进行扩展，并且返回扩展后的状态。（本文所采用的算法描述语言为类Pascal 。）第一部分基本搜索算法一、回溯算法回溯算法是所有搜索算法中最为基本的一种算法，其采用了一种 “ 走不通就掉头 ” 思想作为其控制结构，其相当于采用了先根遍历的方法来构造解答树，可用于找解或所有解以及最优解。具体的算法描述如下： 非递归算法 Node( 节点类型 ) Record Situtation:TSituation（当前节点状态）; Way-NO:Integer（已使用过的扩展规则的数目）; End List( 回溯表 ):Array1.Ma

3、x(最大深度 ) of Node; pos( 当前扩展节点编号):Integer; List-0; pos-1; List1.Situation0(有路可走 ) and (未达到目标 ) do Begin If pos=Max then (数据溢出 ,跳出主程序 ); Listpos.Way-NO:=Listpos.Way-No+1; If (Listpos.Way-NOMax then (空间达到极限 ,跳出本过程 ); If Situation=Target then (找到目标 ); For I:=1 to TotalExpendMethod do Begin BackTrack(Exp

4、endNode(Situation,I),deepth+1); End-For; End; 范例： 一个 M*M的棋盘上某一点上有一个马，要求寻找一条从这一点出发不重复的跳完棋盘上所有的点的路线。评价： 回溯算法对空间的消耗较少，当其与分枝定界法一起使用时，对于所求解在解答树中层次较深的问题有较好的效果。但应避免在后继节点可能与前继节点相同的问题中使用，以免产生循环。二、深度搜索与广度搜索深度搜索与广度搜索的控制结构和产生系统很相似，唯一的区别在于对扩展节点选取上。由于其保留了所有的前继节点， 所以在产生后继节点时可以去掉一部分重复的节点，从而提高了搜索效率。这两种算法每次都扩展一个节点的所有

5、子节点，而不同的是， 深度搜索下一次扩展的是本次扩展出来的子节点中的一个，而广度搜索扩展的则是本次扩展的节点的兄弟节点。在具体实现上为了提高效率,所以采用了不同的数据结构. 广度搜索 Node( 节点类型 ) Record Situtation:TSituation（当前节点状态）; Level:Integer(当前节点深度 ); Last :Integer(父节点 ); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 11 页 - - - - - - - - - End

6、 List( 节点表 ):Array1.Max(最多节点数 ) of Node(节点类型 ); open( 总节点数 ):Integer; close( 待扩展节点编号):Integer; New-S:TSituation;(新节点 ) List-0; open-1; close-0; List1.Situation- 初始状态 ; List1.Level:=1; List1.Last:=0; While (close (open ( 未找到目标节点) do Begin close:=close+1; For I:=1 to TotalExpendMethod do（扩展一层子节点）Begin

7、 New-S:=ExpendNode(Listclose.Situation,I); If Not (New-S in List) then ( 扩展出的节点从未出现过) Begin open:=open+1; Listopen.Situation:=New-S; Listopen.Level:=Listclose.Level+1; Listopen.Last:=close; End-If End-For; End-While; 深度搜索 Open:Array1.Max of Node;(待扩展节点表 ) Close:Array1.Max of Node;(已扩展节点表 ) openL,clo

8、seL:Integer;(表的长度 ) New-S:Tsituation;(新状态 ) Open-0; Close-0; OpenL-1;CloseL-0; Open1.Situation- 初始状态 ; Open1.Level-1; Open1.Last0) and (closeL Begin closeL:=closeL+1; ClosecloseL:=OpenopenL; openL:=openL-1; For I:=1 to TotalExpendMethod do（扩展一层子节点）Begin New-S:=ExpendNode(ClosecloseL.Situation,I); If

9、 Not (New-S in List) then ( 扩展出的节点从未出现过) Begin openL:=openL+1; OpenopenL.Situation:=New-S; OpenopenL.Level:=ClosecloseL.Level+1; OpenopenL.Last:=closeL; End-If End-For; End; 范例：迷宫问题，求解最短路径和可通路径。评价： 广度搜索是求解最优解的一种较好的方法，在后面将会对其进行进一步的优化。而深度搜索多用于只要求解，并且解答树中的重复节点较多并且重复较难判断时使用，但往往可以用A* 或回溯算法代替。第二部分搜索算法的优化一

10、、双向广度搜索广度搜索虽然可以得到最优解，但是其空间消耗增长太快。但如果从正反两个方向进行广度搜索，理想情况下可以减少二分之一的搜索量，从而提高搜索速度。范例：有 N 个黑白棋子排成一派，中间任意两个位置有两个连续的空格。每次空格可以与序列中的某两个棋子交换位置，且两子的次序不变。要求出入长度为length的一个初始状态和一个目标状态，求出最少的转化步数。问题分析：该题要求求出最少的转化步数，但如果直接使用广度搜索，很容易产生数据溢出。但如果从初始状态和目标状态两个方向同时进行扩展，如果两棵解答树在某个节点第一次发生重合，则该节点所连接的两条路径所拼成的路径就是最优解。对广度搜索算法的改进：。

11、添加一张节点表，作为反向扩展表。在 while循环体中在正向扩展代码后加入反向扩展代码，其扩展过程不能与正向过程共享一个for 循环。在正向扩展出一个节点后，需在反向表中查找是否有重合节点。反向扩展时名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11 页 - - - - - - - - - 与之相同。对双向广度搜索算法的改进：略微修改一下控制结构，每次while循环时只扩展正反两个方向中节点数目较少的一个，可以使两边的发展速度保持一定的平衡，从而减少总扩展节点的个数，加

12、快搜索速度。二、分支定界分支定界实际上是A* 算法的一种雏形，其对于每个扩展出来的节点给出一个预期值，如果这个预期值不如当前已经搜索出来的结果好的话，则将这个节点 ( 包括其子节点 )从解答树中删去，从而达到加快搜索速度的目的。范例：在一个商店中购物，设第I 种商品的价格为Ci。但商店提供一种折扣，即给出一组商品的组合，如果一次性购买了这一组商品，则可以享受较优惠的价格。现在给出一张购买清单和商店所提供的折扣清单，要求利用这些折扣，使所付款最少。问题分析： 显然， 折扣使用的顺序与最终结果无关，所以可以先将所有的折扣按折扣率从大到小排序，然后采用回溯法的控制结构，对每个折扣从其最大可能使用次数

13、向零递减搜索，设A 为以打完折扣后优惠的价格， C 为当前未打折扣的商品零售价之和，则其预期值为A+a*C，其中 a 为下一个折扣的折扣率。如当前已是最后一个折扣，则a=1 。对回溯算法的改进：。添加一个全局变量BestAnswer，记录当前最优解。在每次生成一个节点时，计算其预期值，并与BestAnswer比较。如果不好，则调用回溯过程。三、 A* 算法A* 算法中更一般的引入了一个估价函数f, 其定义为 f=g+h。 其中 g 为到达当前节点的耗费，而 h 表示对从当前节点到达目标节点的耗费的估计。其必须满足两个条件：。 h 必须小于等于实际的从当前节点到达目标节点的最小耗费h* 。 f

14、必须保持单调递增。A* 算法的控制结构与广度搜索的十分类似，只是每次扩展的都是当前待扩展节点中f 值最小的一个，如果扩展出来的节点与已扩展的节点重复，则删去这个节点。如果与待扩展节点重复，如果这个节点的估价函数值较小，则用其代替原待扩展节点，具体算法描述如下：范例：一个3*3的棋盘中有1-8 八个数字和一个空格，现给出一个初始态和一个目标态，要求利用这个空格，用最少的步数，使其到达目标态。问题分析：预期值定义为h=|x-dx|+|y-dy|。估价函数定义为f=g+h。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理

15、- - - - - - - 第 5 页，共 11 页 - - - - - - - - - Node( 节点类型 ) Record Situtation:TSituation（当前节点状态）; g:Integer;(到达当前状态的耗费) h:Integer;(预计的耗费 ) f:Real;(估价函数值 ) Last:Integer;(父节点 ) End List( 节点表 ):Array1.Max(最多节点数 ) of Node(节点类型 ); open( 总节点数 ):Integer; close( 待扩展节点编号):Integer; New-S:Tsituation;(新节点 ) List-

16、0; open-1; close-0; List1.Situation1) and (not UsedI) do dec(I); Until I=1; For I:=n downto 1 do(计算总的乘法次数) If UsedI then count:=count+1; Result:=count;(返回乘法次数 ) 思路二：通过对思路一的输出结果的分析可以发现一个规律：a19=a1*a18 a18=a2*a16 a16=a8*a8 a8=a4*a4 a4=a2*a2 a2=a*a 对于一个 n ，先构造一个最接近的2k ，然后利用在构造过程中产生的2I,对 n-2k进行二进制分解，可以得出

17、解。对次数的计算的描述如下：count:=0; Repeat If n mod 2 = 0 then count:=count+1 Else count:=count+2; n:=n div 2; Until n=1; Result:=count; 反思：观察下列数据：a15 a23 a27 Cost:5 Cost:6 Cost:6 a2=a1*a1 a2=a1*a1 a2=a1*a1 a3=a1*a2 a3=a1*a2 a3=a1*a2 a6=a3*a3 a5=a2*a3 a6=a3*a3 a12=a6*a6 a10=a5*a5 a12=a6*a6 a15=a3*a12 a20=a10*a1

18、0 a24=a12*a12 a23=a3*a20 a27=a3*a24 这些数据都没有采用思路二种的分解方法，而都优于思路二中所给出的解。但是经过实测，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 11 页 - - - - - - - - - 思路一二的所有的解的情况相同，而却得不出以上数据中的解。经过对a2 a15的数据的完全分析，发现对于一个 an ，存在多个分解方法都可以得出最优解，而在思路一中只保留了一组分解方式。例如对于 a6 只保留了 a2*a4，从而使 a

19、3*a3这条路中断，以至采用思路一的算法时无法得出正确的耗费值，从而丢失了最优解。所以在计算an=ax1*ax2的重复时，要引入一个搜索过程。例如:a15=a3*a12，a12=a6*a6， 而 a6=a3*a3。 如果采用了a6=a2*a4， 则必须多用一步。Link=Node; （使用链表结构纪录所有的可能解）Node=Record split:Integer; next :Link; End; Solution:Array1.1000 of Link; （对于 an的所有可能解）Cost :Array1.1000 of Integer; （解的代价）max :Integer; （推算的上

20、界）Procedure GetSolution; Var i,j :Integer; min,c:Integer; count:Integer; temp,tail:Link; plan :Array1.500 of Integer; nUsed:Array1.1000 of Boolean; Procedure GetCost(From,Cost:Integer); （搜索计算最优解）Var temp:Link; a,b :Boolean; i :Integer; Begin If Costc then Exit; （剪枝）If From=1 then （递归终结条件）Begin If Co

21、st Exit; End; temp:=SolutionFrom; While tempNIL do （搜索主体）Begin a:=nUsedtemp.Split; If not a then inc(cost); nUsedtemp.Split:=True; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - - - - - - - b:=nUsedFrom - temp.Split; If not b then inc(cost); nUsedFro

22、m-temp.Split:=True; i:=From-1; While (i1) and (not nUsed) do dec(i); GetCost(i,Cost); If not a then dec(cost); If not b then dec(cost); nUsedFrom-temp.Split:=b; nUsedtemp.Split:=a; temp:=temp.next; End; End; Begin For i:=2 to Max do（动态规划计算所有解）Begin count:=0; min:=32767; For j:=1 to i div 2 do （将 I 分

23、解为 I-J 和 J）Begin c:=32767; FillChar(nUsed,Sizeof(nUsed),0); nUsedj:=True;nUsedi-j:=True; If j=i-j then GetCost(i-j,1) Else GetCost(i-j,2); If c Begin count:=1; min:=c; plancount:=j; End Else if c=min then Begin inc(count); plancount:=j; End; End; new(solution); （构造解答链表）solution.split:=plan1; solutio

24、n.next:=NIL; Cost:=min; tail:=solution; For j:=2 to count do Begin 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 - - - - - - - - - new(temp); temp.split:=planj; temp.next:=NIL; tail.next:=temp; tail:=temp; End; End; End; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -