ACM程序设计基础之搜索.ppt

《ACM程序设计基础之搜索.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ACM程序设计之搜索基础搜索是竞赛中的通用解题法1.基本概念2.搜索的基本方式3.搜索的变形搜索动态规划贪心构造图论约10%约15%约5%约5%约10%计算几何纯数学题数据结构其它约5%约20%约5%约25%什么是搜索算法呢？搜索算法是利用计算机的高性能来有目的地穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。1.基本概念状态状态转移搜索树状态空间可行解最优解状态对问题以及事物状态在某一发展阶段的数学描述状态转

2、移问题从一种状态转移到另一种状态的操作搜索树以阶段中每一个状态作为一个点，状态之间的转移作为边，形成一个隐式图。其中我们把初始状态看做根。那么我们的搜索过程实际上就是在对这个树的结点做遍历。这棵树也可以称为状态空间比如：二分查找2345681220324565748695100headmidtail查找示意图：A[1]~A[15]A[1]~A[7]A[9]~A[15]A[1]~A[3]A[5]~A[7]A[1]~A[1]A[3]~A[3]……思考：1、在一百万个元素里查找某个元素大约需要比较多少次？2、时间

3、复杂度：O(logN)可行解最优解2、搜索算法分类枚举算法广度优先搜索（BFS)深度优先搜索(DFS)双向广度优先搜索A*算法回溯算法枚举算法:最直接的搜索方法,列举问题的所有状态.然后从中找出问题的解广度优先搜索:从初始状态开始,通过规则来生成第一层结点,同时检查生成结点中是否有目标结点.若没有则生成下一层接点,并检查是否有目标结点…深度优先搜索:从初始结点开始扩展,按照某中顺序不断的向下扩展,直到找到目标状态或者是无法继续扩展双向广度优先搜索:从两个方向同时开始进行搜索,两个方向的起始点分别为目标状态和初始状

4、态.A*算法:一种典型的启发示搜索F(n)=G(n)+H(n)G(n)从起始点到结点n的最佳路径实际代价H(n)从结点n目标结点的估计代价深度优先搜索用堆栈存储当前结点为下一次扩展结点的父结点0123456搜索到的路径0->1->30->1->40->2->50->2->6voidDFS(intcurNode,intcurDepth){if(curNode==Target)return;if(curEdpth>MaxDepth)return;for(inti=0;i

5、d(curNode,i);DFS(newNode,++curDepth);}return;}函数的返回值可以根据具体的情况来设定广度优先搜索采用队列存储每次扩展出当前结点的所有子结点0123456广度优先搜索voidBFS(intcurNode,intcurDepth){while(front

6、ode==target)return;}}return;}搜索算法举例：八数码难题在3×3的方格棋盘上，分别放置了标有数字1、2、3、4、5、6、7和8的八个棋子5847362158473621S0初始状态Sg目标状态空出一个位置使棋子可以移动，形成不同的局面问题要使棋盘进入某种预定局面应如何移动棋子深度优先搜索算法举例2318476523184765283147652318476528314765283164752831476528316475283164752837146583214765281437

7、652831457612378465123847652836417528316754832147652837146528143765283145761234567891011121312384765目标0层1层2层3层4层规则：空格上下左右下左右广度优先搜索算法举例23184765125673目标840层1层2层3层231847652831476523184765下左右283147652831647528314765下左右12384765下23418765下2831647528316475左右283714

8、6583214765上下2814376528314576上下1237846512384765下右规则：空格上下左右DFS&BFSDFS可以找出两个状态之间的一条路径BFS可以找出两个状态之间的最短路径回溯搜索是DFS的一种改进，更实用的搜索求解方法。与DFS的区别扩展结点时，DFS将所有子结点全部扩展出来，再选取最新的一个结点进行扩展。回溯搜索只扩展所有子结点的其中一个，