（一）问题的表述

（2）相对得当的办理方法：由于大多数须要人工智能方法的问题缺少直接的办理方案，因此搜索是办理问题的通用方法。

其余如果真的想节制这一章，该当把这八个数字对应的每一个情形在PPT或者书上都过一遍，而不是纸上谈兵。

1.搜索须要办理的基本问题：

（1）能否找到办理方案。

（2）该解是否为最优解。

（3）韶光和空间繁芜度是多少？

（4）是否终止操作或者陷入去世循环

2.状态空间图（重点）

问题的状态空间是一个有向图，它表示问题的所有可能状态及其转换。

解题过程便是在图中找到一条路径，实在便是一个搜索的过程。

状态空间四元组：（S，O，S0，G）

S：状态集。

O：一组运算符。

S0：包含问题的初始状态是S的非空子集。

G: 描述知足某些属性的几种详细状态或路径信息

例子：

W：猴子的水平位置

Y：框的水平位置

x：当猴子在箱子上面时，取x=1；否则，取x=0

z：当猴子摘喷鼻香蕉时，z=1；否则，z=0

初始状态和目标状态是：

初始状态：（a，b，0，0）

目标状态： (c,c,1,1)

3.通用图搜索算法（看懂就好）

符号解释：由于搜索是探求从起始节点到目标节点的路径，因此在搜索过程中必须随时记录搜索轨迹。

S-初始状态节点

G-搜索图

OPEN表-存储所有还未展开的节点

CLOSE——存储所有已经展开的节点

MOVE-FIRST(OPEN)——取OPEN表中第一个节点作为须要扩展的节点n，并将节点n移动到CLOSE表中

创建指向父节点的指针并将其添加到 OPEN 列表；必须记住从目标返回的路径 - 代表状态的每个节点构造都必须有一个指向父节点的指针。

（实在便是不断天生新的节点，在这个过程中让新节点的指针指向它的父亲）

利用回溯策略搜索：

当一条路走到尽头的时候，如果碰着了无解节点，那么就会回溯到路径上最近的父节点，类似后面的深度优先搜索，直到找到终极的解。

（1）PS（path states）表：存储当前搜索路径的状态。

（2）NPS（新路径状态）表：该表包含等待搜索的状态，其后代状态还未被搜索，即还未被天生或扩展。

（3）NSS（无可解状态）表：一组不可解状态，列出了无法找到办理路径的状态。
如果搜索过程中扩展的状态是个中的一个元素，则可以立即将其打消，并且不会取得进一步进展。

4.盲目搜索（重点）

盲选便是不提示，分为广度优先和深度优先。

八位代码问题（按中间的空格可以高下旁边移动，不然按数字太麻烦）：

广度优先便是把某一级的父节点能够天生的下一级节点全部列出来，当然这也意味着打算量有时候会非常大，不可能全部打算完。

搜索效率较低，但是利用广度优先搜索总能找到目标节点，并且总能找到最短路径。

行列步队的利用

深度优先搜索的意思便是沿着一条路径走到终点，然后返回到上一个父节点，再找另一条到达终点的路径，然后返回到上一个父节点，再次走到终点。

但如果没有深度限定，那么就可以沿着一条路线无限扩展。

因此，您必须添加一个深度限定，然后，如果该限定不足，则再添加一点并连续该过程。

利用了一个堆栈，即乌鸦喝水的瓶子，前辈后出。

5.启示式策略

给打算机一个提示、一个启示式方法。

就像玩井字游戏一样，给它一个提示，先从中间走，它就会先从中间走，省去十年的弯路！

必须要强调的是如何结束，当你碰着重复的路，就相称于结束了。

1. 启示性信息

分类：

a. 陈述性启示式信息

b. 程序启示式信息

c. 掌握启示式信息

2. 估值函数

f(n) = g(n) + h(n)

h(x)：启示式函数，有利于搜索的纵向开展，提高搜索效率，但影响完备性。

g(x)：代价函数，有利于搜索的横向开展，提高搜索的完备性，但影响搜索效率。

评价函数f(n)：从起始节点经由n个节点到目的节点的路径的最小本钱估计，估计所要搜索的节点的“有希望”程度，并按顺序排列（在打开的表中）。

在f(n)中，g(n)所占比例越大，越方向于广度优先搜索方法；h(n)所占比例越大，启示式性能越强。

f(x)是初始节点S0到达节点x所付出的本钱与节点x与目标节点Sg的估计靠近度之和，是g(x)和h(x)之间的折衷。

3. 极小极大剖析

和上面一样，我们须要利用树形图。

对称性按一个案例打算。

便是打算每个节点的得分，类似于学习成绩，分数越高代表大学越好。

怎么算呢？以井字游戏为例，假设我们用的是“X”，便是X在这个状态下的胜率减去O的胜率，得到的值便是评价函数f(n)，但是按照后面会讲到的，这个该当是h(n)。
末了我们找到一条每个节点的值最大的路径，便是解。

至于为什么是最大，是由于我肯定想以大上风取胜，以是就取大值。
想象一下，为了取胜，机器人已经打算过你做出的每一个局势，以及它会采纳的针对性方法。

后向值：

但实际情形是先打算子节点的值，然后取最小值作为父节点的分数。

（或者取最小值，或者取最大值），然后回退到父节点。

但显然效率太低，因此涌现了α-β剪枝技能。

从字面意思上看，便是减去不须要的，也便是在推送节点的同时，打算分数，将分数小的直接丢弃，这样很多不好的结果就会少打算，从而节省机器开销，提高搜索效率。

6.A和A寻路算法（重中之重，超级大问题）

A和A寻路算法都是探求最优解的算法。

【估计函数f(n)=g(n)+h(n)】

n — 搜索图 G 中的节点；

f(n) — G 中从 s 经由 n 到 ng 的估计最小路径本钱；

g(n) —— G中从s到n的实际路径代价；

h(n) —— 估计从 n 到 ng 的最小路径代价；

h(n) 值——根据启示式知识打算；

h(n)称为启示函数，它不是固定的，必须根据详细情形设定，类似于上面最大值和最小值方法中的分数。
选择的参数h(n)越精确，打算出的f(n)就越精确。

1.算法A

类似于打算机中极小极大算法的运用。

算法A的设计与一样平常的图搜索相同，分为两个阶段：

（1）初始化

创建一个仅包含初始状态节点 s 的搜索图 G:={s}

打开:={s}

关闭:={}

（2）搜索循环

MOVE-FIRST(OPEN) —— 删除 OPEN 列表头部的节点 n。

须要把稳的是，对付每个子节点 ni，打算 f(n,ni) = g(n,ni) + h(ni)，这是从 n 到 ni 确当前实际本钱以及从 n 到 ni 的最短路径本钱。

一起上不断修正指针，也便是比较大小，如果父节点比较短，就将指针指向这个父节点。

（3）八位代码

对付我们熟习的八拼图问题，我们可以将 g(n) 设置为深度（即深度优先层），然后将密钥 h(n) 设置为当前不在目标位置的项目的数量。

此时，还未打算完的新节点就放在open表中（可以用深度优先的方法一贯走到末了），已经打算完的节点就放在close表中，close表中保存着当前打算过程的处理顺序，如果终极打算出了终极的结果，那么这便是一个办理方案。

（4）搜索算法的可适应性

如果能算出解，就说这个算法是可以接管的。
例如广度优先搜索算法虽然可以接管，但是搜索效率不高。

然后算法 A 的可接管性 - 定义 f(n) = g(n) + h(n)

n-搜索图G中解路径最短的节点；

f(n) —— 从 s 经由节点 n 到 ng 的最短解路径的路径本钱；

g(n) —— 路径第一段（从s到n）的路径本钱；

h(n) —— 后半部分路径（从n到ng）的路径代价；

这个看起来和原始的一样，但是带有号的它只代表最短路径，也便是原始图。

也便是说，如果g(n)=g(n)，h(n)=h(n)，那么在搜索过程中，每次都会做出精确的选择，并且不会扩展不干系的节点。

h(n)尽可能靠近h(n)——算法A的关键。

下面大略先容一下8位代码（A算法）如何提高可采取性：

很大略，g(n)肯定不会变，那我们把它改成h(n)吧，本来h(n)便是错位的位数，如果改成最小移动间隔和错位的位数之和，是不是会更快呢？

答案是肯定的，毕竟已经有人问过了。

2. A 搜索算法

为了更好地理解A算法，我们首先理解一下深度和广度优先搜索算法。

（1）深度优先搜索，俗话说，便是算法会沿着一个方向提高，直到碰到边界或者障碍物，然后再回溯。

上风：

a. 实现大略

缺陷：

a.该路径可能不是最优解；

b. 寻路韶光较长。

（2）广度优先搜索：这就像地震波，从出发点向外辐射，直到找到目标点。

上风：

a.大略。
代码只有几十行；

b. 该路径能找到最优解；

缺陷：

a. 该算法遍历许多节点

（3）最佳优先搜索

在某些情形下，如果我们可以预先打算每个节点到目的地的间隔，我们可以利用这些信息更快地到达目的地。

但是这个算法也有缺点：

如果出发点和终点之间存在障碍物，最佳优先算法可能无法找到最短路径。

A算法吸取了这些算法（不仅仅是这两种）的优点然后利用到打算机中：

广度优先搜索是一层层地扩展，虽然找到了最优路线，但是它走遍了大部分格子才找到我们的目标点。
也便是说它只关注当前扩展点和起始点的关系，而忽略了当前点和目标点的间隔。
最佳优先搜索只关注从当前节点到目标节点的路径，虽然有可能找到问题的解，但是很可能不是最优解。
以是A算法实在结合了以上几种算法的特点，即既关注已经走过的节点的代价，又关注未来要走的节点的代价。

A算法通过以下函数打算每个节点的优先级。

f(n) = g(n) + h(n)

f(n)——节点 n 的综合优先级。
当我们选择下一个要遍历的节点时，我们总是选择综合优先级最高（值最小）的节点。

g(n) – 间隔出发点 n 的节点本钱。

h(n)——从终点到节点n的估量本钱，是A算法的启示函数。

A算法选择估计值最小的那个（常日是最小的）并连续。

接下来有两个问题须要办理：

1. 如何打算估计函数h(M)？

对付网格状的图，有几种常见的间隔打算公式（把稳每个点周围的***：

①如果图形只许可高下旁边四个方向移动，可以利用曼哈顿间隔。

②若图形许可八个方向移动，可采取对角线间隔。

③如果图许可向任意方向移动，可以利用欧几里得间隔。

2. 不同的估计函数h(M)会对我们的搜索结果产生什么影响？

（1）当估计间隔h=实际间隔h'时，也便是我们每次扩展一个点，我们精确知道如果选择这个点，路径间隔会是多少。
这样我们就不用随机选择了，总是可以选到最小的那个，这个肯定便是最优解，基本就不用扩展其他点了。

（2）如果预估间隔h < 实际间隔h'，我们终极一定会找到一条最短路径，但是它可能会经由很多无效点。
极度情形下，当h==0时，终极的间隔函数变成：

f(M)=g(M)+h(M) => f(M)=g(M)+0 => f(M)=g(M)

此时A蜕变为Dijkstra（广度优先搜索），担保能找到最短路径，只考虑与出发点的间隔关系，毫无灵感，h(n)越小，A扩展的节点越多，运行速率越慢。

（3）如果估计间隔h > 实际间隔h'，可以快速找到一条到达目的地的路径，但不一定是最优解。
另一种极度情形是，如果h(n)远大于g(n)，则只有h(n)有浸染，这时就变成了最佳优先搜索。

A算法是一种什么样的启示式算法？

策略为 f(n)=g(n)+h(n) 的启示式算法成为 A 算法的充分条件是：

1.搜索树上从出发点到终点存在一条最优路径。

2.问题领域有限。

3. 所有节点的子节点的搜索本钱>0。

4. h(n)=