人工智能搜索策略幻灯片

《人工智能搜索策略幻灯片》由会员分享，可在线阅读，更多相关《人工智能搜索策略幻灯片（160页珍藏版）》请在金锄头文库上搜索。

1、第1-2章 搜索策略,基本概念 状态空间的搜索策略 A算法 与/或图的搜索策略 其它搜索策略 搜索的完备性和效率,第1-2章 搜索策略,基本概念 状态空间的搜索策略 与/或树的搜索策略 搜索的完备性和效率,基本概念,推理 什么是推理：依据一定的规则（策略）从已知的事实推出新事实（结论）的过程称为推理。,基本概念,推理 推理方式及其分类 演绎推理、归纳推理、默认推理 确定推理、不确定推理 单调推理、非单调推理 启发式推理、非启发式推理 ,基本概念 - 搜索,什么叫搜索：根据问题的实际情况不断寻找可用的知识，从而构造一条代价较小的推理线路，使问题得到解的过程称为搜索。 盲目搜索：按预定的控制策略进

2、行搜索，在搜索过程中获得的中间信息不用来改进控制策略。 启发式搜索：在搜索过程中加入了与问题有关的启发性信息，用以指导搜索朝最有利的方向前进，加速求解过程并得到最优解。,基本概念 - 状态空间表示法,状态：描述某一类事物中各不同事物之间的差异而引入的一组变量或多维数组。 Sk=(Sk0,Sk1,Skn) 算符(算子) ：引起状态中某些分量发生变化，从而使问题从一个状态改变到另一个状态的操作，以F指示。 状态空间：以SP指示，表示问题的全部可能的状态及其相互关系，状态和算符的集合。一般用三元式表示： SP = ( S0 , F , Sg ),基本概念 - 状态空间表示法,状态空间以SP指示，也可

3、表示为一个二元组： SP = （S, F） S-在问题求解（即搜索）过程中所有可达的合法状态构成的集合； F-操作算子的集合，操作算子的执行导致状态的变迁。 所以，状态空间又可描述为一个有向图，其节点指示状态，节点间的有向弧表示状态变迁，弧上的标签则指示导致状态变迁的操作算子。状态可通过定义某种数据结构来描述，用于记载问题求解（即搜索）过程中某一时刻问题现状的快照。,状态空间表示法举例：八数码游戏,问题：一个33棋盘，有八张牌1，2， 8及一个空格，空格周围的牌可以向空格移动。 求解：给定一个初始状态S0 、一个目标状态Sg ，求从S0到Sg的走步序列。,S0状态 Sg状态,解： 综合数据库（

4、状态及状态空间描述） 定义：矩阵（Sij）表示任何状态，其中： Sij0,1, 8 1i,j3 Sij 互不相同 状态空间：9！=362,880 种状态,状态空间表示法举例：八数码游戏, 规则集（算符F） 设：空格移动代替数码移动。至多有四种移动的可能：上、下、左、右。 定义： Sij为矩阵第i行j列的数码; 其中：i0,j0表示空格所在的位置，则Si0j0=0 （0代表空格） 空格左移规则： if j0-11 then j0j0-1; Si0j00 解释：如果当前空格不在第一列，则空格左移一位，新的空格位置赋值为0。 同理：右移规则：if j0+13 then j0j0+1; Si0j00

5、上移规则：if i0-11 then i0i0-1; Si0j00 下移规则：if i0+13 then i0i0+1; Si0j00,状态空间表示法举例：八数码游戏, 控制策略 需要解决的问题： 在当前可用的规则中如何选择其中之一来实现状态的转换 实时判断是否到达目标状态,状态空间表示法举例：八数码游戏,随机产生的八数码排列转换成目标共有两种可能，而且这两种不可能同时成立，也就是奇数排列和偶数排列。,状态空间表示法举例：八数码游戏,某初始状态 奇数排列 偶数排列,计算公式 （），其中（） 就是一个数的前面比这个数小的数的个数，判断为奇数或偶数,设N个传教士带领N个野人划船渡河，且为安全起见，

6、渡河需遵从二个约束： 1）船上人数不得超过载重限量，设为K个人； 2）为预防野人攻击，任何时刻（包括两岸、船上）野人数目不得超过传教士。,状态空间表示法举例：传教士和野人问题,状态空间表示法举例：传教士和野人问题,为便于理解状态空间表示方法，我们简化该问题到一个特例：N=3，K=2；并以变量m和c分别指示传教士和野人在左岸或船上的实际人数，变量b指示船是否在左岸（值1指示船在左岸，否则为0）。从而上述约束条件转变为m + c = c。 考虑到在这个渡河问题中，左岸的状态描述（m、c和b）可以决定右岸的状态，所以整个问题状态就可以左岸的状态来描述，以简化问题的表示。,设初始状态下传教士、野人和船

7、都在左岸，目标状态下这三者均在右岸，问题状态以三元组（m,c,b）表示，则问题求解任务可描述为： (3，3，1） （0，0，0） 在这个简单问题中，状态空间可能的状态总数为442 = 32 ，但由于要遵守安全约束，只有20个状态是合法的。下面是几个不合法状态的例子： (1，0，1）， （1，2，1）， （2，3，1） 鉴于存在不合法状态，还会导致某些合法状态不可达，例如状态（0，0，1），（0，3，0）。结果，这个问题总共只有16个可达的合法状态。,状态空间表示法举例：传教士和野人问题,渡河问题中的操作算子可以定义2类：L(m,c)、R(m,c)，分别指示从左岸到右岸的划船操作和从右岸回到左岸

8、的划船操作。由于m和c取值的可能组合只有5个：10，20，11，01，02，故而总共有10个操作算子。 渡河问题状态空间的有向图,状态空间表示法举例：传教士和野人问题,状态空间表示法举例：传教士和野人问题,基本概念 - 与/或树表示法,与/或树又称问题归约。 问题归约是人们求解问题常用的策略，就是把复杂的问题变换为若干需要同时处理的较为简单的子问题后再加以分别求解。只有当这些子问题全部解决时，问题才算解决，问题的解答就由子问题的解答联合构成。,基本概念 - 与/或树表示法,与/或图：应用问题归约策略得到的状态空间图。 与节点：用园弧将几条节点间关联弧连接在一起去指示问题分解为若干子问题，只有这

9、些子问题全部解决才会导致问题的解决。 或节点：问题（子问题）也可能激活多条重写规则（等价变换）；显然，只要有一条激活的重写规则能导致最终的解答成功即可。,基本概念 - 与/或树表示法,本原问题：不可或不需再通过变换，可以直接得到问题的解的子问题。 端节点与终止节点：没有子节点的节点称为端节点（叶节点）。本原问题对应的节点称为终止节点。,基本概念 - 与/或树表示法,可解节点： 终止节点是可解节点。 如果非终止节点有“或”子节点，当且仅当其子节点至少有一个能解，则该非终止节点是可解节点。 如果非终止节点有“与”子节点，当且仅当其子节点都能解，则该非终止节点是可解节点。,基本概念 - 与/或树表示

10、法,不可解节点： 没有后裔的非终止节点是不可解节点（该节点是叶节点但不是本原问题）。 如果非终止节点有“或”子节点，当且仅当所有子节点都不能解，则该非终止节是不可解节点。 如果非终止节点有“与”子节点，至少有一个子节点不能解，则该非终止节点是不可解节点。 解树：由可解节点构成，并且由这些可解节点可推出初始节点为可解节点的子树。,基本概念 - 与/或树表示法,与或图是一个超图，节点间通过连接符连接。 K-连接符：,解图：,基本概念 - 与/或树表示法,解图的耗散值计算： 设K_连接符的耗散值为K，G的耗散值为K(n,N) 若n 是N的一个元素，则K(n,N)=0 若n有一个到解图中后继节点集n1

11、, n2 ni的外向连接符，设该连接符的耗散值为Cn，则 K(n,N) Cn+ K(n1,N)+ K(n2,N)+ + K(ni,N),基本概念 - 与/或树表示法,左图耗散值 K(n0,N) 1+ K(n1,N) 1+1+ K(n3,N) 1+1+2+ K(n5,N)+ K(n6,N) 1+1+2+2+ K(n7,N)+ K(n8,N)+2+ K(n7,N)+ K(n8,N) 1+ 1+ 2+ 2+ 0+ 0+ 2+ 0+ 0 8,右图耗散值 K(n0,N) 2+ K(n4,N) + K(n5,N) 2+ 1+K(n5N) + 2+K(n7,N) +K(n8,N) 2+ 1+ 2+K(n7,

12、N) +K(n8,N) + 2+K(n7,N) +K(n8,N) 2+ 1+ 2+ 0+ 0+ 2+ 0+ 0 7,与/或树表示法举例：梵塔问题,（1 1 1） （3 3 3）,（1 2 2） （3 2 2）,（3 2 2） （3 3 3）,（1 1 1） （1 2 2）,（1 1 1） （1 1 3）,（3 2 2） （3 2 1）,（3 2 1） （3 3 1）,（3 3 1） （3 3 3）,（1 2 3） （1 2 2）,（1 1 3） （1 2 3）,( c b a ),与/或树表示法举例：符号积分问题,符号积分是求不定积分原函数的问题，通过应用各种代数和三角变换以及不定积分性质（如

13、函数和积分、分部积分等）可以把复杂的积分问题逐步归约为若干个本原积分问题（可利用积分表直接求出原函数）。六十年代开发的SAINT系统。就是一个应用问题归约的符号积分系统。,与/或树表示法举例：符号积分问题,作为一个例子，观察： ( sin3x + x4/(x2 + 1) ) dx =sin3xdx + (x4/(x2 + 1)dx =-(1 - cos2x)dcosx + (x2 - 1 + 1/(1 + x2)dx = (-dcosx + cos2xdcosx) + (x2dx - dx + (1/(1 + x2)dx ) = -cosx + cos3x/3 + x3/3 - x + arc

14、tgx 该积分问题首先分解为二个独立的子问题，然后分别变换这二个积分子问题，并分解变换结果为若干本原积分问题，分别求解这些本原问题后再联合成最终解答。,第1-2章 搜索策略,基本概念 状态空间的搜索策略 与/或树的搜索策略 搜索的完备性和效率,第1-2章 搜索策略,基本概念 状态空间的搜索策略 与/或树的搜索策略 搜索的完备性和效率,状态空间的搜索策略,状态空间的搜索以SE指示，可表示为一个五元组： SE = (S,F,E,S0,Sg) E -搜索引擎； S0 -问题的初始状态， S0 S; Sg -问题的目标状态集， Sg S。 状态空间搜索的基本思想就是通过搜索引擎寻找一个操作算子的调用序

15、列，使问题从初始状态变迁到目标状态之一，而变迁过程中的状态序列或相应的操作算子调用序列称为从初始状态到目标状态的 解答路径。搜索引擎可以设计为任意实现搜索算法的控制系统。,状态空间的搜索策略,通常，状态空间的解答路径有多条，但最短的只有1条或少数几条。上述渡河问题就有无数条解答路径（因为划船操作可逆），但只有4条是最短的，都包含11个操作算子的调用。由于一个状态可以有多个可供选择的操作算子，导致了多个待搜索的解答路径。 除了少数像渡河这样的简单问题外，描述状态空间的一般图都很大，无法直观地画出，只能将其视为隐含图，在搜索解答路径的过程中只画出搜索时直接涉及到的节点和弧线，构成所谓的 搜索图。,状态空间的搜索策略,八数码问题的搜索图。 对于八数码游戏，可能的棋盘布局（问题状态）总共9!=362880个，由于棋盘的对称性，实际只有这个总数的一半。显然，我们无法直观地画出整个状态空间的一般图，但搜索图则小得多，可以图示。 状态空间、搜索图和解答路径之间的关系 ,状态空间的搜索策略,尽管状态空间可以很大（例如国际象棋），但只要确保搜索空间足够小，就能在合理的时间范围内搜索到问题解答。 搜索空间的压缩程度主要取决于搜索引擎采用的搜索算法。换言之，当问题有解时，使用不同的搜索策略，找到解答路径时，搜索图的大小是有区别的。,一些基本概念,节点深度： 根节