族谱网 头条 人物百科

搜索

2020-10-16
出处:族谱网
作者:阿族小谱
浏览:539
转发:0
评论:0
搜索方式按是否使用启发式信息分启发式搜索盲目搜索按问题的表示方式分状态空间搜索与/或树搜索搜索策略宽度优先搜索宽度优先搜索算法是沿着树的宽度遍历树的节点,如果发现目标,则算法中止。属于盲目搜索。深度优先搜索深度优先搜索沿着树的最大深度方向生成节点并与目标节点进行比较,只有当上次访问的节点不是目标节点,而且没有其他节点可以生成的时候,才转到上次访问节点的父节点,然后搜索该节点的其他子节点。因此深度优先搜索也称为回溯搜索。它既不是完备的,也不是最优的。有时候,某些特定的问题会产生大量重复的节点。例如“八数码”问题就是这样的,当每次运用向上、向下、向左、向右移动空格的算符时,可能产生与已经产生的节点重复的节点。当再次搜索到这个重复节点时,由于应用的算符基本一致,还会产生重复,所以为了节约时间和存储空间,往往在深度优先算法中设立一个机制,用来删除这些重复的节点,以提高效率。迭代加深搜索(ID搜索)...

搜索方式

按是否使用启发式信息分

启发式搜索

盲目搜索

按问题的表示方式分

状态空间搜索

与/或树搜索

搜索策略

宽度优先搜索

宽度优先搜索算法是沿着树的宽度遍历树的节点,如果发现目标,则算法中止。属于盲目搜索。

深度优先搜索

深度优先搜索沿着树的最大深度方向生成节点并与目标节点进行比较,只有当上次访问的节点不是目标节点,而且没有其他节点可以生成的时候,才转到上次访问节点的父节点,然后搜索该节点的其他子节点。因此深度优先搜索也称为回溯搜索。它既不是完备的,也不是最优的。有时候,某些特定的问题会产生大量重复的节点。例如“八数码”问题就是这样的,当每次运用向上、向下、向左、向右移动空格的算符时,可能产生与已经产生的节点重复的节点。当再次搜索到这个重复节点时,由于应用的算符基本一致,还会产生重复,所以为了节约时间和存储空间,往往在深度优先算法中设立一个机制,用来删除这些重复的节点,以提高效率。

迭代加深搜索(ID搜索)

对深度优先搜索进行了一定改进,对搜索树的深度进行控制,即有界深度优先搜索。

在程序找到目标之前,通过迭代不断增大d以保证完备性和最优性。虽然会有不少重复搜索,但是鉴于每增加一次d,则搜索的时间复杂度会以指数级别增加,所以重复搜索的时间可以忽略,亦可以与A*算法结合(即IDA*搜索算法)来剪枝。

迭代加深搜索通常用于那种搜索树又深又宽、但是解并不是很深的情况,这时广度优先搜索会超空间,而深度优先搜索会超时。这时迭代加深搜索很有用,可是说是在用递归方法在实现广度优先搜索。

启发式OR图搜索算法

爬山算法

模拟退火算法

最好优先

通用图

A*

AND-OR图启发式搜索

一个特殊问题:博弈论

约束满足搜索

搜索策略还可以指在使用搜索引擎中所使用的策略,它通常是搜索之母,一个好的搜索过程必定有一个好的搜索策略来支持。

评价准则

完备性

时间复杂性

空间复杂性

最优性


免责声明:以上内容版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。感谢每一位辛勤著写的作者,感谢每一位的分享。

——— 没有了 ———
编辑:阿族小谱
发表评论
写好了,提交
{{item.label}}
{{commentTotal}}条评论
{{item.userName}}
发布时间:{{item.time}}
{{item.content}}
回复
举报
点击加载更多
打赏作者
“感谢您的打赏,我会更努力的创作”
— 请选择您要打赏的金额 —
{{item.label}}
{{item.label}}
打赏成功!
“感谢您的打赏,我会更努力的创作”
返回

更多文章

更多精彩文章
打赏
私信

推荐阅读

· 广度优先搜索
作法BFS是一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位址,彻底地搜索整张图,直到找到结果为止。BFS并不使用经验法则算法。从算法的观点,所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实现里,其邻居节点尚未被检验过的节点会被放置在一个被称为open的容器中(例如伫列或是链表),而被检验过的节点则被放置在被称为closed的容器中。(open-closed表)实现方法首先将根节点放入队列中。从队列中取出第一个节点,并检验它是否为目标。若队列为空,表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。重复步骤2。C的实现/***ADDQ(Q,p)-pPUSH入Q*DELQ(Q)-POPQ並返回Q頂*FIRSTADJ(G,v)-v的第一個鄰接點,找不到則返回-1*NEXTADJ(G,v)-v的下...
· 搜索及拯救
种类搜索及拯救包括了多项小项,包括:地面搜索及拯救(英文:GroundSearchandRescue,缩写:GSAR),通常是于地面或者内陆水道(例如引水道)进行。传统上,此项工作通常于郊区以至荒野区域进行。城市搜索及拯救(英文:UrbanSearchandRescue,缩写:USAR),是于城市或者市区进行,通常有涉及自然灾害(例如山泥倾泻、地震、台风、洪水、受到海啸侵袭的沿海城市等)、交通意外、坍塌事故及矿道等。山岭搜索及拯救(英文:MountainSearchandRescue,缩写:MSAR),是于山上进行。海空拯救(英文:AirSeaResue),是于空中或者海上进行,需要协调飞行器及船只合作进行。战斗搜索及拯救(英文:CombatSearchandRescue,缩写:CSAR),是于战场或战区上进行。等等。历史世界上最早的搜索及拯救纪录可以追溯至1656年,一艘荷兰商业船只(V...
· 深度优先搜索
C++的实现定义一个结构体来表达一个NODE的结构:structNode{intself;//数据Node*left;//左节点Node*right;//右节点};那么我们在搜索一个树的时候,从一个节点开始,能首先获取的是它的两个子节点。例如:“ABCDEFG”A是第一个访问的,然后顺序是B和D、然后是E。然后再是C、F、G。那么我们怎么来保证这个顺序呢?这里就应该用堆栈的结构,因为堆栈是一个先进后出的顺序。通过使用C++的STL,下面的程序能帮助理解:constintTREE_SIZE=9;std::stackunvisited;Nodenodes[TREE_SIZE];Node*current;//初始化树for(inti=0;i<TREE_SIZE;i++){nodes[i].self=i;intchild=i*2+1;if(childright);//把右边压入因为右边的访问次序是...
· 二叉搜索树
二叉搜索树的查找算法在二叉搜索树b中查找x的过程为:若b是空树,则搜索失败,否则:若x等于b的根节点的数据域之值,则查找成功;否则:若x小于b的根节点的数据域之值,则搜索左子树;否则:查找右子树。/*以下代码为C++写成,下同*/StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){//在根指针T所指二元查找樹中递归地查找其關键字等於key的數據元素,若查找成功,//則指针p指向該數據元素節點,并返回TRUE,否則指针指向查找路徑上訪問的最後//一個節點并返回FALSE,指针f指向T的雙親,其初始调用值為NULLif(!T){//查找不成功p=f;returnfalse;}elseif(key==T->data.key){//查找成功p=T;returntrue;}elseif(keydata.key)//在左子樹中繼續查找returnS...
· 蒙特卡洛树搜索
历史基于随机抽样的蒙特卡洛方法可以追溯到20世纪40年代。布鲁斯·艾布拉姆森(BruceAbramson)在他1987年的博士论文中探索了这一想法,称它“展示出了准确、精密、易估、有效可计算以及域独立的特性“。他深入试验了井字棋,然后试验了黑白棋和国际象棋的机器生成的评估函数。1992年,B·布鲁格曼(B.Brügmann)首次将其应用于对弈程序,但他的想法未获得重视。2006年堪称围棋领域蒙特卡洛革命的一年,雷米·库洛姆(RemiCoulom)描述了蒙特卡洛方法在游戏树搜索的应用并命名为蒙特卡洛树搜索。列文特·科奇什(LeventeKocsis)和乔鲍·塞派什瓦里(CsabaSzepesvári)开发了UCT算法,西尔万·热利(SylvainGelly)等人在他们的程序MoGo中实现了UCT。2008年,MoGo在九路围棋中达到段位水平,Fuego程序开始在九路围棋中战胜实力强劲的业余棋...

关于我们

关注族谱网 微信公众号,每日及时查看相关推荐,订阅互动等。

APP下载

下载族谱APP 微信公众号,每日及时查看
扫一扫添加客服微信