问题求解与搜索策略

1. 状态空间的搜索策略

2. 与或树的搜索策略

3. 搜索的完备性和策略

---

人工智能的核心问题是【问题求解】，问题求解关键在于【问题表示】【解的搜索】

状态空间表示法：算符和状态（S，F，G）

求解过程转化为从初始节点到目标节点的路径问题：

• 必须要记录走过的点。CLOSED
• 必须要记录还可以走的点。OPEN
• 每一个子结点结构中必须要有指向父节点的指针

表中包含的项包括：状态节点和指针

$状态空间搜索策略\{\begin{array}{l}盲目搜索：广度优先搜索、深度优先搜索\\ 启发式搜索：局部择优搜索、全局择优搜索、A\ast 算法\end{array}$

• OPEN表：存放没走过的点；不同的搜索策略，结点的排列顺序是不一样的。
• CLOSED表：存放已经走过的点（已经扩展过的点）
• CLOSE表：存放将要扩展的点。（用可适用的算符对节点操作，生成一组子结点）

【搜索失败】：一直找不到目标节点；OPEN表中不再有可扩展的节点（叶子节点）。

【一般的搜索策略】：

1. 把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G;
2. 检查OPEN表是否为空，若为空则问题无解，退出;
3. 把OPEN表的第1个节点取出放入CLOSE表，并计该节点为n;
4. 考察节点n是否为目标节点。若是，则求得了问题的解，退出;否则执行5
5. 考察节点n是否可以被扩展，扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点，记做集合M，并把这些子节点作为节点n的子节点加入G中;
6. 对于那些未曾在G中出现过的M成员设置–个指向父节点(即节点n)的指针，并把它们放入OPEN表(不在OPEN表 );
7. 按某种搜索策略对OPEN表中的节点进行排序;
8. 转第2步。

【说明】：

• 对于一个新生成的节点A父节点指针的问题，A有可能第一次生成的新节点，也有可能是之前执行过的节点生成过的，再由当前节点重新生成，那么A的父节点一般由原始节点到该节点的代价来决定，处于代价小的路途上的那个节点就作为该节点的父节点。
• 在搜索过程中，一旦某个被考察的节点是目标节点就得到了一个解。该解是由从初始节点到该目标节点路径上的算符构成。
• 如果在搜索中一直找不到目标节点，而且OPEN表中不再有可供扩展的节点，则搜索失败。
• 通过搜索得到的图称为搜索图，搜索图是状态空间图的一个子集。由搜索图中的所有节点及反向指针所构成的集合是一棵树，称为搜索树。根据搜索树可给出问题的解。

盲目搜索–不借用问题本身的经验信息，只用固定的搜索策略进行搜索

广度优先搜索

【基本思想】

• 从初始节点S0开始，逐层地对节点进行扩展并考察它是否为目标节点。在第n层的节点没有全部扩展并考察之前，不对第n＋1层的节点进行扩展。
  OPEN表中节点总是按进入的先后顺序排列，先进入的节点排在前面，后进入的排在后面。
• 扩展结点n（S0），将n的所有子节点放入OPEN表的尾部，为每一个子节点都配置指向父节点的指针。OPEN表相当与一个队列，按照深度优先遍历的顺序排列。
• 如果生成一个新的节点在OPEN表中已经出现过，就立即放弃这个点。

【优点】只要问题有解，用BFS总可以得到解，并且是路径最短的解
【缺点】盲目性很大，产生的无用节点很多，搜索效率很低

深度优先搜索

【基本思想】深度优先搜索与广度优先搜索的唯一区别是：广度优先搜索是将节点n的子节点放入到OPEN表的尾部，而深度优先搜索是把节点n的子节点放入到OPEN表的首部。

【问题】搜索一旦进入某一个分支，就会一直顺着这条分支找下去，万一该分支是无穷分支，那么就始终找不到解了。所以即使有解，也可能找不到解。

有界深度优先搜索

【基本思想】在深度优先搜索的基础上，引入深度的界限（$d_m$），当搜索到达这一界限时还未找到目标节点，就换一个分支进行搜索。初始节点深度$d(s_0)=0$，每一个被拓展的子结点，其深度在父节点的基础上＋1。

【特点】如果问题存在解，且解的深度小于$d_m$，那么一定可以找到解；如果深度大于$d_m$，则不一定能找到了。

【缺点】$d_m$的值不好给，搜索出来的解不一定是最好的
【改进】先设定一个较小的数作为$d_m$，当搜索到指定的深度仍未找到目标节点，并且CLOSE表仍然有可扩展结点时；将所有结点送回OPEN表中，并且增大$d_m$，继续搜索。只要问题有解，不断增大$d_m$一定找得到解，不一定最优。
【最优解】找到目标节点，就将目标节点存起来，记录其对应的路径长度，然后继续搜索。

代价树的深度优先搜索

每一次都将代价最小的放在OPEN表的前面，按照从小到大的顺序在OPEN表中存放。

代价树的深度搜索是不完备的。

代价树的广度优先搜索

【代价树】：边上有权值的树。
【代价计算】初始节点S0到节点x的代价g(x)，父节点x到子结点y的代价C(x,y)，则g(y)=g(x)+C(x,y)

【基本思想】open表中的代价在任意时刻都是从小到大排列的，代价最小的点传到close中。
【特点】若有解，一定是最优解。

启发式搜索

用估价函数表示该点位于解所在的路径“希望”，函数值越小“希望”越大。每一次找估价函数值最小的节点作为下一步考察的节点。引入估价函数f(n)=g(n)+h(n)，函数值越小希望越大。

A算法

在图搜索算法中，如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对OPEN表中的节点进行排序，则该搜索算法为A算法。由于估价函数中带有问题自身的启发性信息，因此，A算法又称为启发式搜索算法。
对启发式搜索算法，又可根据搜索过程中选择扩展节点的范围，将其分为全局择优搜索算法和局部择优搜索算法。

【估价函数】$f(x)=g(x)+h(x)$,其中g(x)表示起始状态到当前状态的代价；h(x)表示当前状态到目标状态的代价（启发函数）。g(x)有利于完备性，却会影响效率；h(x)有利于提高搜索效率，会影响完备性

【全局择优搜索】：要选择下一个考察节点时，选择OPEN表中所有节点代价最小的点

【局部择优搜索】：要选择下一个考察结点时，选择当前被扩展节点的所有子节点中代价最小的点

A*算法

【定义】代价函数满足一定限制条件的算法。

$f(x)=g(x)+h(x)$，其中，g(x)>0，h(x)≤节点x到目标的实际代价。

【八数码问题】：

g(x)可以定义为从源点S0到x的步数；h(x)表示为从x到目标点G走错的步数

【估价函数h(x)对算法的影响】：将上面的估价函数更换为所有错误节点距离目标节点的曼哈顿距离（两点水平和垂直距离之和）

【完备性】

• 对于一类可解的问题和一个搜索过程，如果运用该搜索过程一定能求得该类问题的解，则称该搜索过程为完备的，否则为不完备的。
• 完备的搜索过程称为“搜索算法”。不完备的搜索过程不是算法，称为“过程”。
• 广度优先搜索、代价树的广度优先搜索、改进后的有界深度优先搜索以及A*算法都是完备的搜索过程，其它搜索过程都是不完备的。

---

与或树的搜索策略

【定义】：求解代价最小的解树的搜素方法。

【可解节点】：终叶节点是可解节点；非终叶节点的子结点若是“或”的关系，只要存在一个可解，则非终叶节点是可解节点；若其子节点是“与”的关系，要所有结点都是可解节点才行。

终叶节点是端节点，端节点不一定是终叶节点。

如果已经确定某节点是可解节点，则其不可解子结点可删去。

如果某节点是不可解节点，则其所有的子结点都可以删去，该节点不能删。

如上图，节点下有弧线的表示"与"的关系，如节点2，其子结点4和t1，只有当子结点都是可解节点时，节点2才是可解节点；没有弧线的分支就是“或”的关系，当节点A和t2存在一个是可解节点时，节点4就是可解节点。
例题：
【定义】：求解代价最小的解树的搜素方法。

【可解节点】：终叶节点是可解节点；非终叶节点的子结点若是“或”的关系，只要存在一个可解，则非终叶节点是可解节点；若其子节点是“与”的关系，要所有结点都是可解节点才行。

终叶节点是端节点，端节点不一定是终叶节点。

如果已经确定某节点是可解节点，则其不可解子结点可删去。

如果某节点是不可解节点，则其所有的子结点都可以删去，该节点不能删。

与/或树的有序搜索是求代价最小的解树的搜索方法。

• 为求得代价最小的解树，每次确定待扩展节点时，需要往前多看几步，计算扩展这个节点可能要付出的代价，并选择代价最小的节点进行扩展。

• 根据代价决定搜索路线的方法称为与/或树的有序搜索，它是一种启发式搜索策略。

###【解树的代价计算方法】

通过计算解树中节点的代价得到。若问题可解，由子节点代价推算父节点代价，逐层上推，最终求出S的代价，即解树的代价。

设c(x, y)表示节点x到其子节点y的代价，则x的代价计算方法如下：

• 如果x是终叶节点，则定义x的代价： h(x)=0
• 如果x不可扩展，且不是终叶节点，则定义：h(x)=∞
• 如果x是“或”节点，y1， y2， …， yn是它的子节点，则x的代价为：h(x)=min{c(xi,yi)+h(yi)}h(x)=min\{c(x_i,y_i)+h(y_i)\}h(x)=min{c(xi​,yi​)+h(yi​)}
• 如果x是“与”节点．则x的代价有两种计算方法：
  ※和代价法h(x)=∑i=1n{c(xi,yi)+h(yi)}h(x)=\sum_{i=1}^n\{c(x_i,y_i)+h(y_i)\}h(x)=∑i=1n​{c(xi​,yi​)+h(yi​)} ※最大代价法h(x)=max{c(xi,yi)+h(yi)}h(x)=max\{c(x_i,y_i)+h(y_i)\}h(x)=max{c(xi​,yi​)+h(yi​)}

【例题】

【计算h(x)的条件】已知x所有子节点的代价。
【问题】搜索是自上而下进行的，只有不可扩展节点的代价是已知的（或0），因此除非x的所有子节点都不可扩展，否则x的代价无法计算得到。
【解决方案】根据问题本身提供的启发性信息定义一个启发函数，由启发函数估算子节点的代价，然后反推计算父节点和先辈节点的代价。每当有新一代的节点生成时，都要自下而上地重新计算先辈节点的代价。

###【希望树】

选择待扩展节点时，挑选有希望成为最优解树一部分的节点进行扩展，保证任一时刻求出的部分解树的代价都是最小的。由这些节点及先辈节点（包括初始节点S）构成的与/或树有可能成为最优解树一部分，被称为希望树。
【注意】搜索过程中，随着新节点的不断生成，节点的代价值不断变化。因此，希望树也是在不断变化的。
有序搜索是一个不断选择、不断修正希望树的过程。

【例题】

代价小的子树就作为这一点的希望树。

【博弈树】

【极大极小分析法】根据问题特性定义一个估价函数。考虑每一方案实施后，对方可能采取的所有行动，利用估价函数估算当前博弈树端节点得分（静态估值）。
利用端节点的估值推算其父节点得分（倒推值）。

• 对“或”节点，为了选一个对自己最有利的方案，选其子节点中的最大得分作为父节点得分；

• 对“与”节点，立足于最坏情况，选其子节点中的最小得分作为父节点得分。
  具有较大倒推值的行动方案就是当前最好的行动方案。