《人工智能》.ppt

整理ppt1第六章第六章 搜索策略搜索策略 搜索是人工智能中的一个基本问题，是推理不可分割的一部分，它直接关搜索是人工智能中的一个基本问题，是推理不可分割的一部分，它直接关 系到智能系统的性能与运行效率，因而尼尔逊把它列为人工智能研究中的四个系到智能系统的性能与运行效率，因而尼尔逊把它列为人工智能研究中的四个 核心问题之一。核心问题之一。5.1 基本概念基本概念 1. 什么是搜索什么是搜索 人工智能所要解决的大部分问题是结构不良或非结构化的问题，对这样的人工智能所要解决的大部分问题是结构不良或非结构化的问题，对这样的 问题一般不存在成熟的求解算法可供利用，而只能是利用已有的知识一步步问题一般不存在成熟的求解算法可供利用，而只能是利用已有的知识一步步 摸索着前进。摸索着前进。 在此过程中，存在着如何寻找可用知识的问题，即如何确定推理路线，在此过程中，存在着如何寻找可用知识的问题，即如何确定推理路线，使其付出的代价尽可能的少，而问题又能得到较好的解决。使其付出的代价尽可能的少，而问题又能得到较好的解决。 如：在正向推理中，如：在正向推理中， 对已知的初始事实，需要在知识库中寻找可使用的知识，这就对已知的初始事实，需要在知识库中寻找可使用的知识，这就 存在按何种线路进行寻找的问题。存在按何种线路进行寻找的问题。整理ppt2 另外，可能存在多条线路都可实现对问题的求解，这就又出现另外，可能存在多条线路都可实现对问题的求解，这就又出现 按哪一条线路进行求解以获得较高的运行效率的问题。按哪一条线路进行求解以获得较高的运行效率的问题。 像这样根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少像这样根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称为搜索。的推理路线，使问题得到圆满解决的过程称为搜索。2. 搜索分类搜索分类 搜索分为盲目搜索和启发式搜索。搜索分为盲目搜索和启发式搜索。 盲目搜索盲目搜索按预定的控制策略进行搜索，在搜索过程中获得的中间信按预定的控制策略进行搜索，在搜索过程中获得的中间信 息不用来改进控制策略。这种搜索具有盲目性，效率不高，息不用来改进控制策略。这种搜索具有盲目性，效率不高， 不便于复杂问题的求解。不便于复杂问题的求解。 启发式搜索启发式搜索在搜索中加入了与问题有关的启发性信息，用以指导搜在搜索中加入了与问题有关的启发性信息，用以指导搜 索朝着最有希望的方向前进，加速问题的求解过程并索朝着最有希望的方向前进，加速问题的求解过程并 找到最优解。找到最优解。整理ppt35.2 求解问题的表示方法求解问题的表示方法 用搜索策略求解问题，首先要解决的问题也是：用搜索策略求解问题，首先要解决的问题也是：用什么样的形式把问题表示出来用什么样的形式把问题表示出来. 一般来说，有两种方法：一般来说，有两种方法： 1. 状态空间表示法状态空间表示法状态空间表示法是用来表示问题及其搜索过程的一种方法，它是人工智能中最状态空间表示法是用来表示问题及其搜索过程的一种方法，它是人工智能中最 基本的形式化方法。基本的形式化方法。 状态空间表示法是用状态空间表示法是用“状态状态”和和“算符算符”来表示问题的一种方法。其中，来表示问题的一种方法。其中， “状态状态”用以描述问题求解过程中不同时刻的状况；用以描述问题求解过程中不同时刻的状况； “算符算符”表示对状态的操作，算符的每一次使用就使问题由一种状态变换表示对状态的操作，算符的每一次使用就使问题由一种状态变换为为 另一种状态另一种状态; 解解 当到达目标状态时，由初始状态到目标状态所用算符的序列就是问题当到达目标状态时，由初始状态到目标状态所用算符的序列就是问题 的一个解。的一个解。整理ppt4 状态是描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序组合表示：状态是描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序组合表示： SK(SK0, SK1, ) 当给每一个分量以确定的值时，就得到了一个具体的状态当给每一个分量以确定的值时，就得到了一个具体的状态。 引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算符。引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算符。在产生式系统中，每一条产生式规则就是一个算符。在产生式系统中，每一条产生式规则就是一个算符。 由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，般用般用个三元个三元组表示：组表示： (S，F，G) 其中其中, S是问题的所有初始状态构成的集合；是问题的所有初始状态构成的集合； F是算符的集合；是算符的集合；G是目标状态的集合。是目标状态的集合。 状态空间的图示形式称为状态空间图。其中，节点表示状态；有向边状态空间的图示形式称为状态空间图。其中，节点表示状态；有向边(弧弧)表示算符。表示算符。整理ppt5例例1：钱币翻转问题，如图所示。设有三个钱币，起初是状态为（反正反），：钱币翻转问题，如图所示。设有三个钱币，起初是状态为（反正反）， 允许每次翻转一个钱币（只反一个，也必反一个），连反三次，问是否可达允许每次翻转一个钱币（只反一个，也必反一个），连反三次，问是否可达 到目标状态？（正正正）到目标状态？（正正正） 或（反反反）？或（反反反）？正正反反正正正正正正反反反反反反反反 设用设用 Sk=(s1,s2,s3) 表示问题的状态，表示问题的状态，s=0 表示钱币正面，表示钱币正面，s=1表示钱币反面。表示钱币反面。则钱币可能出现的状态有八种：则钱币可能出现的状态有八种： 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) 问题的初始状态集合问题的初始状态集合：S=S5 目标状态集合：目标状态集合：G=S0 , S7 算符：算符：f1 把把s1翻一面；翻一面； f2 把把s2翻一面；翻一面； f3 把把s3翻一面；翻一面；整理ppt6上述问题的状态空间上述问题的状态空间“三元组三元组”为：为： （S5, f1,f2,f3, s0,s7） 相应的状态空间图：相应的状态空间图：0 0 01 0 00 0 11 0 11 1 10 1 11 1 00 1 0S0S4S1S5S7S3S6S2从图中看出：从从图中看出：从S5不可能经三次翻转到达不可能经三次翻转到达S0, 从从S5 可经三次翻转到达可经三次翻转到达S7 , 且有七种操作方式。且有七种操作方式。f1f1f1f1f2f2f2f2f3f3f3f3整理ppt72. 与与/或树表示法或树表示法 与与/或树是用于表示问题及其求解过程的又一种形式化方法，通常用于表示比较或树是用于表示问题及其求解过程的又一种形式化方法，通常用于表示比较 复杂问题的求解。复杂问题的求解。 对于一个复杂问题，直接求解往往比较困难。此时，可通过下述方法进行简化：对于一个复杂问题，直接求解往往比较困难。此时，可通过下述方法进行简化：(1)分解：分解：“与与”树树 把一个复杂问题分解为若干个较为简单的子问题，然后对每个子问把一个复杂问题分解为若干个较为简单的子问题，然后对每个子问 题分别进行求解，最后把各子问题的解复合起来就得到了原问题的解。题分别进行求解，最后把各子问题的解复合起来就得到了原问题的解。 这是这是“与与”的问题。的问题。PP1P2P3P1, P2, P3 为子节点，子问题对应子节点。为子节点，子问题对应子节点。P为为“与与”节点，只有当三个子问题都有解时，节点，只有当三个子问题都有解时，P才可解。才可解。 如图所示，称为如图所示，称为“与与”树。树。(2) 等价变换：等价变换：“或或”树树 利用等价变换，把它变换为若干个较容易求解的新问题。利用等价变换，把它变换为若干个较容易求解的新问题。 若新问题中有一个可求解，则就得到了原问题的解。若新问题中有一个可求解，则就得到了原问题的解。 这是这是“或或”的问题。的问题。 如图所示，称为如图所示，称为“或或”树。树。PP1P2P3整理ppt8与与/或树：或树： 将上述两种方法也可结合起来使用，此时的图称为将上述两种方法也可结合起来使用，此时的图称为“与与/或树或树”，其中既有，其中既有“与与”节点，节点，也也 有有“或或”节点。在此统称为子节点。节点。在此统称为子节点。P1P11P12P3P31P32P33PP2(3) 几个基本概念：几个基本概念： 不能再分解或变换，而且直接可解的子问题称为本原问题。不能再分解或变换，而且直接可解的子问题称为本原问题。 在与在与/ /或树中，没有子节点的节点称为端节点；本原问题所对应的节点称为终止节点。或树中，没有子节点的节点称为端节点；本原问题所对应的节点称为终止节点。 显然终止节点一定是端节点，但端节点不一定是终止节点。显然终止节点一定是端节点，但端节点不一定是终止节点。整理ppt9 在与在与/ /或树中，满足下列条件之一者，称为可解节点：或树中，满足下列条件之一者，称为可解节点： 它是一个终止节点。它是一个终止节点。 它是一个它是一个“或或”节点，且其子节点中至少有一个是可解节点。节点，且其子节点中至少有一个是可解节点。 它是一个它是一个“与与”节点，且其子节点全部是可解节点。节点，且其子节点全部是可解节点。 关于可解节点的三个条件全部不满足的节点称为不可解节点。关于可解节点的三个条件全部不满足的节点称为不可解节点。 由可解节点所构成，并且由这些可解节点可推出初始节点由可解节点所构成，并且由这些可解节点可推出初始节点( (它对应于原始问题它对应于原始问题) )为可解为可解 节点的节点的子树子树称为解树。在解树中一定包含初始节点。称为解树。在解树中一定包含初始节点。 例如：例如：t t标出的节点是终止节点，标出的节点是终止节点， 根据可解节点的定义，根据可解节点的定义， 原始问题原始问题P P是可解的。是可解的。 t tP整理ppt10例：三阶汉诺塔问题。设有例：三阶汉诺塔问题。设有A，B，C三个金片以及三根钢针，三个金片按自上而三个金片以及三根钢针，三个金片按自上而下从小到大的顺序穿在下从小到大的顺序穿在1号钢针上，要求把它们全部移到号钢针上，要求把它们全部移到3号钢针上，而且每次号钢针上，而且每次只能移动一个金片，任何时刻都不能把大的金片压在小的金片上面，如图所示。只能移动一个金片，任何时刻都不能把大的金片压在小的金片上面，如图所示。首先进行问题分析：首先进行问题分析： (1) 为了把三个金片全部移到为了把三个金片全部移到3号针上，必须先把金片号针上，必须先把金片C移到移到3号针上。号针上。 (2) 为了移金片为了移金片C，必须先把金片必须先把金片A及及B移到移到2号针上。号针上。 (3) 当把金片当把金片c移到移到3号针上后，就可把号针上后，就可把A，B从从2号移到号移到3号针上，这样就可完成问题的求解。号针上，这样就可完成问题的求解。 由此分析，得到了原问题的三个子问题：由此分析，得到了原问题的三个子问题： (1)把金片把金片A及及B移到移到2号针的双金片问题。号针的双金片问题。 (2)把金片把金片C移到移到3号针的单金片问题。号针的单金片问题。 (3)把金片把金片A及及B移到移到3号针的双金片问题。号针的双金片问题。 其中，子问题其中，子问题(1)与子问题与子问题(3)又分别可分解为三个子问题。又分别可分解为三个子问题。 A BCA B C整理ppt11 设仍用状态表示问题在任一时刻的状况；设仍用状态表示问题在任一时刻的状况； 用三元组用三元组 (i，j，k) 表示状态：表示状态：i代表金片代表金片C所在的钢针号；所在的钢针号； j代表金片代表金片B所在的钢针号所在的钢针号; k代表金片代表金片A所在的钢针号。所在的钢针号。 用用“”表示状态的变换；表示状态的变