《搜索算法结构》课件.pptx

该【《搜索算法结构》课件 】是由【1772186****】上传分享，文档一共【29】页，该文档可以免费在线阅读，需要了解更多关于【《搜索算法结构》课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。搜索算法结构BIGDATAEMPOWERSTOCREATEANEWERA目录CONTENTS搜索算法概述深度优先搜索广度优先搜索A搜索算法启发式搜索算法混合搜索算法BIGDATAEMPOWERSTOCREATEANEWERA01搜索算法概述搜索算法的定义搜索算法是一种解决问题的策略,通过搜索算法可以在给定的解空间中寻找满足特定条件的解。解空间是指问题所有可能解的集合,而满足特定条件的解被称为目标解或最优解。按照搜索方式分类可以分为盲目搜索和启发式搜索。盲目搜索按照某种固定的顺序或规则逐个搜索解空间,而启发式搜索利用问题的特性或经验知识,采用启发式策略指导搜索方向,提高搜索效率。按照搜索范围分类可以分为局部搜索和全局搜索。局部搜索只搜索解空间的某个子集,而全局搜索则覆盖整个解空间。搜索算法的分类在计算机科学中,搜索算法广泛应用于各种问题求解,如图遍历、最短路径、排序和查找等。计算机科学人工智能数据挖掘自然语言处理人工智能领域中,搜索算法常用于路径规划、决策制定、游戏AI等领域。在数据挖掘中,搜索算法用于查找满足特定条件的数据项或模式。在自然语言处理中,搜索算法用于查找符合特定条件的语义或句法结构。搜索算法的应用场景BIGDATAEMPOWERSTOCREATEANEWERA02深度优先搜索深度优先搜索(DFS)是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这个过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。深度优先搜索的定义设置起始节点为当前节点,将起始节点标记为已访问。初始化沿着当前节点的未探索的边进行递归调用深度优先搜索,直到当前节点的所有边都己被探寻过。递归调用如果当前节点不是目标节点,则回溯到发现当前节点的一条边的起始节点。回溯重复执行递归调用和回溯,直到所有可达节点都被访问为止。重复执行深度优先搜索的算法流程优点深度优先搜索可以用于发现图的连通分量、寻找图的桥等,算法相对简单,容易理解和实现。缺点深度优先搜索需要使用递归或栈来实现,对于大规模的图或树,可能会导致栈溢出或效率低下。同时,深度优先搜索无法利用图中的信息进行优化,可能会浪费大量的时间和空间资源。深度优先搜索的优缺点