第五章人工智能搜索策略

《第五章人工智能搜索策略》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、人工智能ArtificialIntelligence主讲：杨利英西安电子科技大学计算机学院E_mail：yangliying1208@163.com第五章搜索策略5.1基本概念5.2状态空间的搜索策略5.3与/或树的搜索策略5.4搜索的完备性与效率5.1基本概念采用某种策略，在知识库中寻找可利用的知识，从而构造一条代价较小的推理路线，使问题得到解决的过程称为搜索。5.1.1什么是搜索5.1.1什么是搜索搜索分为盲目搜索和启发式搜索。盲目搜索是按照预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。启发式搜索是在搜索中

2、加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。5.1.2状态空间表示法状态空间用“状态”和“算符”来表示问题。状态状态用以描述问题在求解过程中不同时刻的状态，一般用向量表示算符使问题从一个状态转变为另一个状态的操作称为算符。状态空间由所有可能出现的状态及一切可用算符所构成的集合称为问题的状态空间。回顾状态空间示例：十五数码难题11915134127586132101411941513127586132101411915134127586132101411941513127586132

3、1014119151341275861321014119415131275861321014119415138127561321014119415131275861321014回顾5.1.3与/或树表示法对于一个复杂问题，直接求解往往比较困难。此时可通过下述方法进行简化：（1）分解（2）等价变换回顾5.1.3与/或树表示法（1）分解把一个复杂问题分解为若干个较为简单的子问题，每个子问题又可继续分解。重复此过程，直到不需要再分解或者不能再分解为止。如此形成“与”树。（2）等价变换利用同构或同态的等价变换，把原问题变换为若干个较为容易求解

4、的新问题。如此形成“或”树。回顾与/或树分解与等价变换可以结合起来使用，这样形成的图称为“与/或树”回顾由可解节点所构成，并且由这些可解节点可推出初始节点为可解节点的子树称为解树(t表示终止节点)。解树中一定包含初始节点。（它对应于原始问题）解树回顾5.2状态空间的搜索策略5.2状态空间的搜索策略盲目搜索搜索按规定的路线进行，不使用与问题有关的启发性信息；适用于其状态空间图是树状结构的一类问题。启发式搜索使用与问题有关的启发性信息，并以这些启发性信息指导搜索过程，可以高效地求解结构复杂的问题。5.2.1状态空间的一般搜索过程一个复杂问

5、题的状态空间一般都是十分庞大的。如64阶梵塔问题共有3的64次方个不同的状态。把问题的所有状态空间都进行存储有时候是不可能的。把问题的所有状态空间都进行存储也是不必要的。因为与解题有关的状态空间往往只是整个状态空间的一部分，只要能生产并存储这部分状态空间就可以求出问题的解。5.2.1状态空间的一般搜索过程如何产生问题需要的状态空间从而实现对问题的求解呢？答案就是搜索技术。搜索技术基本思想：把问题的初始状态作为当前状态，选择适用的算符对其操作，生产一组子状态，然后检查目标状态是否在其中出现。若出现，则搜索成功，找到了问题的解，否则按某种

6、搜索策略从已生成的状态中再选择一个作为当前状态。重复上述过程，直到目标状态出现或者不再有可供操作的状态及算符为止。5.2.1状态空间的一般搜索过程OPEN表和CLOSE表OPEN表用于存放刚生成的节点。对于不同的搜索策略，节点在OPEN表中的排列顺序是不同的。CLOSE表用于存放将要扩展的节点。对一个节点的扩展是指：用所有可适用的算符对该节点进行操作，生成一组子节点OPEN表状态节点父节点编号状态节点父节点CLOSE表搜索的一般过程把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G；检查OPEN表是否为空，若为空则问题无解

7、，退出；把OPEN表的第一个节点取出放入CLOSE表，并计该节点为n；考察节点n是否为目标节点。若是，则求得了问题的解，退出；扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点记做集合M，并把这些子节点作为节点n的子节点加入G中；针对M中子节点的不同情况，分别进行如下处理：对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表；（不在OPEN表）对于那些先前已经在G中出现过的M成员，确定是否需要修改它指向父节点的指针；（在OPEN表中）对于那些先前已在G中出现并且已经扩展了的M成员，确定

8、是否需要修改其后继节点指向父节点的指针；（在CLOSE表中）按某种搜索策略对OPEN表中的节点进行排序；转第2步。搜索的一般过程对一般搜索过程的一些说明一个节点经一个算符操作后一般只生成一个子节点。但适用于一个节点的算符