资源描述：
《人工智能3(1)搜索推理技术》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第3章确定性推理3.1图搜索策略3.2盲目搜索3.3启发式搜索3.4消解原理3.5规则演绎系统3.6产生式系统3.7非单调推理2012-9-211概述(1)问题求解§AI中每个研究领域都有其各自的特点和规律,但就求解问题的过程看,都可抽象为一个问题求解过程。§问题求解过程实际上是一个搜索,广义地说,它包含了全部计算机科学。§任何问题求解技术都包括两个重要的方面:表示和搜索§表示是基本的,搜索必须要在表示的基础上进行。表示关系到搜索的效率。§本章讨论的表示主要包括:§状态空间表示§问题空间表示概述(2)q1974年，Nilsson归纳出的AI研究的基本问题知识的模型化和表示常识性推理、演
2、绎和问题解决启发式搜索人工智能系统和语言q搜索是人工智能中的一个基本问题,是推理不可分割的一部分,直接关系到智能系统的性能和运行效率qAI为什么要研究search?问题没有直接的解法;需要探索地求解;搜索(3)什么是搜索§根据问题的实际情况不断寻找可利用的知识,构造出一条代价较少的推理路线,使问题得到圆满解决的过程称为搜索包括两个方面：---找到从初始事实到问题最终答案的一条推理路径---找到的这条路径在时间和空间上复杂度最小搜索(4)§盲目搜索:也称为无信息搜索，即只按预定的控制策略进行搜索,在搜索过程中获得的中间信息不用来改进控制策略§启发式搜索:在搜索中加入了与问题有关的启发性信
3、息,用于指导搜索朝着最有希望的方向进行,加速问题的求解过程并找到最优解要考虑的因素u完备性：当问题有解时，这个算法是否能保证找到一个解？u最优性：这个搜索策略是否能找到最优解？u时间复杂度：找到一个解需要花费多长时间？u空间复杂度：在执行搜索过程中需要有多少内存？2012-9-216无信息的搜索策略•广度优先搜索(Breadth-firstsearch)•代价一致搜索(Uniform-costsearch)•深度优先搜索(Depth-firstsearch)•深度有限搜索(Depth-limitedsearch)•双向搜索(Bidirectionalsearch)•迭代深度优先搜索(I
4、terativedeepeningdepth-firstsearch)2012-9-217有信息的搜索策略贪婪最佳优先搜索(Greedybest-firstsearch)A*搜索(A*search:Minimizingthetotalestimatedsolutioncost)递归最佳优先搜索(Recursivebest-firstsearch)BeyondClassicalSearchHeuristicsearch爬山法搜索(Hill-climbingsearch)模拟退火搜索(Simulatedannealingsearch)局部剪枝搜索(Localbeamsearch)遗传算法(
5、Geneticalgorithm)联机搜索(Onlinesearch)2012-9-218状态空间表示法(1)q状态空间表示法：用来表示问题及其搜索过程的一种方法q状态：状态是描述问题求解过程中任一时刻状况的数据结构.23751486（2,3,7,0,5,1,4,8,6）状态空间表示法(2)q状态空间:由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间.一般表示为:(S,F,G)S:问题所有的初始状态集合;F:算符集合;G:目标状态集合q算符:引起状态中某些分量发生变化,从而使问题由一个状态变为另一个状态的操作称为算符.q状态空间表示法是用“状态”和“算符”表示问题的一种方法
6、q状态空间图:状态空间的图式表示,称为状态空间图.其中节点表示状态,有向边(弧)表示算符.状态空间表示法(3)路径状态序列搜索寻找从初始状态到目标状态的路径;S0Sg状态空间表示法（4）例1:二阶梵塔问题§设有三个钢针,在一号钢针上穿有A,B两个金片,A小于B,A位于B的上面.要求把这两个金片全部移到另一个钢针上,而且规定每次只能移动一片,任何时刻都不能使B位于A的上面§设用Sk=(Sk0,Sk1)表示问题的状态,SK0表示金片A所在的钢针号,SK1表示金片B所在的钢针号,全部可能的状态为:S0=(1,1),S1=(1,2),S3=(1,3)S4=(2,1),S5=(2,2),S6=(
7、2,3)S7=(3,1),S8=(3,2),S9=(3,3)§问题初始状态集合S={S0},§目标状态集合G={S4,S8}.§算符:A(i,j):表示把金片A从第i号针移到第j号针上B(i,j):表示把B从第i号针移到第j号针上§共12个算符:§A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2)§B(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2)状态空间表示法（5）用状态空间表示
