文档介绍：人工智能及其应用
主讲:李敏教授
智能信息处理与仪器研究室
2007年3月
一般搜索原理
前面研究的知识表示方法是问题求解所必需的。表示问题是为了进一步解决问题。从问题表示到问题的解决,有个求解的过程。也就是搜索过程。在这一过程中,采用适当的搜索技术,包括各种规则、过程和算法等推理技术,力求找到问题的解答。本章讨论一些早期的搜索技术或用于解决比较简单问题的搜索原理。
从本节起,我们将要研究如何通过网络寻找路径,进而求解问题。我们还将学****宽度优先搜索和深度优先搜索,它们均属于盲目搜索方法。盲目搜索又叫做无信息搜索,一般只适用于求解比较简单的问题。
1. 一般搜索过程
对于一个具体问题,如如何生成它所需要的部分状态空间从而实现对问题的求解呢?在人工智能中是通过运用搜索技术来解决这一问题的。
其基本思想是:首先把问题的初始状态(即初始节点—)作为当前状态,选择适用的算符对其进行操作,生成一组子状态(或称为后继状态,后继节点,子节点),然后检查目标状态是否在其中出现。若出现,则搜索成功,找到了问题的解;若不出现,则按某种搜索策略从已生成的状态中再选出一个状态作为当前状态。重复上述过程,直到目标状态出现或者不再有可供操作的状态及算符时为止。
盲目搜索
下面列出状态空间的一般搜索过程。
搜索过程中要用到两个数据结构(OPEN表与CLOSED表)。OPEN表用于存放刚生成的节点。CLOSED表用于存放将要扩展或者已扩展的节点。
所谓对一个节点进行“扩展”是指:用合适的算符对该节点进行操作,生成一组子节点。
解;若不出现,则按某种搜索策略从已生成的状态中再选出一个状态作为当前状态。重复上述过程,直到目标状态出现或者不再有可供操作的状态及算符时为止。
下面列出状态空间的一般搜索过程。
搜索过程中要用到两个数据结构(OPEN表与CLOSED表)。OPEN表用于存放刚生成的节点。CLOSED表用于存放将要扩展或者已扩展的节点。(所谓对一个节点进行“扩展”是指:用合适的算符对该节点进行操作,生成一组子节点。)
搜索的一般过程如下:
(1)把初始节点S0放入OPEN表,并建立目前只包含S0的图,记为G。
(2)检查OPEN表是否为空,若为空则问题无解,退出。
(3)把OPEN表的第一个节点取出放入CLOSED表,并记该节点为节点n。
(4)考察节点n是否为目标节点。若是,则求得了问题的解,退出。
(5)扩展节点n,生成一组子节点。把其中不是节点n先辈的那些子节点记做集合M,并把这些子节点作为节点n的子节点加入G中。
(6)针对M中子节点的不同情况,分别进行如下处理:
①对于那些未曾在G中出现过的M成员设置一个指向父节点(即节点n)的指针,并把它们放入OPEN表。
②对于那些先前已在G中出现过的M成员,确定是否需要修改它指向父节点的指针。
③对于那些先前已在G中出现并已经扩展了的M成员,确定是否需要修改其后继节点指向父节点的指针。
(7)按某种搜索策略对OPEN表中的节点进行排序
(8)转第(2)步。
说明:
(1)上述过程是状态空间的一般搜索过程,具有通用性,在此之后讨论的各种搜索策略都可以看作它的一个特例。各种搜索策略的主要区别是对OPEN表中节点排序的准则不同。例如:宽度优先搜索则把后生成的子节点排在前面。
(2)一个节点经一个算符操作后一般只生成一个子节点,但适用于一个节点的算符可能有多个,此时就会生成一组子节点。在这些子节点中可能有些是当前扩展节点(即节点n)的父节点,祖父节点等,此时不能把这些先辈节点作为当前扩展节点的子节点。余下的子节点记为集合M,并加入圈G中。这就是第(5)步要说明的意思。
(3)一个新生成的节点,它可能是第一次被生成的节点,也可能是先前已作为被生成,当前又作为另一个节点的后继节点被再次生成。此时,它究竟应作为哪个节点的后继节点呢?一般由原始节点到该节点路径上所付出的代价来决定,哪条路径付出的代价最下,相应当节点就作为它的父节点。
这就是搜索过程第(6)步所阐述的内容。
由于盲目搜索仅适用于其状态空间是树状结构的问题,因此对盲目搜索而言,不会出现一般搜索过程第(6)步中②③两点的问题,每个节点经扩展后生成的子节点都是第一次出现的节点,不必检查并修改指针方向。
(4)通过搜索所得到的图称为搜索图,由搜索图中的所有节点及反向指针(在第(6)步形成的指向父节点的指针)所构成的集合是一颗树,称为搜索树。
(5)在搜索过程中,一旦某个被考虑的节点是目标节点(第(4)步)就得到一个解。该解是由从初始节点到该目标节点上的算符构成的,而路径由第(6)步形成的反向指针指定。
(6)如果在搜索中一直找不到目标节点,而且OPEN表中不再有可供扩展的节点,则搜索失败,在第(2)步退出。