搜索策略搜索是人工智能中的一个基本问题是推理课件

《搜索策略搜索是人工智能中的一个基本问题是推理课件》由会员分享，可在线阅读，更多相关《搜索策略搜索是人工智能中的一个基本问题是推理课件（22页珍藏版）》请在金锄头文库上搜索。

1、第六章 搜索策略 搜索是人工智能中的一个基本问题，是推理不可分割的一部分，它直接关 系到智能系统的性能与运行效率，因而尼尔逊把它列为人工智能研究中的四个 核心问题之一。 5.1 基本概念 1. 什么是搜索 人工智能所要解决的大部分问题是结构不良或非结构化的问题，对这样的 问题一般不存在成熟的求解算法可供利用，而只能是利用已有的知识一步步 摸索着前进。 在此过程中，存在着如何寻找可用知识的问题，即如何确定推理路线，使其付出的代价尽可能的少，而问题又能得到较好的解决。 如：在正向推理中， 对已知的初始事实，需要在知识库中寻找可使用的知识，这就 存在按何种线路进行寻找的问题。, 另外，可能存在多条线

2、路都可实现对问题的求解，这就又出现 按哪一条线路进行求解以获得较高的运行效率的问题。 像这样根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称为搜索。 2. 搜索分类 搜索分为盲目搜索和启发式搜索。 盲目搜索按预定的控制策略进行搜索，在搜索过程中获得的中间信 息不用来改进控制策略。这种搜索具有盲目性，效率不高， 不便于复杂问题的求解。 启发式搜索在搜索中加入了与问题有关的启发性信息，用以指导搜 索朝着最有希望的方向前进，加速问题的求解过程并 找到最优解。,5.2 求解问题的表示方法 用搜索策略求解问题，首先要解决的问题也是：用什么样的形式把问题表

3、示出来. 一般来说，有两种方法： 状态空间表示法； 与/或树表示法； 1. 状态空间表示法 状态空间表示法是用来表示问题及其搜索过程的一种方法，它是人工智能中最 基本的形式化方法。 状态空间表示法是用“状态”和“算符”来表示问题的一种方法。其中， “状态”用以描述问题求解过程中不同时刻的状况； “算符”表示对状态的操作，算符的每一次使用就使问题由一种状态变换为 另一种状态; 解 当到达目标状态时，由初始状态到目标状态所用算符的序列就是问题 的一个解。,. 状态 状态是描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序组合表示： SK(SK0, SK1, ) 当给每一个分量以确定的值

4、时，就得到了一个具体的状态。 . 算符 引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算符。在产生式系统中，每一条产生式规则就是一个算符。 . 状态空间 由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，般用个三元组表示： (S，F，G) 其中, S是问题的所有初始状态构成的集合； F是算符的集合；G是目标状态的集合。 状态空间的图示形式称为状态空间图。其中，节点表示状态；有向边(弧)表示算符。,例1：钱币翻转问题，如图所示。设有三个钱币，起初是状态为（反正反）， 允许每次翻转一个钱币（只反一个，也必反一个），连反三次，问是否可达 到目标状态？（正正正）

5、或（反反反）？,设用 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翻一面；,上述问题的状态空间“三元组”为： （S5, f1,f2,f3, s0,s7） 相应的状态空间图：,从图中看出：从S5不可能经三次翻转到达

6、S0, 从S5 可经三次翻转到达S7 , 且有七种操作方式。,2. 与/或树表示法 与/或树是用于表示问题及其求解过程的又一种形式化方法，通常用于表示比较 复杂问题的求解。 对于一个复杂问题，直接求解往往比较困难。此时，可通过下述方法进行简化： (1)分解：“与”树 把一个复杂问题分解为若干个较为简单的子问题，然后对每个子问 题分别进行求解，最后把各子问题的解复合起来就得到了原问题的解。 这是“与”的问题。,P1, P2, P3 为子节点，子问题对应子节点。 P为“与”节点，只有当三个子问题都有解时，P才可解。 如图所示，称为“与”树。,(2) 等价变换：“或”树 利用等价变换，把它变换为若干

7、个较容易求解的新问题。 若新问题中有一个可求解，则就得到了原问题的解。 这是“或”的问题。 如图所示，称为“或”树。,与/或树： 将上述两种方法也可结合起来使用，此时的图称为“与/或树”，其中既有“与”节点，也 有“或”节点。在此统称为子节点。,(3) 几个基本概念： .本原问题 不能再分解或变换，而且直接可解的子问题称为本原问题。 .端节点与终止节点 在与/或树中，没有子节点的节点称为端节点；本原问题所对应的节点称为终止节点。 显然终止节点一定是端节点，但端节点不一定是终止节点。,. 可解节点 在与/或树中，满足下列条件之一者，称为可解节点： 它是一个终止节点。 它是一个“或”节点，且其子节

8、点中至少有一个是可解节点。 它是一个“与”节点，且其子节点全部是可解节点。 . 不可解节点 关于可解节点的三个条件全部不满足的节点称为不可解节点。 . 解树 由可解节点所构成，并且由这些可解节点可推出初始节点(它对应于原始问题)为可解 节点的子树称为解树。在解树中一定包含初始节点。 例如：t标出的节点是终止节点， 根据可解节点的定义， 原始问题P是可解的。,例：三阶汉诺塔问题。设有A，B，C三个金片以及三根钢针，三个金片按自上而下从小到大的顺序穿在1号钢针上，要求把它们全部移到3号钢针上，而且每次只能移动一个金片，任何时刻都不能把大的金片压在小的金片上面，如图所示。,首先进行问题分析： (1)

9、 为了把三个金片全部移到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 B C,A B C,为了用与/或树把问题的分解过程表示出来，先要定义问题的形式化表示方法。 设仍用状态表示问题在任一时刻的状况； 用三元组 (i，j，k) 表

10、示状态：i代表金片C所在的钢针号； j代表金片B所在的钢针号; k代表金片A所在的钢针号。 用“”表示状态的变换； 这样原始问题就可表示为： (1, 1, 1) (3，3，3) 用与/或树把分解过程表示出来。,若把这些本原问题的解按从左至右的顺序排列，就得到了原始问题的解： (1,1,1)(1,l,3)， (1,1,3)(1,2,3)， (1,2,3)(1,2,2)， (1,2,2)(3,2,2)， (3,2,2)(3,2,1)， (3,2,1)(3,3,1)， (3,3,1)(3,3,3) 它指出了移动金片的次序。,此图共有七个终止节点，对应于七个本原问题，它们是通过“分解”得到的。,5.3

11、 状态空间搜索策略 1. 概述 (1) 显式图与隐式图 为了求解问题，需要把知识存储在计算机的知识库中，有下列两种存储方式： 显式存储： 把与问题有关的全部状态空间图，即相应的全部知识（事实性知识、过程性知识，控制性知识）都直接存入知识库，称为“显式存储”或“显式图”。 隐式存储： 只存储与问题有关的部分知识，在求解过程中，又初始状态出发，运用相应的知识，逐步生成所需的部分状态空间图，通过搜索推理，找到所求目标。这样只需在知识库中存储局部状态空间图，称为“隐式图”。 通常，为了节约计算机的存储容量，提高搜索推理效率，采用隐式存储方法，进行隐士图搜索推理。,(2) 搜索方法 .运用事实性知识，给

12、出问题的部分状态描述，包括：初始状态S0，目标状态 Sg，和某些中间状态Sh； .运用过程性知识，给出由状态空间图“父节点”生成“子节点”的操作“算符”； .运用控制性知识（在此为搜索策略），选取适当的节点，控制继续搜索的方 向。 (3) 搜索过程 .给出初始状态（初始节点）； .选择选择适用的算符对其进行操作，生成一组子状态(或称后继状态、后继 节点、子节点)； .检查目标状态是否在其中出现。若出现，则搜索成功，找到了问题的解；若 不出现，则按某种搜索策略从已生成的状态中再选一个状态作为当前状态。 重复上述过程，直到目标状态出现或者不再有可供操作的状态及算符时为止。,(4) 搜索过程中要用到

13、的两个数据结构 OPEN表： 用于存放刚生成的节点。对于不同的搜索策略，节点在OPEN表中的排列顺序是不同的。 CLOSED表： 用于存放将要扩展或者已扩展的节点，所谓对节点进行“扩展”是指：用合适的算符对该节点进行操作，生成一组子节点。,OPEN表,CLOSED表,(5) 状态空间法搜索策略 广度优先搜索 深度优先搜索 有界深度优先搜索 代价树的广度优先搜索 代价树的深度优先搜索 （以上属于盲目搜索策略） 局部择优搜索 全局择优搜索 （以上搜索属于启发式搜索）,2. 广度优先搜索法（Breadth-First Search) (1) 基本思想 从初始节点开始，按照某种生成规则（算符）逐步生成

14、下一级各子节点，顺序（先生成的子节点优先检查，优先扩展）地检查是否出现目标节点，在该级全部节点中沿广度进行“横向”扫描，即：沿“广度”遍历所有节点，故称“广度优先搜索法”。 (2) 广度优先搜索法搜索过程 .把初始节点S0放人OPEN表，若S0为目标节点，则得到问题的解，退出； .如果OPEN表为空，则问题无解，退出； .把OPEN表的第一个节点(记为节点n)取出放入CLOSED表； .考察节点n，若节点n不可扩展，则转第步； .扩展节点n，将其子节点放入0PEN表的尾部，并为每一个子节点都配置指向父节点 的指针； .如果n的任一个后继节点是目标节点，则找到问题的解，成功退出，否则转向第步。,

15、OPEN表,CLOSED表,(a),(b),(c),(d),S0,S0,1,1,2,1,2,0,0,0,3,4,2,0,3,3,5,6,7,8,9,4,1,1,1,1,2,2,3,3,4,4,5,S0,1,0,2,0,3,1,4,1,Sg(9),例： 重排九宫问题。在3X3的方格棋盘上放置分别标有数字1，2，3，4，5，6， 7，8的八张牌，初始状态为50，目标状态为S，如下图所示。 可使用的算符有： 空格左移，空格上移，空格右移，空格下移 即，它们只允许把位于空格左，上，右，下边的牌移入空格。 要求寻找从初始状态到目标状态的路径。 应用广度优先搜索，可得到如图所示的搜索树。,由图可以看出，解的路径是: S03 8 16 26 (Sg) 小结： 缺点： 广度优先搜索的盲目性较大，当目标节点距离初始节点较远时将会产生许 多无用节点，搜索效率低，这是它的缺点。 优点： 只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的 解，这是它的优点。,3