人工智能原理PrinciplesofArtificialIntelligence

《人工智能原理PrinciplesofArtificialIntelligence》由会员分享，可在线阅读，更多相关《人工智能原理PrinciplesofArtificialIntelligence（96页珍藏版）》请在装配图网上搜索。

1、Principles of AI-Wang WenjieSearching:1 Graduate School,Chinese academy of Sciences.人工智能原理PrinciplesofArtificialIntelligence Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望Principles of AI-Wang WenjieSearching:2 Graduate School,Chinese academy of Sciences.搜索

2、技术搜索技术（一）（一）Principles of AI-Wang WenjieSearching:3 Graduate School,Chinese academy of Sciences.主要内容主要内容概述概述状态空间的搜索状态空间的搜索状态空间的一般搜索过程状态空间的一般搜索过程盲目搜索盲目搜索启发式搜索启发式搜索约束满足问题约束满足问题博弈博弈Principles of AI-Wang WenjieSearching:4 Graduate School,Chinese academy of Sciences.概述概述(1)p问题求解问题求解AI中每个研究领域都有其各自的特点和规律中每

3、个研究领域都有其各自的特点和规律,但就求解但就求解问题问题的过程看的过程看,都可抽象为一个问题求解过程都可抽象为一个问题求解过程.问题求解过程实际上是一个搜索问题求解过程实际上是一个搜索,广义地说广义地说,它包含了全部计算机科学它包含了全部计算机科学p1974年，年，Nilsson归纳出的归纳出的AI研究的基本研究的基本问题问题知识的模型化和表示知识的模型化和表示常识性推理、演绎和问题解决常识性推理、演绎和问题解决启发式搜索人工智能系统和语言人工智能系统和语言p本章讨论的表示主要包括本章讨论的表示主要包括:状态空间表示状态空间表示问题空间表示问题空间表示Principles of AI-Wan

4、g WenjieSearching:5 Graduate School,Chinese academy of Sciences.搜索搜索(2)p什么是搜索什么是搜索根据问题的实际情况不断寻找可利用的知识根据问题的实际情况不断寻找可利用的知识,构造出一条代价较少的推构造出一条代价较少的推理路线理路线,使问题得到圆满解决的过程称为使问题得到圆满解决的过程称为搜索 包括两个方面：-找到从初始事实到问题最终答案的一条推理路径 -找到的这条路径在时间和空间上复杂度最小p搜索分两大类:盲目搜索:也称为无信息搜索，即只按预定的控制策略进行也称为无信息搜索，即只按预定的控制策略进行搜索搜索,在搜索过程中获得的

5、中间信息不用来改进控制策略在搜索过程中获得的中间信息不用来改进控制策略启发式搜索:在搜索中加入了与问题有关的启发性信息在搜索中加入了与问题有关的启发性信息,用用于指导搜索朝着最有希望的方向进行于指导搜索朝着最有希望的方向进行,加速问题的求解过程加速问题的求解过程并找到最优解并找到最优解Principles of AI-Wang WenjieSearching:6 Graduate School,Chinese academy of Sciences.状态空间表示法状态空间表示法(1)q状态空间表示法：用来表示问题及其搜索过程的一种方法状态空间表示法：用来表示问题及其搜索过程的一种方法q状态状态

6、状态是描述问题求解过程中任一时刻状况的数据结构状态是描述问题求解过程中任一时刻状况的数据结构.23751486A，B，C，D（2,3,7,0,5,2,4,8,6）Principles of AI-Wang WenjieSearching:7 Graduate School,Chinese academy of Sciences.状态空间表示法状态空间表示法(2)p一般一个搜索问题由四个部分组成：一般一个搜索问题由四个部分组成：初始状态集合：定义了初始状态集合：定义了agent所处的环境；所处的环境；操作符集合：把一个问题从一个状态变换为另一个状态操作符集合：把一个问题从一个状态变换为另一个状态

7、的动作；的动作；目标检测函数：目标检测函数：agent用来确定一个状态是不是目标；用来确定一个状态是不是目标；路径费用函数：对每条路径赋予一定费用的函数。路径费用函数：对每条路径赋予一定费用的函数。p初始状态集合和操作符集合定义了问题的搜索空间初始状态集合和操作符集合定义了问题的搜索空间Principles of AI-Wang WenjieSearching:8 Graduate School,Chinese academy of Sciences.吸尘器问题吸尘器问题states?灰尘和吸尘器的位置灰尘和吸尘器的位置，共有，共有2 228actions?Left,Right,Suckgoa

8、l test?所有位置都没有灰尘所有位置都没有灰尘path cost?每一步消耗为每一步消耗为1Principles of AI-Wang WenjieSearching:9 Graduate School,Chinese academy of Sciences.八数码问题八数码问题states?数字的位置数字的位置，共有，共有9！/2=181440actions?空格的上下左右移动空格的上下左右移动goal test?给定的目标状态给定的目标状态path cost?每一步消耗为每一步消耗为1Principles of AI-Wang WenjieSearching:10 Graduate S

9、chool,Chinese academy of Sciences.状态空间表示法（状态空间表示法（3）二阶梵塔问题二阶梵塔问题设有三个钢针设有三个钢针,在一号钢针上穿有在一号钢针上穿有A,B两个金片两个金片,A小于小于B,A位于位于B的上面的上面.要求把这两要求把这两个金片全部移到另一个钢针上个金片全部移到另一个钢针上,而且规定每次只能移动一片而且规定每次只能移动一片,任何时刻都不能使任何时刻都不能使B位于位于A的上面的上面设用设用Sk=(Sk0,Sk1)表示问题的状态表示问题的状态,SK0表示金片表示金片A所在的钢针号所在的钢针号,SK1表示金片表示金片B所在的钢所在的钢针号针号,全部可能

10、的状态为全部可能的状态为:S0=(1,1),S1=(1,2),S2=(1,3)S3=(2,1),S4=(2,2),S5=(2,3)S6=(3,1),S7=(3,2),S8=(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),

11、B(3,2)Principles of AI-Wang WenjieSearching:11 Graduate School,Chinese academy of Sciences.状态空间表示法（状态空间表示法（4）用状态空间表示用状态空间表示,首先必须定义状态的描述形式首先必须定义状态的描述形式,把问题的一切状态都表把问题的一切状态都表示出来示出来,其次定义算符其次定义算符,完成状态的转换完成状态的转换问题的求解过程就是一个把算符不断地作用于状态的过程问题的求解过程就是一个把算符不断地作用于状态的过程.如果在使用如果在使用某个算符后得到的状态就是目标状态某个算符后得到的状态就是目标状态,就

12、得到了问题的解就得到了问题的解.这个解就是从这个解就是从初始状态到目标状态所用算符构成的序列初始状态到目标状态所用算符构成的序列.算符的一次使用算符的一次使用,就使问题由一种状态转变为另一种状态就使问题由一种状态转变为另一种状态.可能有多个算可能有多个算符序列都可使问题从初始状态变到目标状态符序列都可使问题从初始状态变到目标状态,这就得到了多个解这就得到了多个解.对任何一个状态对任何一个状态,可使用的算符可能不止一个可使用的算符可能不止一个,这样由一个状态所生成的这样由一个状态所生成的后继状态可能有多个后继状态可能有多个.如何选择下一步的操作如何选择下一步的操作,由搜索策略决定由搜索策略决定.

13、Principles of AI-Wang WenjieSearching:12 Graduate School,Chinese academy of Sciences.回溯搜索控制策略（回溯搜索控制策略（1）例：四皇后问题例：四皇后问题Principles of AI-Wang WenjieSearching:13 Graduate School,Chinese academy of Sciences.()Principles of AI-Wang WenjieSearching:14 Graduate School,Chinese academy of Sciences.()Q(1,1)P

14、rinciples of AI-Wang WenjieSearching:15 Graduate School,Chinese academy of Sciences.()QQ(1,1)(1,1)(2,3)Principles of AI-Wang WenjieSearching:16 Graduate School,Chinese academy of Sciences.()Q(1,1)(1,1)(2,3)Principles of AI-Wang WenjieSearching:17 Graduate School,Chinese academy of Sciences.()QQ(1,1)

15、(1,1)(2,3)(1,1)(2,4)Principles of AI-Wang WenjieSearching:18 Graduate School,Chinese academy of Sciences.()QQ(1,1)(1,1)(2,3)(1,1)(2,4)Q(1,1)(2,4)(3.2)Principles of AI-Wang WenjieSearching:19 Graduate School,Chinese academy of Sciences.()QQ(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Principles of AI-Wang

16、 WenjieSearching:20 Graduate School,Chinese academy of Sciences.()Q(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Principles of AI-Wang WenjieSearching:21 Graduate School,Chinese academy of Sciences.()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Principles of AI-Wang WenjieSearching:22 Graduate School,Chinese a

17、cademy of Sciences.()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Principles of AI-Wang WenjieSearching:23 Graduate School,Chinese academy of Sciences.()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)Principles of AI-Wang WenjieSearching:24 Graduate School,Chinese academy of Sciences.()(1

18、,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)Q(1,2)(2,4)(3,1)Principles of AI-Wang WenjieSearching:25 Graduate School,Chinese academy of Sciences.QQQQ()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)(1,2)(1,2)(2,4)(1,2)(2,4)(3,1)(1,2)(2,4)(3,1)(4,3)Principles of AI-Wang WenjieSearching:26 Graduat

19、e School,Chinese academy of Sciences.回溯搜索控制策略（回溯搜索控制策略（2）p对于对于n皇后问题可用于对搜索算法进行测试皇后问题可用于对搜索算法进行测试p对这类问题的形式化描述主要有两类：对这类问题的形式化描述主要有两类：p增量形式化：包括了增加状态描述的算符，从空状态开增量形式化：包括了增加状态描述的算符，从空状态开始；这意味着每次行动添加一个皇后到状态中去始；这意味着每次行动添加一个皇后到状态中去p完全状态形式化：把完全状态形式化：把8个皇后都放在棋盘上，然后移动它个皇后都放在棋盘上，然后移动它们。们。Principles of AI-Wang Wen

20、jieSearching:27 Graduate School,Chinese academy of Sciences.现实问题现实问题p旅行商问题旅行商问题p超大规模集成电路的布局问题超大规模集成电路的布局问题p机器人导航问题机器人导航问题.Principles of AI-Wang WenjieSearching:28 Graduate School,Chinese academy of Sciences.度量问题求解的性能度量问题求解的性能p一般搜索策略可以通过下面四个准则来评价：一般搜索策略可以通过下面四个准则来评价：完备性：如果存在一个解答，该策略是否保证能够找到？完备性：如果存在一

21、个解答，该策略是否保证能够找到？时间复杂性：需要多长时间可以找到解答？时间复杂性：需要多长时间可以找到解答？空间复杂性：执行搜索需要多少存储空间？空间复杂性：执行搜索需要多少存储空间？最优性：如果存在不同的几个解答，该策略是否可以发现最高质量的解答最优性：如果存在不同的几个解答，该策略是否可以发现最高质量的解答？p搜索策略反映了状态空间或问题空间扩展的方法，也决定了状态或问题搜索策略反映了状态空间或问题空间扩展的方法，也决定了状态或问题的访问顺序。的访问顺序。p在在AI领域，状态空间图由初始状态和算子隐含地表示，经常是无限的，领域，状态空间图由初始状态和算子隐含地表示，经常是无限的，它的复杂度

22、根据下面三个值来表达：它的复杂度根据下面三个值来表达：p分支因子分支因子b：任何节点的后继的最大个数：任何节点的后继的最大个数p最浅的目标节点的深度最浅的目标节点的深度dp状态空间中任何路径的最大长度状态空间中任何路径的最大长度mPrinciples of AI-Wang WenjieSearching:29 Graduate School,Chinese academy of Sciences.与与/或树表示法（或树表示法（1）q基本概念基本概念与与/或树是用于表示问题及其求解过程的又一种形式化方或树是用于表示问题及其求解过程的又一种形式化方法法.复杂问题的简化方法复杂问题的简化方法分解:把

23、一个问题分解到不需再分解或不能再分解为把一个问题分解到不需再分解或不能再分解为止止,然后对每个子问题进行求解然后对每个子问题进行求解,然后把各子问题的解然后把各子问题的解复合起来复合起来,就得到原问题的解就得到原问题的解.等价变换:利用同构或同态的等价变换利用同构或同态的等价变换,把复杂问题转把复杂问题转换成若干个较为容易求解的新问题换成若干个较为容易求解的新问题.若新问题中有一若新问题中有一个可求解个可求解,则就得到了原问题的解则就得到了原问题的解.Principles of AI-Wang WenjieSearching:30 Graduate School,Chinese academy

24、 of Sciences.与与/或树表示法（或树表示法（2）三阶梵塔问题三阶梵塔问题设有设有A,B,C三个金片以及三个钢针三个金片以及三个钢针,三个金片按自上而下从小到大的三个金片按自上而下从小到大的顺序穿在顺序穿在1号钢针上号钢针上,要求把它们全部移到要求把它们全部移到3号钢针上号钢针上,而且每次只能而且每次只能移到一个金片移到一个金片,任何时候都不能把大的金片压在小的金片上面任何时候都不能把大的金片压在小的金片上面.用与用与/或树表示或树表示:问题分解问题分解(1)为了把三个金片全部移到为了把三个金片全部移到3号针上号针上,必须先把必须先把C移到移到3号针上号针上(2)为了移到为了移到C,

25、必须把必须把A和和B移到移到2号针上号针上(3)当当C移到移到3针后针后,就可把就可把A和和B移到移到3针上针上,完成问题求解完成问题求解得到三个子问题得到三个子问题(1)把把A和和B移到移到2号针的双金片问题号针的双金片问题(2)把把C移到移到3号针的单金片问题号针的单金片问题(3)把把A和和B移到移到3号针的双金片问题号针的双金片问题Principles of AI-Wang WenjieSearching:31 Graduate School,Chinese academy of Sciences.状态空间搜索过程要点（状态空间搜索过程要点（1）p求解一个能够满足目标条件的问题可以表达为

26、搜索一个图以找到一个求解一个能够满足目标条件的问题可以表达为搜索一个图以找到一个满足目标状态描述的节点问题。满足目标状态描述的节点问题。p搜索过程的要点如下搜索过程的要点如下:起始节点起始节点:对应于初始状态描述对应于初始状态描述后继节点后继节点:把适用于某个节点状态描述的一些算符用来推算该节点把适用于某个节点状态描述的一些算符用来推算该节点而得到的新节点而得到的新节点,称为该节点的后继节点称为该节点的后继节点指针指针:从每个后继节点返回指向其父辈节点从每个后继节点返回指向其父辈节点检查各后继节点看是否为目标节点检查各后继节点看是否为目标节点.p搜索过程扩展后继节点的次序搜索过程扩展后继节点的

27、次序如果搜索是以接近起始节点的程度如果搜索是以接近起始节点的程度(由节点之间连结弧线的数目来由节点之间连结弧线的数目来衡量衡量)依次扩展节点依次扩展节点,称为广称为广(宽宽)度优先搜索度优先搜索如果搜索时首先扩展最新产生的节点如果搜索时首先扩展最新产生的节点,称为深度优先搜索称为深度优先搜索Principles of AI-Wang WenjieSearching:32 Graduate School,Chinese academy of Sciences.状态空间搜索过程要点（状态空间搜索过程要点（2）调整指针调整指针扩展一个节点扩展一个节点生成出该节点的所有后继节点。生成出该节点的所有后继

28、节点。弧的费用弧的费用有一条弧连接有一条弧连接ni和和nj两个节点两个节点,用用C(ni,nj)表示从表示从ni到到nj的费用的费用(耗耗散值散值)。路径的耗散值路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用用C(ni,nj)表示从表示从ni到到nj的路径的耗散值。的路径的耗散值。Principles of AI-Wang WenjieSearching:33 Graduate School,Chinese academy of Sciences.状态空间的一般搜索过程（状态空间的一般搜索过程（1）主要数据结构

29、主要数据结构OPEN表表:存放刚生成的节点存放刚生成的节点,是还未扩展的节点是还未扩展的节点.一般是一般是端节点端节点.CLOSED表表:存放将要扩展或已扩展的节点存放将要扩展或已扩展的节点.或者是已被或者是已被扩展但还没有在搜索树中生成后继节点的端节点扩展但还没有在搜索树中生成后继节点的端节点,或者是或者是非端节点非端节点Principles of AI-Wang WenjieSearching:34 Graduate School,Chinese academy of Sciences.状态空间的一般搜索过程（状态空间的一般搜索过程（2）(1)把初始节点把初始节点S0放入放入OPEN表表,

30、并建立目前只包含并建立目前只包含S0的图的图,记为记为G(2)检查检查OPEN表是否为空表是否为空,若为空则问题无解若为空则问题无解,退出退出(3)把把OPEN表的第一个节点取出放入表的第一个节点取出放入CLOSED表表,记该节点为记该节点为n(4)考察考察n是否为目标节点是否为目标节点.如是如是,则问题得解则问题得解,退出退出(5)扩展节点扩展节点n,生成一组子节点生成一组子节点.把其中不是节点把其中不是节点n先辈的那些节点记作集合先辈的那些节点记作集合M,并并把这些子节点作为节点把这些子节点作为节点n的子节点加入的子节点加入G中中(6)针对针对M中子节点的不同情况中子节点的不同情况,分别进

31、行处理分别进行处理1.对于那些未曾在对于那些未曾在G中出现过的中出现过的M成员设置一个指向父节点成员设置一个指向父节点(即即n)的指针的指针,并并把它们放入把它们放入OPEN表表2.对于那些先前已在对于那些先前已在G中出现过的中出现过的M成员成员,确定是否需要修改它指向父节点确定是否需要修改它指向父节点的指针的指针3.对于那些先前已在对于那些先前已在G中出现并且已经扩展了的中出现并且已经扩展了的M成员成员,确定是否需要修改确定是否需要修改其后继节点指向父节点的指针其后继节点指向父节点的指针(7)按某种搜索策略对按某种搜索策略对OPEN表中的节点进行排序表中的节点进行排序(8)转第转第(2)步步

32、Principles of AI-Wang WenjieSearching:35 Graduate School,Chinese academy of Sciences.例子例子SOPENCLOSES 123 S 1,2,3 S 2,1,3 S 451,3 S,2 1,3,4,5 S,2 3,1,4,5 S,2 1,4,5 S,2,3 61,4,5,6 S,2,3 Principles of AI-Wang WenjieSearching:36 Graduate School,Chinese academy of Sciences.2S13451,2,3 S 3,1,2 S OPENCLOSE

33、S 4,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 1414,10,11,9,7,5,2 S,3,4,6,8,1,12,13 Principles of AI-Wang WenjieSearching:37 Graduate School,Chinese academy of Sciences.2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 676,7,5,1,2

34、S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 14OPEN表中的节点修改指针Principles of AI-Wang WenjieSearching:38 Graduate School,Chinese academy of Sciences.2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,

35、4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 1413,10,11,9,7,5 S,3,4,6,8,1,12,2 Principles of AI-Wang WenjieSearching:39 Graduate School,Chinese academy of Sciences.2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,

36、2 S,3,4,6,8,1,12 1413,10,11,9,7,5 S,3,4,6,8,1,12,2 CLOSE表中的节点修改指针Principles of AI-Wang WenjieSearching:40 Graduate School,Chinese academy of Sciences.2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,1

37、2 1413,10,11,9,7,5 S,3,4,6,8,1,12,2 CLOSE表中的节点(8)的后裔(10)修改指针Principles of AI-Wang WenjieSearching:41 Graduate School,Chinese academy of Sciences.状态空间的一般搜索过程状态空间的一般搜索过程(3)q这是一个通用的搜索过程这是一个通用的搜索过程,后面讨论的状态空间各种搜索策后面讨论的状态空间各种搜索策略都是其特例略都是其特例.各种搜索策略的主要区别就是对各种搜索策略的主要区别就是对OPEN表中节表中节点排序准则不同点排序准则不同q算法结束后，将生成一个图

38、算法结束后，将生成一个图G，称为称为搜索图。同时由于每个。同时由于每个节点都有一个指针指向父节点，这些指针指向的节点构成节点都有一个指针指向父节点，这些指针指向的节点构成G的一个支撑树，称为的一个支撑树，称为搜索树。q从目标节点开始，将指针指向的状态回串起来，即找到一条从目标节点开始，将指针指向的状态回串起来，即找到一条解路径.Principles of AI-Wang WenjieSearching:42 Graduate School,Chinese academy of Sciences.盲目搜索盲目搜索盲目盲目 搜索策略只使用问题定义中的信息搜索策略只使用问题定义中的信息宽度优先搜索宽

39、度优先搜索代价一致搜索代价一致搜索深度优先搜索深度优先搜索深度有限搜索深度有限搜索迭代加深搜索迭代加深搜索Principles of AI-Wang WenjieSearching:43 Graduate School,Chinese academy of Sciences.广度优先搜索（广度优先搜索（1）搜索过程如下搜索过程如下:(1)把初始节点把初始节点S0放入放入OPEN表表(2)如果如果OPEN表为空表为空,则问题无解则问题无解,退出退出(3)把把OPEN表的第一个节点表的第一个节点(记为节点记为节点n)取出取出,放入放入CLOSED表表(4)考查节点考查节点n是否为目标节点是否为目标

40、节点.若是若是,则求得了问题的解则求得了问题的解,退出退出(5)若节点若节点n不可扩展不可扩展,则转第则转第(2)步步(6)扩展节点扩展节点n,将其子节点放入将其子节点放入OPEN表的表的尾部,并为每一个子节点都并为每一个子节点都配置指向父节点的指针配置指向父节点的指针,转第转第(2)步步扩展最浅的未扩展的节点扩展最浅的未扩展的节点实现实现:FIFO队列队列Principles of AI-Wang WenjieSearching:44 Graduate School,Chinese academy of Sciences.23184765231847652831476523184765283

41、147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标8234187654Principles of AI-Wang WenjieSearching:45 Graduate School,Chinese academy of Sciences.广度优先搜索（广度优先搜索（2）Complete?Yes(如果如果 b 是有限的是有限的)Time?1+b+b2+b3+bd+b(bd-1)=O(bd+1)Space?O(bd+1)Optimal?Yes(如

42、果每步代价为如果每步代价为1)空间空间是大问题是大问题(和时间相比和时间相比)特点特点缺点缺点当目标节点距离初始节点较远时会产生许多无用的节点当目标节点距离初始节点较远时会产生许多无用的节点,搜索效率搜索效率低低优点优点只要问题有解只要问题有解,则总可以得到解则总可以得到解,而且是最短路径的解而且是最短路径的解Principles of AI-Wang WenjieSearching:46 Graduate School,Chinese academy of Sciences.深度优先搜索（深度优先搜索（1）搜索过程如下搜索过程如下:(1)把初始节点把初始节点S0放入放入OPEN表表(2)如果

43、如果OPEN表为空表为空,则问题无解则问题无解,退出退出(3)把把OPEN表的第一个节点表的第一个节点(记为节点记为节点n)取出取出,放入放入CLOSED表表(4)考查节点考查节点n是否为目标节点是否为目标节点.若是若是,则求得了问题的解则求得了问题的解,退出退出(5)若节点若节点n不可扩展不可扩展,则转第则转第(2)步步(6)扩展节点扩展节点n,将其子节点放入将其子节点放入OPEN表的表的首部,并为每一个子节点都并为每一个子节点都配置指向父节点的指针配置指向父节点的指针,转第转第(2)步步扩展最深的未扩展节点扩展最深的未扩展节点实现实现:LIFO队列队列Principles of AI-Wa

44、ng WenjieSearching:47 Graduate School,Chinese academy of Sciences.23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476528364175283167548321476528371465281437652831457623456789abcd12384765目标Principles of AI-Wang WenjieSearching:48 Gra

45、duate School,Chinese academy of Sciences.深度优先搜索（深度优先搜索（2）Complete?No:当空间为无限深度时当空间为无限深度时Time?O(bm):如果如果 m 比比d大很多则比较严重大很多则比较严重Space?O(bm),线性空间线性空间Optimal?No特点特点缺点缺点如果目标节点不在搜索所进入的分支上如果目标节点不在搜索所进入的分支上,而该分支又是而该分支又是一个无穷分支一个无穷分支,则就得不到解则就得不到解.因此该算法是不完备的因此该算法是不完备的优点优点如果目标节点不在搜索所进入的分支上如果目标节点不在搜索所进入的分支上,则可以较快地

46、则可以较快地得到解得到解Principles of AI-Wang WenjieSearching:49 Graduate School,Chinese academy of Sciences.有界深度优先搜索有界深度优先搜索q定义搜索深度的界限定义搜索深度的界限dm,当搜索深度达到了深度界限当搜索深度达到了深度界限,而尚未出现目标节点时而尚未出现目标节点时,就换一个分支进行搜索就换一个分支进行搜索搜索过程如下搜索过程如下:(1)把初始节点把初始节点S0放入放入OPEN表表,置置S0的深度的深度d(S0)=0(2)如果如果OPEN表为空表为空,则问题无解则问题无解,退出退出(3)把把OPEN表

47、的第一个节点表的第一个节点(记为节点记为节点n)取出取出,放入放入CLOSED表表(4)考查节点考查节点n是否为目标节点是否为目标节点.若是若是,则求得了问题的解则求得了问题的解,退出退出(5)如果节点如果节点n的深度的深度d(节点节点n)=dm,则转第则转第(2)步步(6)若节点若节点n不可扩展不可扩展,则转第则转第(2)步步(7)扩展节点扩展节点n,将其子节点放入将其子节点放入OPEN表的表的首部,并为每一个子节点都配置指向并为每一个子节点都配置指向父节点的指针父节点的指针,转第转第(2)步步Principles of AI-Wang WenjieSearching:50 Graduate

48、 School,Chinese academy of Sciences.迭代加深搜索（迭代加深搜索（1 1）对于有界深度搜索策略，有下面几点需要说明：对于有界深度搜索策略，有下面几点需要说明：1 1）在有界深度搜索算法中，深度限制）在有界深度搜索算法中，深度限制d dm m是一个很重要的参数。是一个很重要的参数。2 2）深度限制）深度限制d dm m不能太大。不能太大。3 3）有界深度搜索的主要问题是深度限制值）有界深度搜索的主要问题是深度限制值d dm m的选取。的选取。问题：但是对很多问题，我们并不知道该值到底为多少，问题：但是对很多问题，我们并不知道该值到底为多少，直到该问题求解完成了，

49、才可以确定出深度限制直到该问题求解完成了，才可以确定出深度限制d dm m。Principles of AI-Wang WenjieSearching:51 Graduate School,Chinese academy of Sciences.迭代加深搜索（迭代加深搜索（2 2）改进方法改进方法-迭代加深搜索算法迭代加深搜索算法 ：先任意给定一个较小的数作为先任意给定一个较小的数作为d dm m，然后按有界深度算法然后按有界深度算法搜索，若在此深度限制内找到了解，则算法结束；如在搜索，若在此深度限制内找到了解，则算法结束；如在此限度内没有找到问题的解，则增大深度限制此限度内没有找到问题的解，

50、则增大深度限制d dm m，继续继续搜索。搜索。迭代加深搜索是一种回避选择最优深度限制问题的策略，迭代加深搜索是一种回避选择最优深度限制问题的策略，它是试图尝试所有可能的深度限制：首先深度为它是试图尝试所有可能的深度限制：首先深度为0 0，然后，然后深度为深度为1 1，然后为，然后为2 2，等等，一直进行下去。，等等，一直进行下去。问题：问题：迭代加深搜索看起来会很浪费，因为很多节点都要扩展迭代加深搜索看起来会很浪费，因为很多节点都要扩展多次。多次。Principles of AI-Wang WenjieSearching:52 Graduate School,Chinese academy

51、of Sciences.迭代加深搜索（迭代加深搜索（3 3）Principles of AI-Wang WenjieSearching:53 Graduate School,Chinese academy of Sciences.迭代加深搜索（迭代加深搜索（4 4）Principles of AI-Wang WenjieSearching:54 Graduate School,Chinese academy of Sciences.迭代加深搜索（迭代加深搜索（5 5）Principles of AI-Wang WenjieSearching:55 Graduate School,Chinese

52、 academy of Sciences.迭代加深搜索（迭代加深搜索（6 6）Principles of AI-Wang WenjieSearching:56 Graduate School,Chinese academy of Sciences.迭代加深搜索（迭代加深搜索（6 6）深度为深度为d，分支因子为，分支因子为b的深度优先搜索生成的节点数为：的深度优先搜索生成的节点数为：NDLS=b0+b1+b2+bd-2+bd-1+bd 深度为深度为d，分支因子为，分支因子为b的迭代加深搜索生成的节点数为的迭代加深搜索生成的节点数为NIDS=(d+1)b0+d b1+(d-1)b2+3bd-2+2

53、bd-1+1bd 对于对于 b=10,d=5,NDLS=1+10+100+1,000+10,000+100,000=111,111NIDS=6+50+400+3,000+20,000+100,000=123,456增加增加=(123,456-111,111)/111,111=11%Principles of AI-Wang WenjieSearching:57 Graduate School,Chinese academy of Sciences.迭代加深搜索（迭代加深搜索（7 7）Complete?YesTime?(d+1)b0+d b1+(d-1)b2+bd=O(bd)Space?O(bd

54、)Optimal?Yes,如果每步代价为如果每步代价为1Principles of AI-Wang WenjieSearching:58 Graduate School,Chinese academy of Sciences.其他问题其他问题避免重复状态：由于扩展已经遇到并扩展过的状态可能造成避免重复状态：由于扩展已经遇到并扩展过的状态可能造成时间的浪费时间的浪费利用利用CLOSED表，如果当前节点与其中的某个节点相匹配的话，那么表，如果当前节点与其中的某个节点相匹配的话，那么它可以被放弃而不去扩展，或者需要比较耗散值它可以被放弃而不去扩展，或者需要比较耗散值如果单步耗散为常数时，代价广度优先

55、搜索找到的总是最优路径如果单步耗散为常数时，代价广度优先搜索找到的总是最优路径使用不完全信息的搜索：使用不完全信息的搜索：无传感问题：无传感问题：Agent了解它的每个行动的结果，但是没有传感器。了解它的每个行动的结果，但是没有传感器。从从Agent可能到达的状态中搜索，而不是实际状态空间中搜索可能到达的状态中搜索，而不是实际状态空间中搜索偶发性问题：环境是部分可观察的，或者行动是不确定的。在每个行偶发性问题：环境是部分可观察的，或者行动是不确定的。在每个行动后动后Agent能从感知器中得到新的信息。能从感知器中得到新的信息。其解答往往表现为树的形式，对树的分支的选择取决于树上结点接收到的感知

56、信息其解答往往表现为树的形式，对树的分支的选择取决于树上结点接收到的感知信息Principles of AI-Wang WenjieSearching:59 Graduate School,Chinese academy of Sciences.主要内容主要内容概述概述状态空间的搜索状态空间的搜索状态空间的一般搜索过程状态空间的一般搜索过程盲目搜索盲目搜索启发式搜索启发式搜索约束满足问题约束满足问题博弈博弈Principles of AI-Wang WenjieSearching:60 Graduate School,Chinese academy of Sciences.启发式搜索（启发式搜

57、索（1）q前面讨论的方法都是盲目的搜索方法前面讨论的方法都是盲目的搜索方法,即都没有利用问题本身即都没有利用问题本身的特性信息的特性信息,在决定要被扩展的节点时在决定要被扩展的节点时,都没有考虑该节点在都没有考虑该节点在解的路径上的可能性有多大解的路径上的可能性有多大,它是否有利于问题求解以及求出它是否有利于问题求解以及求出的解是否为最优的解是否为最优q启发式搜索要用到问题自身的某些特性信息启发式搜索要用到问题自身的某些特性信息,以指导搜索朝着以指导搜索朝着最有希望的方向前进最有希望的方向前进启发信息的强度启发信息的强度强：降低搜索工作量，但可能导致找不到最优解强：降低搜索工作量，但可能导致找

58、不到最优解弱：一般导致工作量加大，极限情况下变为盲目搜索，但弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解可能可以找到最优解Principles of AI-Wang WenjieSearching:61 Graduate School,Chinese academy of Sciences.启发式搜索（启发式搜索（2）q启发性信息和估价函数启发性信息和估价函数用于指导搜索过程用于指导搜索过程,且与具体问题有关的控制性信息称为为且与具体问题有关的控制性信息称为为启发性信息启发性信息用于评价节点重要性的函数称为估价函数用于评价节点重要性的函数称为估价函数.记为记为 f(x)

59、=g(x)+h(x)g(x)为从初始节点为从初始节点S0到节点到节点x已经实际付出的代价已经实际付出的代价h(x)是从节点是从节点x到目标节点到目标节点Sg的最优路径的估价代价的最优路径的估价代价,体体现了问题的启发性信息现了问题的启发性信息,称为启发函数称为启发函数f(x)表示从初始节点经过节点表示从初始节点经过节点x到达目标节点的最优路径到达目标节点的最优路径的代价估价值的代价估价值,其作用是用来评估其作用是用来评估OPEN表中各节点的重表中各节点的重要性要性,决定其次序决定其次序Principles of AI-Wang WenjieSearching:62 Graduate Schoo

60、l,Chinese academy of Sciences.启发式搜索（启发式搜索（3）启发式就是要猜测：启发式就是要猜测：从节点从节点n开始，找到最优解的可能性有多大？开始，找到最优解的可能性有多大？从起始节点开始，经过节点从起始节点开始，经过节点n，到达目标节点到达目标节点的最佳路径的费用是多少？的最佳路径的费用是多少？(存在一个约束存在一个约束)ghPrinciples of AI-Wang WenjieSearching:63 Graduate School,Chinese academy of Sciences.最佳优先搜索（最佳优先搜索（1）p思想:对每个节点使用估价函数,估计希望

61、:扩展最有希望未扩展的节点p主要包括:-贪婪最佳优先搜索 -A*算法Principles of AI-Wang WenjieSearching:64 Graduate School,Chinese academy of Sciences.最佳优先搜索（最佳优先搜索（2）Principles of AI-Wang WenjieSearching:65 Graduate School,Chinese academy of Sciences.贪婪最佳优先搜索贪婪最佳优先搜索(1)启发失函数启发失函数 f(n)=h(n):从从n到最近的目标节点代价的估计到最近的目标节点代价的估计这里采用这里采用hSL

62、D(n):从从n到到Bucharest的直线距离的直线距离贪婪算法扩展看来与目标最近的节点贪婪算法扩展看来与目标最近的节点Principles of AI-Wang WenjieSearching:66 Graduate School,Chinese academy of Sciences.贪婪最佳优先搜索贪婪最佳优先搜索(2)Principles of AI-Wang WenjieSearching:67 Graduate School,Chinese academy of Sciences.贪婪最佳优先搜索贪婪最佳优先搜索(3)Principles of AI-Wang WenjieSea

63、rching:68 Graduate School,Chinese academy of Sciences.贪婪最佳优先搜索贪婪最佳优先搜索(4)Principles of AI-Wang WenjieSearching:69 Graduate School,Chinese academy of Sciences.贪婪最佳优先搜索贪婪最佳优先搜索(5)特性特性完备性完备性:NO时间时间:O(bm),但是一个好的启发式可以得到很大的改进但是一个好的启发式可以得到很大的改进空间空间:O(bm),保存所有的节点在内存中保存所有的节点在内存中最优最优:NOPrinciples of AI-Wang W

64、enjieSearching:70 Graduate School,Chinese academy of Sciences.A*算法算法(1)q思想思想:避免对已经扩展的路径进行再扩展避免对已经扩展的路径进行再扩展q评价函数为评价函数为:f(x)=g(x)+h(x)1)把把OPEN表中的节点按表中的节点按此此函数的值从小到大进行排序函数的值从小到大进行排序2)g(x)是对是对g*(x)的估价的估价,g(x)03)h(x)是是h*(x)的下界的下界,即对所有的即对所有的x,h(x)=h*(x)其中其中:g*(x)是从初始节点是从初始节点S0到节点到节点x的最小代价的最小代价 h*(x)是从节点是

65、从节点x到目标节点的最小代价到目标节点的最小代价,若有多个目标节点若有多个目标节点,则为则为 其中最小的一个其中最小的一个Principles of AI-Wang WenjieSearching:71 Graduate School,Chinese academy of Sciences.nSg*(n)h*(n)gPrinciples of AI-Wang WenjieSearching:72 Graduate School,Chinese academy of Sciences.A*算法（算法（2）f*(S)f*(S)=g*(S)+h*(S)=h*(S)从从S无约束地到达目标的最佳路经上的

66、耗散值无约束地到达目标的最佳路经上的耗散值;g(n)一般一般取实际走过的路径的费用和取实际走过的路径的费用和.g(n)g*(n)随着算法的执行，由于指针的变动，随着算法的执行，由于指针的变动，g(n)会下降会下降.h 0没有启发式信息没有启发式信息;Principles of AI-Wang WenjieSearching:73 Graduate School,Chinese academy of Sciences.A*算法（算法（3）8数码问题数码问题h(n)=“不在位不在位”的将牌数的将牌数h(n)=将牌将牌“不在位不在位”的距离和的距离和2831647512345768将牌1：1将牌2：1将牌6：1将牌8：2Principles of AI-Wang WenjieSearching:74 Graduate School,Chinese academy of Sciences.A*算法（算法（4）Principles of AI-Wang WenjieSearching:75 Graduate School,Chinese academy of Sciences.A*算法（算法（5