人工智能导论学习笔记04——基本搜索(无信息)

肝！

搜索问题求解

1. 搜索问题求解

问题求解

AI中每个研究领域都有其各自的特点和规律,但就求解问题的过程看,都可抽象为一个问题求解过程。
某些问题的求解过程实际上是一个搜索。
AI为什么要研究搜索：
问题没有直接的解法+需要探索地求解
根据问题的实际情况不断寻找可利用的知识,构造出一条代价较少的推理路线,使问题得到圆满解决的过程称为搜索。
搜索问题求解包括两个重要的方面:表示和搜索
表示是基本,搜索必须要在表示的基础上进行。表示关系到搜索的效率。
知识表示：状态空间、问题归约、谓词逻辑、产生式
本章主要讨论基于搜索的问题求解（状态空间）

状态空间图

状态空间图是搜索问题的一种数学描述
结点：问题的某个状态
边：表示操作符（动作）
目标：一组结点，通常只有一个
在状态空间图中，每个状态仅出现一次
状态空间图一般较大，很少生成全图，但它是一种搜索问题的有效表示方法
在这里插入图片描述

状态空间图搜索

在这里插入图片描述

无信息搜索

状态空间图搜索

图搜索策略主要分为无信息搜索(Uninformed Search)和启发式搜索(Heuristic Search)。
无信息搜索：也称为盲目搜索，即只按预定的控制策略进行搜索,在搜索过程中获得的中间信息不会用来改进控制策略。
启发式搜索: 在搜索中加入了与问题有关的启发性信息,用于指导搜索朝着最有希望的方向进行,加速问题的求解过程并找到最优解。

无信息搜索

无信息搜索一般是按预定的搜索策略进行搜索。由于这种搜索总是按预定的路线进行，没有考虑到问题本身的特性，所以这种搜索具有很大的盲目性，效率不高，适应于简单问题求解。
在这里插入图片描述

宽度优先搜索(Breadth-Frist Search)

定义：以接近起始节点的程度依次扩展节点的搜索方法宽度优先搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。
在这里插入图片描述

深度优先搜索(Depth-Frist Search)

定义：优先扩展最新产生的(即最深的)节点的搜索方法
深度优先搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。
状态空间搜索树的深度可能为无限深，往往给出一个节点扩展的最大深度—深度界限

在这里插入图片描述
有界深度优先搜索算法如下：
(1) 把起始节点S放到未扩展节点OPEN表中。如果此节点为一目标节
点，则得到一个解。
(2) 如果OPEN为一空表，则失败退出。
(3) 把第一个节点(节点n)从OPEN表移到CLOSED表。
(4) 如果节点n的深度等于最大深度，则转向(2)。
(5) 扩展节点n，产生其全部后裔，并把它们放入OPEN表的前端，提
供返回节点n的指针，如果没有后裔，则转向(2)。
(6) 如果后继节点中有任一个为目标节点，则求得一个解，成功退出；
否则，转向(2)。