人工智能及其应用 教学课件 ppt 作者 李长河 第6章搜索

《人工智能及其应用 教学课件 ppt 作者 李长河 第6章搜索》由会员分享，可在线阅读，更多相关《人工智能及其应用 教学课件 ppt 作者 李长河 第6章搜索（138页珍藏版）》请在金锄头文库上搜索。

1、2019/5/20,第6章 搜 索 李长河主编,1,第6章 搜 索,2019/5/20,第6章 搜 索 李长河主编,2,第6章 搜 索,6.1 什么是搜索? 6.2 状态空间表示法 6.3 状态空间的基本搜索策略 6.4 启发式搜索策略 6.5 启发式搜索法 6.6 与/或树的启发式搜索 6.7 博弈对策（Game of Chess Strategy）,学海无涯,2019/5/20,第6章 搜 索 李长河主编,3,6.1 概述,搜索（Search），即寻找，设法在庞大状态空间图中找到目标。也可以把搜索看作是一种推理，它是人工智能问题求解的基本方法之一。 主要分为两类性质的搜索：即基本搜索和智能

2、搜索。 基本搜索是一种没有任何经验和知识起作用的、由某种规则所确定的非智能性的搜索； 启发式搜索（Heuristic Search）：其特点在于是一种有准备的、追求效率而有的放矢的智能搜索，它要求依据某种知识及信息的指导，通过逐一状态比较而找到符合规定条件的目标状态解。,6.1.1 什么是搜索?,2019/5/20,第6章 搜 索 李长河主编,4,6.1.1 什么是搜索？,可把问题世界的全部信息空间划分为三类： （1）全信息环境Ee； （2）部分已知信息环境Ep； （3）未知信息环境En,2019/5/20,第6章 搜 索 李长河主编,5,6.1.1 什么是搜索？,（1）全信息环境Ee。已知与

3、问题的解有关的全部信息，其搜索的目标和任务是：运用知识和经验，设法找到最佳路径，以便取得理想搜索效果。例如，在国际象棋博奕中，选择最优算法来克敌制胜。,6.1.1 什么是搜索？,（2）部分已知信息环境Ep。当只有部分信息已知，这时，其目标和任务是：充分利用已知信息，把未知的信息不利影响设法降到最低程度，尽可能按照最佳搜索路径取得理想搜索效果。或者设法弥补信息损失，发挥已知信息作用，扬长避短，制定策略来克敌制胜。例如，在海陆空战棋或军棋游戏中，运用知识和经验猜测对方的军事布局，一方面用手榴弹对付比我方师长还要厉害的指挥官，另一方面要设法用最小代价摧毁对方强大火力，以便开辟夺取对方军旗的坦途。,2

4、019/5/20,第6章 搜 索 李长河主编,7,6.1.1 什么是搜索？,（3）未知信息环境En。 对于未知信息环境的问题求解，首先要设法变En为部分已知信息环境Ep来解决。例如，为了探测海洋、极地、外星球的奥秘，就需要实地探险或发射相应的探测器，以便取得必要的信息与知识；当进入陌生的地带作战时，需要派出侦察小分队了解地形地物和侦察敌人火力部署，或用侦察卫星探测敌情等。,2019/5/20,第6章 搜 索 李长河主编,8,6.1.2 问题的状态空间图搜索,问题的状态空间可用有向图来表达，如图6-2所示，又常称其为状态树(State Tree)。图中，节点Sk表示状态，状态之间的连接采用有向弧

5、(Arc)，弧上标以操作数OK来表示状态之间的转换关系。 用状态空间法搜索求解问题: 首先要把待求解的问题表示为状态空间图;把问题的解表示为目标节点Sg。 求解就是要找到从根节点S0到达目标节点Sg的搜索路径。,2019/5/20,第6章 搜 索 李长河主编,9,6.1.2 问题的状态空间图搜索,状态空间图在计算机中有两种存储方式：一种是图的显式存储，另一种是图的隐式存储。 图的显式存储: （1）概念：所谓图的显式存储，即把问题的全部状态空间图直接都存于计算机中的方式。诸如一般计算机文件、程序文件和库文件的存储等，均为图的显式存储方式。 （2）适用条件：通常图的显式存储方式需要占据计算机的大量

6、存储空间和处理时间，故这种存储方式仅适用于状态空间十分有限以及较简单的问题求解。 （3）特点：其优点是直观、明了，但缺点是占据存储空间大。,2019/5/20,第6章 搜 索 李长河主编,10,6.1.2 问题的状态空间图搜索,图的隐式存储: （1）概念：仅在计算机中存储关于要求解问题的相关各种知识,只在必要时再由相关的信息和知识逐步生成状态空间图的方式称为图的隐式存储。 （2）适用条件：适用于一般问题求解，尤其适宜于状态空间庞大的情况。 （3）特点：占据空间小，但不够直观，与图的显式存储刚好特点互补。 例如，针对问题的状态空间十分庞大的情况，人们可采用图的隐式存储：即只需要存入问题的参数、参

7、数数值表和计算公式等，仅在问题求解中，按照推理或搜索过程的需要，进行参数和参数值的代换与公式计算，再求得状态空间各点的数值。通过数值的比较与搜索，最后再完成问题的求解,2019/5/20,第6章 搜 索 李长河主编,11,6.1.2 问题的状态空间图搜索,隐式图的搜索过程: （1）概念：根据机器中所存储的待求解问题的相关知识，逐步产生问题的状态空间图并检查解是否在其中的过程，叫做隐式图的搜索过程。 （2）隐式图的搜索过程与步骤： 搜索之先，必须配置一个发生器函数Q(x)，用以描述状态操作；还需要配置一个估计函数f(x)，用以比较和评估搜索步骤中产生的耗费代价。,2019/5/20,第6章 搜

8、索 李长河主编,12,6.1.2 问题的状态空间图搜索,隐式图的搜索过程: 步1.按照问题的已知条件，产生一个初始状态So的有限描述，并依照一定的数据结构形式存于计算机中； 步2.用发生器函数Q(x)作用于So并扩展生成So的子节点Si , 逐一比较目标节点Sg是否在Si中出现，若出现则搜索成功。 步3.若没有出现Sg，就用估计函数f(x)对所有这些刚生成的子节点Si进行价值评估，在适当范围内选择最有希望的结点Sk替代So，返回步2对Sk进行扩展生成。当所有可扩展的节点均已用Q(x)生成，仍无Sg出现，则搜索失败。 可逐层按照f(x)选择子节点并返回步2、步3反复进行扩展生成，比较目标，价值评

9、估等操作，直到找到目标节点Sg为止。,2019/5/20,第6章 搜 索 李长河主编,13,6.1.2 搜索过程完备性概念,一般来说，对于任何一个可解的树状问题，至少对应就能找到一个使用搜索的求解过程。倘若问题有解，运用某一搜索过程就一定能求得该问题的解，则称此问题的搜索过程是完备的；而对于有解而找不到解的过程，则称其是不完备的。但是，这里应该加以区分的概念是：对于本来就不可解的问题，即便使用完备的搜索过程，也自然找不到解。 只有完备的搜索过程才可称其为“搜索算法”，简称为“算法”；不完备的搜索过程一般不能称为算法，但可以简称其为“过程”。当然，有一些不完备的搜索过程可以通过必要的改造，使它们

10、成为有较高效率的完备搜索过程，并可称其为搜索算法。,2019/5/20,第6章 搜 索 李长河主编,14,6.2 状态空间表示法,状态空间表示法是人工智能最基本的知识表示方法之一。 状态：描述某一类事物在不同时刻所处于的信息状况。可用一组变量的有序组合来表示为如下形式： Sk= x0,x1, x2, x3,T （6-1） 其中的每个元素xI(i=0,1,2)称为分量，相应的变量值域为ai,bi。给定每个分量的值，就得到了一个具体的状态。状态的维数可以任意，一般为有限值。,6.2.1 状态、操作和状态空间,2019/5/20,第6章 搜 索 李长河主编,15,6.2 状态空间表示法,操作：描述了

11、状态之间的关系。它可以是一个行为步骤，也可以是一个改变过程、规则或操作数。使状态中的某些分量发生改变，就将使问题由一个具体状态变化到了另一个具体状态。 问题的状态空间可用一个三元序组来表示： S，F，G （6-2） S是初始状态集；F是操作的集合；而G为目标状态集。,6.2.1 状态、操作和状态空间,2019/5/20,第6章 搜 索 李长河主编,16,6.2 状态空间表示法,问题的求解就转化为从状态空间图的初始状态S0出发，搜索寻取目标状态Sg的路径问题。搜索过程所得到的操作序列就反映了问题的解路径。故搜索求解的过程可简洁地表示为： Sg=fn(（f2(f1(S0)）) （6-3） 式中，f

12、i表示对其右边的当前状态将进行第i个操作。 对一个智能问题全部状态及其操作关系，给予具体的赋值，就可构成一个状态空间的相互关系有向图，使用该图，即可进行具体问题求解。,6.2.1 状态、操作和状态空间,2019/5/20,第6章 搜 索 李长河主编,17,6.2 状态空间表示法,例6-1设有分别由开关控制的一字排开的3盏信号灯，处在“亮、暗、亮”的初始状态。每次操作允许并必须扳动一只开关，问：如果连扳三次开关后，是否可以出现错“亮、亮、亮”或“暗、暗、暗”的状态？ 解:首先将该问题形式化：设开关“off”灯为“暗”，以0表示；开关“on”灯为“亮”，以1表示；再分别用A、B、C标识3盏灯亮或暗

13、的状态。这样，可引入一三元数组Sk=（A,B,C）来描述这3盏信号灯的总状态。全部可能的状态计有8种： S0 =（0,0,0）, S1 =（0,0,1）,S2 =（0,1,0）, S3 =（0,1,1）, S4 =（1,0,0）, S5 =（1,0,1）,S6 =（1,1,0）, S7=（1,1,1）.,6.2.2 使用状态空间图搜索的问题求解,2019/5/20,第6章 搜 索 李长河主编,18,6.2 状态空间表示法,这里，初始状态一个： S =S5=（1,0,1）； 目标状态有2个： G =S0，S7=（0,0,0），（1,1,1） 状态的操作数，共3个，F =a,b,c,分别表示把各灯

14、开关扳动一次 ； 问题的状态空间可写成S5,a,b,c,S0，S7.,6.2.2 使用状态空间图搜索的问题求解,三盏信号灯问题的状态空间图,2019/5/20,第6章 搜 索 李长河主编,19,6.2 状态空间表示法,教材中图6-3表示了全部可能的状态及其相互关系。 其中S5是初始状态，S0和S7都是目标状态。从图中我们可以清楚地看出：从S5经过三步搜索不可能恰好到达S0，即不存在从S5到达S0的解；但从S5出发搜索，到达S7的路径有7条，它们的动作序列分别为aab、aba、baa、bbb、bcc、cbc和ccb等，共有七组解。,6.2.2 使用状态空间图搜索的问题求解,2019/5/20,第

15、6章 搜 索 李长河主编,20,6.2 状态空间表示法,由上述利用状态空间图求解的举例，对具体问题搜索求解可总结为如下的思路和步骤： （1）设定状态变量及确定值域； （2）确定状态组，分别列出初始状态集和目标状态集； （3）定义并确定操作集； （4）估计全部状态空间数，并尽可能列出全部状态空间或予以描述之； （5）当状态数量不是很大时，按问题的有序元组画出状态空间图，依照状态空间图搜索求解。,6.2.2 使用状态空间图搜索的问题求解,2019/5/20,第6章 搜 索 李长河主编,21,6.2 状态空间表示法,例6-2 传教士和野人问题（The Missionaries and Canniba

16、ls Problem）。在河的左岸有三个传教士、一条船和三个野人，传教士们想用这条船将所有的成员都运过河去，但是受到以下条件的限制：传教士和野人都会划船，但船一次最多只能装运两个；在任何岸边野人数目都不得超过传教士，否则传教士就会遭遇危险：被野人攻击甚至被吃掉。此外，假定野人会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。,6.2.3 用状态空间法求解传教士和食人者问题,2019/5/20,第6章 搜 索 李长河主编,22,6.2 状态空间表示法,解：我们按上述步骤来进行求解分析。 （1）设定状态变量及确定值域。 为了建立这个问题的状态空间，设左岸传教士数为m，则 m =0,1,2,3； 对应右岸的传教士数为3m； 左岸的野人数为c，则有 c =0,1,2,3； 对应右岸野人数为3c；左岸船数为b，故又有b=0,1，右岸的船数为1b.,6.2.3 用状态空间法求解传教士和食人者问题,2019/5/2