3-5deepth searching

《3-5deepth searching》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、3.5深度优先搜索首部EFCD1)深度优先搜索basicidea例1：2)深度优先算法步骤：(1)初始结点S放入OPEN中；(2)若OPEN为空，则搜索失败，问题无解；(3)OPEN表中最顶端结点放到CLOSE表中，并给出顺序编号n；(4)若n为目标结点D，则搜索成功，问题有解；(5)若n无子结点，转(2)；(6)扩展n结点，将其所有子结点配上返回n的指针，并按次入OPEN首部，转(2)。首部EFCD首部EFCD深度优先搜索节点扩展顺序Open①A②BCD③EFCD④KLFCD⑤LFCD⑥FCD⑦MCD⑧CD⑨GD⑽DRednodesissuccee

2、ding.NODEVELOPED首部EFCDtop空栈topA进栈AtopA出栈DCB进栈DBCtopB出栈DC3)深度优先搜索datastructureOPEN?首部EFCDtopKLF出栈DCtopMC出栈DtopFE进栈DEFCtopE出栈LK进栈DCFLKtopG进栈DGtopM进栈DMC叶深度优先搜索CLOSED?首部EFCDtop空栈BEKL进栈topABKELtopA进栈AFＭＣ进栈ABKELtopCＭＦＧ例2：八数码问题(2)操作规定已在广度优先搜索算法举例中介绍过。初始布局S和目标状态D如下图所示：12384765S3S2S1S4S

3、6S5S7S9S8问题目标状态问题初始状态GreenmeansOrderofEnteringopenS0RedmeansOrderofdevelopingOrOrderofEnteringclosed例3深度优先搜索树：Whenwillsearchingend?4)有界深度优先搜索特点：引入搜索深度限制值d，使深度优先搜索过程具有完备性。有界深度优先算法步骤：(1)初始结点S放入OPEN中；(2)若OPEN为空，则搜索失败，问题无解；(3)出OPEN中顶结点n，放入CLOSE表中，并给出顺序编号n；(4)若n为目标结点D，则搜索成功，问题有解；(5)

4、若n的深度d(n)=d，则转(2)；(6)若n无子结点，即不可扩展，转(2)；(7)扩展结点n，将其所有子结点配上返回n的指针，入OPEN，转(2)。checkdAftercheckingWhetherGoalAndidentifiednot.首部EFCDtopEF出栈DCtopC出栈DtopB出栈FE进栈DEFCtopG进栈DG有界深度优先搜索OPEN搜索深度d==3EF到达搜索深度例4有界深度优先搜索树：例5：八数码问题设定搜索深度限制d=5。OPENx182例6重排九宫问题d=58181624281013312226Laste.g.OPENfi

5、rstCLOSED1218xx“Goodluck”搜索顺序:1-18-28-33-34-36OPENxxxx28解路径为:So：l→11→12→13→14：SgSg2834765S01283147652238476511283476528364758321476528371465238476523847652843765283457628364752836475371383214765283714651238476523487652843765283457628364175283675448832147658132476556283746152837

6、146591012384765123784651412例7：initiald=4changinginDepth12384765SgDepthfirstAlgorithm:1.signdepthofanodeasd(n)whenitisjustgenerated.2.Checkdepthafteranodeisidentifiednotthegoal,thenisidentifiedwhetheritcouldbedeveloped.Notify:1.initialdepthis’tenough.So,nosolution.Improvementof

7、DepthfirstAlgorithm:1.setinitialsearchingdepth2.nosolution,add⊿dindepth,researching.3.beforeresearching,putnodesinclosedbacktotheclosed.Notify:1.solutionisthefirstone,butisn’tthebestone.ImprovementofDepthfirstAlgorithm:1.setListR(Sg)forstoringsolutions.2.signthedepthforeachs

8、olution.3.putthesolutionatthefirstpartinthelistR4.res