人工智能——搜索求解策略

第五章 搜索求解策略

5.1 搜索的概念

口人类的实际搜索行为
口人工智能所要解决的问题大部分不具备明确的解题步骤，而只能是利用已有的知识一步一步地摸索前进。
什么是搜索?
根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称之为搜索

搜索中需要解决的基本问题

(1)是否一定能找到一个解
(2)找到的解是否是最佳解
3)时间与空间复杂性如何
4)是否终止运行或是否会陷入一个死循环

1.搜索方向:
(1)数据驱动: 从初始状态出发的正向搜索

正向搜索-从问题给出的条件出发

(2)目的驱动:从目的状态出发的逆向搜索
逆向搜索: 从想达到的目的入手，看哪些操作算子能产生该目的以及应用这些操作算子产生目的时需要哪些条件
(3)双向搜索
双向搜索: 从开始状态出发作正向搜索，同时又从目的状态出发作逆向搜索，直到两条路径在中间的某处汇合为止

2.盲目搜索与启发式搜索:
(1)盲目搜索:在不具有对特定问题的任何有关信息的条件下，按固定的步骤(依次或随机调用操作算子) 进行的搜索
(2)启发式搜索:考虑特定问题领域可应用的知识动态地确定调用操作算子的步骤，优先选择较适合的操作算子，尽量减少不必要的搜索，以求尽快地到达结束状态

搜索方法的经典应用：
8数码问题
传教士和野人问题
旅行商问题
4皇后问题
迷宫问题
博弈问题

5.2 状态空间知识表示方法

问题的形式化描述：

状态描述： 用数学方法定义系统状态
初始状态、目标状态
行动规则：产生后继节点
目标测试：判断当前节点是否就是目标节点

路径成本：为每一条搜索路径定义数值化的消耗值。

搜索方法的一般步骤
1、定义状态描述形式
2、定义算符一是把问题从一种状态变换到另一种状态的方法代号，即状态演变规则
3、确定初始状态(初始节点)和目标状态(目标节点)
4、状态更新一根据算符更新当前状态(扫描操作算子集，将适用当前状态的一些操作算子作用于当前状态而得到新的状态，并建立指向其父结点的指针)
5、目标测试一判断更新后的状态是否为目标状态，若不是则转到4再进行搜索，否则转到6
6、搜索成功记录搜索路径(沿着有关指针从结束状态反向到达开始状态，给出一解答路径)
用open表和closed表保存搜索经过的各个节点

5.3 盲目的图搜索策略

口又称穷举式搜索，只能按照预先规定的搜索控制策略进行搜索，没有任何中间信息来改变这些控制策
口具有盲目性，效率不高，不便于复杂问题的求解

口常用方法有广度优先搜索和深度优先搜索以及这两种搜索方法的改良方法。

5.3.1 宽度优先搜索策略

最简便的图搜索算法之一，属于一种盲目搜寻法。

口目的是系统地展开并检查图中的所有节点，以找寻结果。
口基本思想是首先搜索与初始节点距离为1的所有顶点，然后再去搜索与初始节点距离为2的其他顶点依次类推
口它并不考虑结果的可能位置，彻底地搜索整张图直到找到结果为止。

口优点
完备性:如果问题有解宽度优先搜索总能够在有限步内找到目标节点
最优性:在不考虑路径成本的前提下，宽度优先搜索总能够找到最浅的目标节点
口缺点
遍历各个节点，搜索效率差，消耗大量内存和时间

5.3.2 宽度优先搜索的拓展–代价树宽度搜索

口代价树宽度搜索(代价致搜索)对于任意单步路径成本都是最优的搜索策略
其基本思想是优先扩展路径成本最小的节点
口对于任意节点n，用f(n）来表示n到初始节点的路径成本，即代价

5.3.3 深度优先搜索策略

• 深度优先搜索总是先扩展搜索树的当前边缘中最深的节点

• 一种最原始的仿生学算法，来源于爬虫在树枝的搜索过程

深度优先搜索算法:
步1把初始节点SO放入OPEN表中。

步2 若OPEN表为空.则搜索失败,退出。

步3 取OPEN表中前面第一一个节点N放入CLOSED表中并冠以顺序编号n。
步4 若目标节点Sg-N,则搜索成功,结束
步5 若N不可扩展，则转步2
步6 扩展N.将其所有子节点配上指向N的返回指针依次放入OPEN表的首部.转步2。

例:传教士和野人问题
有3个传教士和3个野人过河
只有一条能装下两个人的船
在河的任何一方或者船上，如果野人的人数大于传教士的人数，那么传教士就会有危险.
要求安全渡河

口 优点:
对内存需求比较少如果一个节点的全部后代都被完全探索过那么这个节点和它的全部后继都可以从内存(open表和closed表)中删掉了
口缺点:
不完备，也不最优

深度优先搜索的拓展—深度有限搜索
深度有限搜索
预先设定一个搜索深度l，用以解决搜索树无边界的问题
搜索过程中认为深度为的节点没有后继节点，必须回溯
缺点:增加了算法的不完备性

5.3.4 回溯策略

口双向搜索
同时进行两个搜索，可以采用任意搜索方法
个从初始状态向前搜索
另一个从目标状态向后搜索
当两个搜索在某个节点相遇时，搜索成功

5.3.5 盲目搜索的讨论

口算法评判
(1)完备性
对于一类可解的问题和一个搜索过程，如果运用该搜索过程一定能求得该类问题的解，则称该搜索过程为完备的，否则为不完备的。
完备的搜索过程称为“搜索算法”。不完备的搜索过程不是算法，称为“过程”
广度优先搜索、代价树的广度优先搜索、改进后的有界深度优先搜索都是完备的搜索过程，其它搜索过程都是不完备的。
(2)最优性一搜索得到的解是否最优解
(3)时间复杂度： 算法的时间需求

(4)空间复杂度： 算法对计算机内存的需求

(5)外显率:P=L/T
其中，L为从初始节点到目标节点的路径长度，T为整个搜索过程中所生成的节点总数。
外显率反映了搜索过程中从初始节点向目标节点前进时搜索区域的宽度。当T=L时，P=1，表示搜索过程中每次只生成一个节点，它恰好是解路径上的节点，搜索效率最高。P越小表示搜索时产生的无用节点愈多，搜索效率愈低

口 重复状态
扩展一个节点时，新生成的节点已经在open表或者closed表中存在了，这种情况称为重复状态
有些情况下，重复状态会导致搜索失败，有些情况下，重复状态可以保留，但是会带来额外的计算资源的消耗
因此，一般期望尽可能避免重复状态
这时，有可能出现节点指针重新定向的情况

5.4 启发式图搜索策略

5.4.1 启发式策略

口“启发” (heuristic): 关于发现和发明操作算子及搜索方法的研究。
口 在状态空间搜索中，启发式被定义成一系列操作算子，并能从状态空间中选择最有希望到达问题解的路径
口启发式策略：利用与问题有关的启发信息进行搜索

口运用启发式策略的两种基本情况：
(1) 一个问题由于在问题陈述和数据获取方面固有的模糊性，可能会使它没有一个确定的解
(2) 虽然一个问题可能有确定解，但是其状态空间特别大，搜索中生成扩展的状态数会随着搜索的深度呈指数级增长。

口启发式搜索，也称为有信息搜索，借助问题的特定知识来帮助选择搜索方向
口 在搜索过程中对待扩展的每一个节点进行评估，得到最好的位置，再从这个位置进行搜索直到目标。
口启发式搜索的目的是省略大量无谓的搜索路径，提高效率。
口在启发式搜索中，对节点的评价是十分重要的，估价函数是搜索成败的关键

5.4.2 启发信息和估价函数

口估价函数，也称为启发函数提供问题的启发性信息，按其用途划分，可分为以下三类
用于扩展节点的选择，即用于决定应先扩展哪个节点，以免盲目扩展
用于生成节点的选择，即用于决定应生成哪些后续节点，以免盲目地生成过多无用节点
用于删除节点的选择，即用于决定应删除哪些无用节点，以免造成进一步的时空浪费

口一个节点n的估价函数的构造通常由两部分构成

从初始节点到当前节点n的路径成本g(n)

从当前节点n到目标节点的期望成本h(n)
口即:估价函数可表示为:
f(n)=g(n)+h(n)
口其中g(x)表示从初始节点S到节点x的代价;h(x)是从节点x到目标节点S的最优路径的代价估计, 它体现了问题的启发性信息，称为启发函数。f(x)决定节点在OPEN表中的次序

口g(x)指出了搜索的横向趋势，有利于搜索的完备性，但影响搜索的效率。
口h(x)指出了搜索的纵向趋势，有利于提高搜索的效率，但影响搜索的完备性。
确定f(x)时要使g(x)+h(x)各占适当比重

贪婪搜索的启发函数只考虑待扩展节点到目标节点的期望成本，而没有考虑初始节点到待扩展节点的实际成本
贪婪搜索类似于深度优先搜索，总是先沿着一条枝搜索下去
贪梦搜索既不是完备的，也不是最优的

5.4.3 A搜索算法

口A算法
f(n)=g(n)+h(n)
代价树宽度搜索只考虑初始节点到待扩展节点的路径成本
贪婪搜索只考虑待扩展节点到目标节点的期望成本
A算法既考虑待扩展节点到目标节点的期望成本，又考虑初始节点到待扩展节点的路径成本

5.4.4 A*搜索算法及其特性分析

5.4.5 启发式搜索：爬山法

5.4.6 启发式搜索：模拟退火算法

5.4.6 启发式搜索：遗传算法

5.5 与/或图搜索策略（不考）