人工智能课件搜索技术.ppt

《人工智能课件搜索技术.ppt》由会员分享，可在线阅读，更多相关《人工智能课件搜索技术.ppt（113页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、Searching:1搜索策略第一页，编辑于星期六：十五点 四十三分。Searching:2 搜索是人工智能中的一个基本问题，并与推理密切相关，搜索是人工智能中的一个基本问题，并与推理密切相关，搜索策略的优劣，将直接影响到智能系统的性能与推理效率。搜索策略的优劣，将直接影响到智能系统的性能与推理效率。第二页，编辑于星期六：十五点 四十三分。Searching:3主要内容主要内容状态空间的表示状态空间的表示搜索的基本概念搜索的基本概念状态空间的搜索状态空间的搜索状态空间的一般搜索过程状态空间的一般搜索过程盲目搜索盲目搜索启发式搜索启发式搜索第三页，编辑于星期六：十五点 四十三分。Searchin

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

3、状态空间表示问题空间表示问题空间表示第四页，编辑于星期六：十五点 四十三分。Searching:5搜索的基本概念搜索的基本概念搜索的含义搜索的含义状态空间法状态空间法第五页，编辑于星期六：十五点 四十三分。Searching:6适用情况：适用情况：不良结构或非结构化问题；难以获得求解所需的全部信息；更不良结构或非结构化问题；难以获得求解所需的全部信息；更没有现成的算法可供求解使用。没有现成的算法可供求解使用。概念：概念：依靠经验，利用已有知识，根据问题的实际情况，不断寻找可依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以利用知识，从而构

4、造一条代价最小的推理路线，使问题得以解决的过程称为搜索解决的过程称为搜索第六页，编辑于星期六：十五点 四十三分。Searching:7搜索的类型搜索的类型按是否使用启发式信息：按是否使用启发式信息：盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。中间信息并不改变控制策略。启发式搜索：在搜索中加入了与问题有关的启发性信息，用于启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。找到最优解。按问题

5、的表示方式：按问题的表示方式：状态空间搜索：用状态空间法来求解问题所进行的搜索状态空间搜索：用状态空间法来求解问题所进行的搜索 与或树搜索：用问题归约法来求解问题时所进行的搜索与或树搜索：用问题归约法来求解问题时所进行的搜索 第七页，编辑于星期六：十五点 四十三分。Searching:8p什么是搜索什么是搜索根据问题的实际情况不断寻找可利用的知识根据问题的实际情况不断寻找可利用的知识,构造出一条代价较少的推构造出一条代价较少的推理路线理路线,使问题得到圆满解决的过程称为使问题得到圆满解决的过程称为搜索 包括两个方面：-找到从初始事实到问题最终答案的一条推理路径 -找到的这条路径在时间和空间上复

6、杂度最小p搜索分两大类:盲目搜索:也称为无信息搜索，即只按预定的控制策略进行搜也称为无信息搜索，即只按预定的控制策略进行搜索索,在搜索过程中获得的中间信息不用来改进控制策略在搜索过程中获得的中间信息不用来改进控制策略启发式搜索:在搜索中加入了与问题有关的启发性信息在搜索中加入了与问题有关的启发性信息,用于指导用于指导搜索朝着最有希望的方向进行搜索朝着最有希望的方向进行,加速问题的求解过程并找到最优解加速问题的求解过程并找到最优解第八页，编辑于星期六：十五点 四十三分。Searching:9状态空间法状态空间法状态状态(State)：是表示问题求解过程中每一步问题状况的数据结构，它可是表示问题求

7、解过程中每一步问题状况的数据结构，它可形式地表示为：形式地表示为：Sk=Sk0,Sk1,当对每一个分量都给以确定的值时，就得到了一个具体的当对每一个分量都给以确定的值时，就得到了一个具体的状态。状态。操作操作(Operator)也称为算符，它是把问题从一种状态变换为另一种状态的也称为算符，它是把问题从一种状态变换为另一种状态的手段。操作可以是一个机械步骤，一个运算，一条规则或一手段。操作可以是一个机械步骤，一个运算，一条规则或一个过程。操作可理解为状态集合上的一个函数，它描述了状个过程。操作可理解为状态集合上的一个函数，它描述了状态之间的关系。态之间的关系。第九页，编辑于星期六：十五点 四十三

8、分。Searching:10状态空间状态空间(State space)用来描述一个问题的全部状态以及这些状态之间的相互关用来描述一个问题的全部状态以及这些状态之间的相互关系。常用一个三元组表示为：系。常用一个三元组表示为：(S,F,G)其中，其中，S为问题的所有初始状态的集合；为问题的所有初始状态的集合；F为操作的集合；为操作的集合；G为目标状态的集合。为目标状态的集合。状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图。在状态空间图中，节点表示问题的状态，有向状态空间图。在状态空间图中，节点表示问题的状态，有向边表示操作。边表示操作

9、。第十页，编辑于星期六：十五点 四十三分。Searching:11状态空间表示法状态空间表示法状态空间表示法是用来表示问题及其搜索过程的一种方法状态空间表示法是用来表示问题及其搜索过程的一种方法q状态状态状态是描述问题求解过程中任一时刻状况的数据结构状态是描述问题求解过程中任一时刻状况的数据结构.23751486A，B，C，D（2,3,7,0,5,2,4,8,6）第十一页，编辑于星期六：十五点 四十三分。Searching:12状态空间表示法状态空间表示法p一般一个搜索问题由四个部分组成：一般一个搜索问题由四个部分组成：初始状态集合：定义了初始状态集合：定义了agent所处的环境；所处的环境；

10、操作符集合：把一个问题从一个状态变换为另一个状态的操作符集合：把一个问题从一个状态变换为另一个状态的动作；动作；目标检测函数：目标检测函数：agent用来确定一个状态是不是目标；用来确定一个状态是不是目标；路径费用函数：对每条路径赋予一定费用的函数。路径费用函数：对每条路径赋予一定费用的函数。p初始状态集合和操作符集合定义了问题的搜索空间初始状态集合和操作符集合定义了问题的搜索空间第十二页，编辑于星期六：十五点 四十三分。Searching:13 状态空间法求解问题的基本过程：状态空间法求解问题的基本过程：首先为问题选择适当的首先为问题选择适当的“状态状态”及及“操作操作”的形式化描述方法；的

11、形式化描述方法；然后从某个初始状态出发，每次使用一个然后从某个初始状态出发，每次使用一个“操作操作”，递增地建，递增地建立起操作序列，直到达到目标状态为止；立起操作序列，直到达到目标状态为止；此时，由初始状态到目标状态所使用的算符序列就是该问此时，由初始状态到目标状态所使用的算符序列就是该问题的一个解。题的一个解。第十三页，编辑于星期六：十五点 四十三分。Searching:14八数码问题八数码问题states 数字的位置数字的位置，共有，共有9！/2=181440actions 空格的上下左右移动空格的上下左右移动goal test 给定的目标状态给定的目标状态path cost 每一步消耗

12、为每一步消耗为1第十四页，编辑于星期六：十五点 四十三分。Searching:15二阶梵塔问题二阶梵塔问题 二二阶阶梵梵塔塔问问题题。设设有有三三根根钢钢针针，它它们们的的编编号号分分别别是是1号号、2号号和和3号号。在在初初始始情情况况下下，1号号钢钢针针上上穿穿有有A、B两两个个金金片片，A比比B小小，A位位于于B的的上上面面。要要求求把把这这两两个个金金片片全全部部移移到到另另一一根根钢钢针针上上，而而且且规规定定每每次次只只能能移移动动一一个个金金片片，任任何何时时刻刻都都不不能能使使大的位于小的上面大的位于小的上面。第十五页，编辑于星期六：十五点 四十三分。Searching:16

13、解：解：设用设用Sk=(Sk0,Sk1)表示问题的状态，其中，表示问题的状态，其中，Sk0表示金表示金片片A所在的钢针号，所在的钢针号，Sk1表示金片表示金片B所在的钢针号。全部可能所在的钢针号。全部可能的问题状态共有以下的问题状态共有以下9种：种：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)第十六页，编辑于星期六：十五点 四十三分。Searching:17ABABAB123123123二阶梵塔问题的初始状态和目标状态二阶梵塔问题的初始状态和目标状态问题的初始状态集合问题的初始状态集合为为S=S

14、0 目标状态集合目标状态集合为为G=S4,S5初始状态初始状态S0和目标状态和目标状态S4、S8如图所示如图所示 S0=(1,1)S4=(2,2)S8=(3,3)第十七页，编辑于星期六：十五点 四十三分。Searching:18 操作分别用操作分别用A(i,j)和和B(i,j)表示表示 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)

15、B(1,3)B(2,1)B(2,3)B(3,1)B(3,2)根据上述根据上述9种可能的状态和种可能的状态和12种操作，可构成二阶梵塔问种操作，可构成二阶梵塔问题的状态空间图，如下图所示。题的状态空间图，如下图所示。第十八页，编辑于星期六：十五点 四十三分。Searching:19(3,3)(1,3)(1,2)(2,2)二阶梵塔的状态空间图 从初始节点从初始节点(1,1)到目标节点到目标节点(2,2)及及(3,3)的任何一条路径都是问题的一个解。的任何一条路径都是问题的一个解。其中，最短的路径长度是其中，最短的路径长度是3，它由，它由3个操作组成。例如，从个操作组成。例如，从(1,1)开始，通过

16、使用开始，通过使用操作操作A(1,3)、B(1,2)及及A(3,2)，可到达，可到达(3,3)。A(1,2)B(1,3)A(2,3)(1,1)(3,1)(3,2)(2,1)(2,3)A(1,3)B(1,2)A(3,2)第十九页，编辑于星期六：十五点 四十三分。Searching:20例例 修道士修道士(Missionaries)和野人和野人(Cannibals)问题问题(简称简称M-C问题问题)设在河的一岸有三个野人、三个修道士和一条船，修道士想用设在河的一岸有三个野人、三个修道士和一条船，修道士想用这条船把所有的人运到河对岸，但受以下条件的约束：这条船把所有的人运到河对岸，但受以下条件的约束

17、：一是修道士和野人都会划船，但每次船上至多可载两个人；一是修道士和野人都会划船，但每次船上至多可载两个人；二是在河的任一岸，如果野人数目超过修道士数，修道士会被二是在河的任一岸，如果野人数目超过修道士数，修道士会被 野人吃掉。野人吃掉。如果野人会服从任何一次过河安排，请规划一个确保修道士和如果野人会服从任何一次过河安排，请规划一个确保修道士和野人都能过河，且没有修道士被野人吃掉的安全过河计划。野人都能过河，且没有修道士被野人吃掉的安全过河计划。第二十页，编辑于星期六：十五点 四十三分。Searching:21 解：解：首先选取描述问题状态的方法。在这个问题中，需要考虑两岸的修道士首先选取描述问

18、题状态的方法。在这个问题中，需要考虑两岸的修道士人数和野人数，还需要考虑船在左岸还是在右岸。从而可用一个三元组来表人数和野人数，还需要考虑船在左岸还是在右岸。从而可用一个三元组来表示状态示状态 S=(m,c,b)其中，其中，m表示左岸的修道士人数，表示左岸的修道士人数，c表示左岸的野人数，表示左岸的野人数，b表示左岸的船数。表示左岸的船数。右岸的状态可由下式确定：右岸的状态可由下式确定：右岸修道士数右岸修道士数 m=3-m 右岸野人数右岸野人数 c=3-c 右岸船数右岸船数 b=1-b 在这种表示方式下，在这种表示方式下，m和和c都可取都可取0、1、2、3中之一，中之一，b可取可取0和和1中中

19、之一。因此，共有之一。因此，共有442=32种状态。种状态。第二十一页，编辑于星期六：十五点 四十三分。Searching:22这这32种状态并非全有意义，除去不合法状态和修道士被野人吃种状态并非全有意义，除去不合法状态和修道士被野人吃掉的状态，掉的状态，有意义的状态只有有意义的状态只有16种：种：S0=(3,3,1)S1=(3,2,1)S2=(3,1,1)S3=(2,2,1)S4=(1,1,1)S5=(0,3,1)S6=(0,2,1)S7=(0,1,1)S8=(3,2,0)S9=(3,1,0)S10=(3,0,0)S11=(2,2,0)S12=(1,1,0)S13=(0,2,0)S14=(0

20、,1,0)S15=(0,0,0)第二十二页，编辑于星期六：十五点 四十三分。Searching:23操作操作是指用船把修道士或野人从河的左岸运到右岸，或从河的是指用船把修道士或野人从河的左岸运到右岸，或从河的 右岸运到左岸。右岸运到左岸。每个操作都应当满足如下条件：每个操作都应当满足如下条件：一是一是船至少有一个人（船至少有一个人（m或或c）操作，离开岸边的）操作，离开岸边的m和和c的减少的减少 数目应该等于到达岸边的数目应该等于到达岸边的m和和c的增加数目；的增加数目；二是二是每次操作船上人数不得超过每次操作船上人数不得超过2个；个；三是三是操作应保证不产生非法状态。操作应保证不产生非法状态

21、。第二十三页，编辑于星期六：十五点 四十三分。Searching:24操作的表示：操作的表示：用符号用符号Pij表示从左岸到右岸的运人操作表示从左岸到右岸的运人操作 用符号用符号Qij表示从右岸到左岸的操作表示从右岸到左岸的操作其中：其中：i表示表示船上的修道士人数船上的修道士人数 j表示表示船上的野人数船上的野人数操作集操作集 本问题有本问题有10种操作可供选择：种操作可供选择：F=P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20第二十四页，编辑于星期六：十五点 四十三分。Searching:25 至此，该问题的状态空间至此，该问题的状态空间(S,F,G)构造完

22、成，这就完成了对构造完成，这就完成了对问题的状态空间表示。问题的状态空间表示。为了求解该问题，根据该状态空间的为了求解该问题，根据该状态空间的16种可能达到的合法种可能达到的合法状态和状态和10种算符，构造状态转换图。种算符，构造状态转换图。第二十五页，编辑于星期六：十五点 四十三分。Searching:26用状态空间表示用状态空间表示,首先必须定义状态的描述形式首先必须定义状态的描述形式,把问题的把问题的一切状态都表示出来一切状态都表示出来,其次定义算符其次定义算符,完成状态的转换完成状态的转换问题的求解过程就是一个把算符不断地作用于状态的过程问题的求解过程就是一个把算符不断地作用于状态的过

23、程.如果在使用某个算符后得到的状态就是目标状态如果在使用某个算符后得到的状态就是目标状态,就得到了就得到了问题的解问题的解.这个解就是从初始状态到目标状态所用算符构成这个解就是从初始状态到目标状态所用算符构成的序列的序列.第二十六页，编辑于星期六：十五点 四十三分。Searching:27算符的一次使用算符的一次使用,就使问题由一种状态转变为另一种状态就使问题由一种状态转变为另一种状态.可能可能有多个算符序列都可使问题从初始状态变到目标状态有多个算符序列都可使问题从初始状态变到目标状态,这就得这就得到了多个解到了多个解.对任何一个状态对任何一个状态,可使用的算符可能不止一个可使用的算符可能不止

24、一个,这样由一个状态这样由一个状态所生成的后继状态可能有多个所生成的后继状态可能有多个.如何选择下一步的操作如何选择下一步的操作,由搜由搜索策略决定索策略决定.第二十七页，编辑于星期六：十五点 四十三分。Searching:28搜索策略搜索策略搜索的基本概念搜索的基本概念状态空间的盲目搜索状态空间的盲目搜索状态空间的启发式搜索状态空间的启发式搜索第二十八页，编辑于星期六：十五点 四十三分。Searching:29状态空间的盲目搜索状态空间的盲目搜索一般图搜索过程一般图搜索过程广度优先和深度优先搜索广度优先和深度优先搜索代价树搜索代价树搜索第二十九页，编辑于星期六：十五点 四十三分。Search

25、ing:30 状态空间搜索的基本思想状态空间搜索的基本思想 先把问题的初始状态作为当前扩展节点对其进行扩展，生先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。节点中。若出现，则搜索成功，找到了问题的解；若没出现，则再若出现，则搜索成功，找到了问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中选择一个节点作为当按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点。前扩展节点。重复上述过程，直到目标状态出现在子节点中或者没有重复上述过程，直到目标状态出现在子节点中或者

26、没有可供操作的节点为止。所谓对一个节点进行可供操作的节点为止。所谓对一个节点进行“扩展扩展”是指对是指对该节点用某个可用操作进行作用，生成该节点的一组子节点。该节点用某个可用操作进行作用，生成该节点的一组子节点。第三十页，编辑于星期六：十五点 四十三分。Searching:31算法的数据结构和符号约定算法的数据结构和符号约定 Open表：用于存放刚生成的节点表：用于存放刚生成的节点 Closed表：用于存放已经扩展或将要扩展的节点表：用于存放已经扩展或将要扩展的节点 S0：用表示问题的初始状态：用表示问题的初始状态 G：表示搜索过程所得到的搜索图：表示搜索过程所得到的搜索图 M：表示当前扩展节

27、点新生成的且不为自己先辈的子节点集。：表示当前扩展节点新生成的且不为自己先辈的子节点集。第三十一页，编辑于星期六：十五点 四十三分。Searching:32如何度量问题求解的性能如何度量问题求解的性能一般搜索策略可以通过下面四个准则来评价：一般搜索策略可以通过下面四个准则来评价：完备性：如果存在一个解答，该策略是否保证能够找到？完备性：如果存在一个解答，该策略是否保证能够找到？时间复杂性：需要多长时间可以找到解答？时间复杂性：需要多长时间可以找到解答？空间复杂性：执行搜索需要多少存储空间？空间复杂性：执行搜索需要多少存储空间？最优性：如果存在不同的几个解答，该策略是否可以发现最高最优性：如果存

28、在不同的几个解答，该策略是否可以发现最高质量的解答？质量的解答？第三十二页，编辑于星期六：十五点 四十三分。Searching:33如何度量问题求解的性能如何度量问题求解的性能搜索策略反映了状态空间或问题空间扩展的方法，也决定了搜索策略反映了状态空间或问题空间扩展的方法，也决定了 状态或问题的访问顺序。状态或问题的访问顺序。在在AI领域，状态空间图由初始状态和算子隐含地表示，经常是领域，状态空间图由初始状态和算子隐含地表示，经常是无限的，它的复杂度根据下面三个值来表达：无限的，它的复杂度根据下面三个值来表达：分支因子分支因子b：任何节点的后继的最大个数：任何节点的后继的最大个数 最浅的目标节点

29、的深度最浅的目标节点的深度d 状态空间中任何路径的最大长度状态空间中任何路径的最大长度m第三十三页，编辑于星期六：十五点 四十三分。Searching:34状态空间搜索过程要点状态空间搜索过程要点p求解一个能够满足目标条件的问题可以表达为搜索一个图求解一个能够满足目标条件的问题可以表达为搜索一个图以找到一个满足目标状态描述的节点问题。以找到一个满足目标状态描述的节点问题。p搜索过程的要点如下搜索过程的要点如下:起始节点起始节点:对应于初始状态描述对应于初始状态描述后继节点后继节点:把适用于某个节点状态描述的一些算符用来推把适用于某个节点状态描述的一些算符用来推算该节点而得到的新节点算该节点而得

30、到的新节点,称为该节点的后继节点称为该节点的后继节点指针指针:从每个后继节点返回指向其父辈节点从每个后继节点返回指向其父辈节点检查各后继节点看是否为目标节点检查各后继节点看是否为目标节点.第三十四页，编辑于星期六：十五点 四十三分。Searching:35p状态空间搜索过程要点状态空间搜索过程要点搜索过程扩展后继节点的次序搜索过程扩展后继节点的次序如果搜索是以接近起始节点的程度如果搜索是以接近起始节点的程度(由节点之间连结弧线的由节点之间连结弧线的数目来衡量数目来衡量)依次扩展节点依次扩展节点,称为广称为广(宽宽)度优先搜索度优先搜索如果搜索时首先扩展最新产生的节点如果搜索时首先扩展最新产生的

31、节点,称为深度优先搜索称为深度优先搜索第三十五页，编辑于星期六：十五点 四十三分。Searching:36p状态空间搜索过程要点状态空间搜索过程要点调整指针调整指针扩展一个节点扩展一个节点生成出该节点的所有后继节点。生成出该节点的所有后继节点。弧的费用弧的费用有一条弧连接有一条弧连接ni和和nj两个节点两个节点,用用C(ni,nj)表示从表示从ni到到nj的费的费用用(耗散值耗散值)。路径的耗散值路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用值的总和。用C(ni,nj)表示从表示从ni到到nj的路径的耗散值。的路径的耗散

32、值。第三十六页，编辑于星期六：十五点 四十三分。Searching:37状态空间的一般搜索过程状态空间的一般搜索过程主要数据结构主要数据结构OPEN表表:存放刚生成的节点存放刚生成的节点,是还未扩展的节点是还未扩展的节点.一般是端节一般是端节点点.CLOSED表表:存放将要扩展或已扩展的节点存放将要扩展或已扩展的节点.或者是已被扩展但还或者是已被扩展但还没有在搜索树中生成后继节点的端节点没有在搜索树中生成后继节点的端节点,或者是非端节点或者是非端节点第三十七页，编辑于星期六：十五点 四十三分。Searching:38一般图搜索过程一般图搜索过程(1)把初始节点把初始节点S0放入放入OPEN表表

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

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

35、步第三十八页，编辑于星期六：十五点 四十三分。Searching:39算法算法说明明 (1)上述上述过程是状程是状态空空间的一般的一般图搜索算法，它具有通用性，搜索算法，它具有通用性，后面所要后面所要讨论的各种状的各种状态空空间搜索策略都是上述搜索策略都是上述过程的一个程的一个特例。各种搜索策略的主要区特例。各种搜索策略的主要区别在于在于对Open表中表中节点的排列点的排列顺序不同。例如，广度序不同。例如，广度优先搜索把先生成的子先搜索把先生成的子节点排在前面，点排在前面，而深度而深度优先搜索先搜索则把后生成的子把后生成的子节点排在前面。点排在前面。第三十九页，编辑于星期六：十五点 四十三分。

36、Searching:40算法算法说明明 对节点对节点n扩展后，生成并记入扩展后，生成并记入M的子节点有以下三种情况：的子节点有以下三种情况：该子节点来从未被任何节点生成过，由该子节点来从未被任何节点生成过，由n第一次生成；第一次生成；该子节点原来被其他节点生成过，但还没有被扩展，这一次又被该子节点原来被其他节点生成过，但还没有被扩展，这一次又被n再次生成；再次生成；该子节点原来被其他节点生成过，并且已经被扩展过，这一次又被该子节点原来被其他节点生成过，并且已经被扩展过，这一次又被n再次生成。再次生成。上三种情况是对一般图搜索算法而言。对于状态空间是树状结构不会出现后两上三种情况是对一般图搜索算

37、法而言。对于状态空间是树状结构不会出现后两种情况，这是因为每个节点经扩展后生成的子节点都是第一次出现的种情况，这是因为每个节点经扩展后生成的子节点都是第一次出现的 节点，不必检查并修改指向父节点的指针。节点，不必检查并修改指向父节点的指针。第四十页，编辑于星期六：十五点 四十三分。Searching:41在第在第(6)步针对步针对M中子节点的不同情况进行处理时，如果发生中子节点的不同情况进行处理时，如果发生当第当第种情况，那么，这个种情况，那么，这个M中的节点究竟应该作为哪一个节中的节点究竟应该作为哪一个节点的后继节点？点的后继节点？一般是由原始节点到该节点路径上所付出的代价来决定的，哪一般是

38、由原始节点到该节点路径上所付出的代价来决定的，哪一条路经付出的代价小，相应的节点就作为它的父节点。一条路经付出的代价小，相应的节点就作为它的父节点。原始节点到该节点路径上的代价是指这条路经上的所有有向边原始节点到该节点路径上的代价是指这条路经上的所有有向边的代价之和。的代价之和。如果发生第如果发生第种情况，除了需要确定该子节点指向父节点的指种情况，除了需要确定该子节点指向父节点的指针外，还需要确定其后继节点指向父节点的指针。其依据也针外，还需要确定其后继节点指向父节点的指针。其依据也是由原始节点到该节点的路径上的代价。是由原始节点到该节点的路径上的代价。第四十一页，编辑于星期六：十五点 四十三

39、分。Searching:42 在搜索图中，除初始节点外，任意一个节点都含有且只含有一在搜索图中，除初始节点外，任意一个节点都含有且只含有一个指向其父节点的指针。因此，由所有节点及其指向父节点个指向其父节点的指针。因此，由所有节点及其指向父节点的指针所构成的集合是一棵树，称为搜索树。的指针所构成的集合是一棵树，称为搜索树。第四十二页，编辑于星期六：十五点 四十三分。Searching:43在搜索过程的第在搜索过程的第(4)步，一旦某个被考察的节点是目标节点，步，一旦某个被考察的节点是目标节点，则搜索过程成功结束。由初始节点到目标节点路径上的所有则搜索过程成功结束。由初始节点到目标节点路径上的所有

40、操作就构成了该问题的解，而路径由第操作就构成了该问题的解，而路径由第(6)步所形成的指向父步所形成的指向父节点的指针来确定。节点的指针来确定。如果搜索过程终止在第如果搜索过程终止在第(2)步，即没有达到目标，且步，即没有达到目标，且Open表中表中已无可供扩展的节点，则失败结束。已无可供扩展的节点，则失败结束。第四十三页，编辑于星期六：十五点 四十三分。Searching:44例子例子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 第四十四页，编辑于星期

41、六：十五点 四十三分。Searching:452S13451,2,3 S 3,1,2 S OPENCLOSES 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 第四十五页，编辑于星期六：十五点 四十三分。Searching:462S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 676,7,5,1

42、,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 14OPEN表中的节点修改指针第四十六页，编辑于星期六：十五点 四十三分。Searching:472S131,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,12 14

43、13,10,11,9,7,5 S,3,4,6,8,1,12,2 第四十七页，编辑于星期六：十五点 四十三分。Searching:482S131,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,12 1413,10,11,9,7,5 S,3,4,6,8,1,12,2 CLOSE表中的节点修改指针第四十八页，编辑于星期六：十五点 四十三分。Searching:49

44、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,12 1413,10,11,9,7,5 S,3,4,6,8,1,12,2 CLOSE表中的节点(8)的后裔(10)修改指针第四十九页，编辑于星期六：十五点 四十三分。Searching:50q这是一个通用的搜索过程这是一个通用的搜索过程,后面讨论的状态空间各种搜索策后面讨论的状态空间各种搜索策略都是其

45、特例略都是其特例.各种搜索策略的主要区别就是对各种搜索策略的主要区别就是对OPEN表中节表中节点排序准则不同点排序准则不同q算法结束后，将生成一个图算法结束后，将生成一个图G，称为称为搜索图。同时由于每个。同时由于每个节点都有一个指针指向父节点，这些指针指向的节点构成节点都有一个指针指向父节点，这些指针指向的节点构成G的一个支撑树，称为的一个支撑树，称为搜索树。q从目标节点开始，将指针指向的状态回串起来，即找到一条从目标节点开始，将指针指向的状态回串起来，即找到一条解路径.第五十页，编辑于星期六：十五点 四十三分。Searching:51盲目搜索盲目搜索盲目盲目 搜索策略只使用问题定义中的信息

46、搜索策略只使用问题定义中的信息宽度优先搜索宽度优先搜索代价一致搜索代价一致搜索深度优先搜索深度优先搜索深度有限搜索深度有限搜索迭代加深搜索迭代加深搜索第五十一页，编辑于星期六：十五点 四十三分。Searching:52广度优先搜索广度优先搜索基本思想基本思想 从初始节点从初始节点S0开始逐层向下扩展，在第开始逐层向下扩展，在第n层节点还没有全部层节点还没有全部搜索完之前，不进入第搜索完之前，不进入第n+1层节点的搜索。层节点的搜索。Open表中的节点表中的节点总是按进入的先后排序，先进入的节点排在前面，后进入的总是按进入的先后排序，先进入的节点排在前面，后进入的节点排在后面。节点排在后面。第五

47、十二页，编辑于星期六：十五点 四十三分。Searching:53广度优先搜索广度优先搜索搜索算法搜索算法:(1)把初始把初始节点点S0放入放入Open表中；表中；(2)如果如果Open表表为空，空，则问题无解，失无解，失败退出；退出；(3)把把Open表的第一个表的第一个节点取出放入点取出放入Closed表，并表，并记该节点点为n；(4)考察考察节点点n是否是否为目目标节点。若是，点。若是，则得到得到问题的解，成的解，成功退出；功退出；(5)若若节点点n不可不可扩展，展，则转第第(2)步；步；(6)扩展展节点点n，将其子，将其子节点放入点放入Open表的尾部，并表的尾部，并为每一个每一个子子节

48、点点设置指向父置指向父节点的指点的指针，然后，然后转第第(2)步。步。第五十三页，编辑于星期六：十五点 四十三分。Searching:54例例 八数码难题。在八数码难题。在33的方格棋盘上，分别放置了表有数字的方格棋盘上，分别放置了表有数字1、2、3、4、5、6、7、8的八张牌，初始状态的八张牌，初始状态S0，目标状态，目标状态Sg，如下图所示。可以使用的操作有，如下图所示。可以使用的操作有 空格左移，空格上移，空格右移，空格下移空格左移，空格上移，空格右移，空格下移即只允许把位于空格左、上、右、下方的牌移入空格。要求应即只允许把位于空格左、上、右、下方的牌移入空格。要求应用广度优先搜索策略寻

49、找从初始状态到目标状态的解路径用广度优先搜索策略寻找从初始状态到目标状态的解路径2 331 8 447 6 5 1 2 38 47 6 5 S0 Sg第五十四页，编辑于星期六：十五点 四十三分。Searching:5523184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标8234187654第五十五页，编辑于星期六：十五点 四十三分。Searching:56广度优先搜索广度优先搜

50、索Complete Yes(如果如果 b 是有限的是有限的)Time 1+b+b2+b3+bd+b(bd-1)=O(bd+1)Space O(bd+1)Optimal Yes(如果每步代价为如果每步代价为1)分支因子分支因子b：任何节点的后继的最大个数：任何节点的后继的最大个数 最浅的目标节点的深度最浅的目标节点的深度d 状态空间中任何路径的最大长度状态空间中任何路径的最大长度m空间空间是大问题是大问题(和时间相比和时间相比)特点特点缺点缺点当目标节点距离初始节点较远时会产生许多无用的节点当目标节点距离初始节点较远时会产生许多无用的节点,搜索效率低搜索效率低优点优点只要问题有解只要问题有解,则