人工智能--状态空间的盲目搜索

小灰灰 2022-01-21 10:53 266阅读 0赞

### 文章目录 ###

*  状态空间的盲目搜索
 *   *  广度优先算法
     *   *  算法描述：
         *  总结
     *  深度优先算法
     *   *  总结

# 状态空间的盲目搜索 #

根据状态空间所采用的数据结构的不同，可分为**图搜索算法和树搜索算法**。由于图搜索算法且一般问题都可用树搜索算法解决，于是主要讨论树搜索算法，包括一般和代价树。

一般树的盲目搜索主要包括深度优先和广度优先两种搜索算法。

## 广度优先算法 ##

也称为宽度优先算法，**是一种先生成的节点先扩展的策略**。

**算法精髓：从初始节点`$S_0$`开始逐层向下扩展，在第`n`层还没有完全搜索完之前不会进入第`n+1`层的搜索。`Open`表中的节点总是按进入的先后排序，先进入的节点排在前面。**

### 算法描述： ###

1.  把初始节点`$S_0$`放入`Open`表中
2.  如果`Open`表为空，则问题无解，失败退出
3.  把`Open`表的第一个节点取出，放入`Closed`表，并记该节点为`n`
4.  考察节点`n`是否为目标节点，若是，则得到问题的解，成功退出
5.  若节点`n`不可扩展，则转第二步
6.  扩展节点`n`，将其子节点放入`Open`表的**尾部**，并未每一个子节点设置指向父节点的指针，然后转到第二步。

![image][]

### 总结 ###

广度优先搜索是一种完备策略，即只要问题有解，算法就一定可以找到解。并且，广度优先算法找到的解还一定是路径最短的解。

缺点是盲目性较大，特别是当目标节点与初始节点距离较远时，将产生许多无用的节点，效率较低。

## 深度优先算法 ##

算法步骤基本与广度优先算法相同，只是`Open`表中的排序不同，在深度优先算法中，后进入Open表的节点总是排在最前面。即后生成的节点先扩展。

### 总结 ###

深度优先算法是一种非完备策略，即某些本身有解的问题，该算法可能找不到最优解，甚至找不到解。**常见做法是增加一个深度限制，当达到一定深度时，停止深度搜索，转向宽度搜索。这种算法也叫有界深度优先算法。**

[image]: http://note.youdao.com/yws/res/13848/1AC056FEF9D248668664A84641781F08

发表评论取消回复

表情：

评论列表（有 0 条评论，266人围观）

还没有评论，来说两句吧...

相关阅读

相关基于C++实现的状态空间的启发式搜索

实验题目：实现状态空间的启发式搜索 1. 实验目的理解启发式搜索的概念掌握状态空间搜索技术 2. 实验内容

深碍√TFBOYSˉ_/ 2024年04月05日 06:30/ 0 赞/ 65 阅读

相关网络空间搜索FOFA

源起在逛某类乌云的漏洞众测平台的时候看到一位老哥提交的所有漏洞均是CVE-2019-11510VPN任意文件下载的高危洞，总数量大概在五六十个。作为刚开始混迹于众测平台

我就是我/ 2023年08月17日 17:11/ 0 赞/ 127 阅读

相关人工智能搜索技术_未来世界畅想丨人工智能和机器人

对许多人来说，第一次接收人工智能和机器人的概念可能是在电影中——一个智能机器人与人类互动，例如《星球大战》《wall-E》《AI》等，这些例子将人工智能和机器人融合在一起，

野性酷女/ 2022年10月24日 02:14/ 0 赞/ 188 阅读

相关人工智能：搜索策略

一、无信息的搜索策略 1.宽度优先搜索 2.一致代价搜索当每一步的行动代价都相等时宽度优先搜索是最优的,因为它总是先扩展深度最浅的未扩展结点。一致代价搜

梦里梦外;/ 2022年08月28日 13:56/ 0 赞/ 420 阅读

相关 PHP搜索记住状态

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR

ゝ一世哀愁。/ 2022年07月12日 04:20/ 0 赞/ 147 阅读

相关【Solr空间搜索SpatialSearch】

喂，这几个单词什么意思，你晓得伐 <table> <thead> <tr> <th>名词</th> <th>含义</th> </tr>

喜欢ヅ旅行/ 2022年03月08日 03:26/ 0 赞/ 307 阅读

相关人工智能--代价树的盲目搜索

文章目录代价树及其代价运算概念代价树的广度优先搜索算法描述总结代价树的深度优先搜索在一般树的

左手的ㄟ右手/ 2022年01月21日 11:13/ 0 赞/ 447 阅读

相关人工智能--状态空间的盲目搜索

文章目录状态空间的盲目搜索广度优先算法算法描述：总结深度优先算法

小灰灰/ 2022年01月21日 10:53/ 0 赞/ 267 阅读

相关人工智能--状态空间问题求解方法

文章目录状态空间问题表示状态操作状态空间状态空间问题的求解例子二阶梵塔问题

ゝ一世哀愁。/ 2022年01月21日 03:45/ 0 赞/ 938 阅读

相关人工智能--搜索概述

文章目录搜索的含义搜索的分类搜索的含义人工智能所研究的对象大多是属于结构不良或非结构化的问题。对于这些问题，一般很难获得其全部信息，更没有现成

清疚/ 2022年01月21日 03:35/ 0 赞/ 244 阅读