人工智能之搜索163

人工智能导论第二章：搜索、问题求解与博弈第二章搜索、问题求解与博弈问题求解能力是人类智能的基本组成部分，研究并实现问题求解是人工智能的重要研究内容之一。知识（问题）的表示是问题求解的基础，两种普遍采用的问题表示方法：状态空间表示与或图表示搜索（优化）：在问题表示基础上，在合理的时间范围内，从问题所有可能的解中找到一个最优解或可行解，是问题求解中的核心技术。启发式搜索----人工智能的本质特征之一。计算机博弈涉及问题表示、搜索技术等AI核心问题，现有的计算机博弈本质上是将博弈问题转变为一个与或图搜索问题进行处理。主要内容2.1搜索概述2.2问题求解2.2.1状态空间2.2.2与或图2.3搜索技术图搜索2.4机器博弈一些例子搭积木智力游戏：有一个农夫带一条狼、一只羊和一筐菜要从河的左岸乘船到右岸，但受下列条件限制：船太小，农夫每次只能带一样东西过河没有农夫看管，则狼要吃羊，羊要吃菜请设计一个过河方案，使得农夫、狼、羊、菜都不能受损地过河。类似问题：野人和传教士问题下棋（扑克、西洋跳棋、国际象棋、象棋等）（属于博弈）2.1搜索概述人工智能的多个研究领域从求解现实问题的过程来看，都可抽象为一个“问题求解”过程问题求解过程实际上就是一个搜索过程最优性和计算法复杂性是搜索中的一对矛盾，搜索必须考虑的三个问题：采用盲目搜索还是启发式搜索盲目搜索：不考虑问题本身的特性，通过遍历问题解的集合来寻找可行解或最优解。启发式搜索：利用与问题有关的启发式信息来确定搜索方向，以加快搜索过程。进行局部搜索还是全集搜索搜索可行解还是最优解2.1搜索概述评价一个搜索算法的因素：完备性：如果问题有解，一定能找到一个解最优性：如果问题存在最优解，则一定能找到这个最优解复杂性：时间和空间复杂性，在保证最优性和完备性的前提下，算法的复杂性越小越好。目前的搜索算法还不能同时满足以上三个要求。为了进行搜索，首先必须用某种形式把问题表示出来：状态空间表示法和与或图表示法就是用来表示问题及其搜索过程的两种常用方法。2.2问题求解状态空间表示法和与或图表示法不仅是问题表示的方法，也分别代表了两种问题求解的思路状态空间将问题求解所涉及的每个可能的步骤表示成一个状态，全部状态以及状态之间的所有转换构成一个以图的形式表示的状态空间。问题的求解过程是在状态空间中搜索一条最优的或可行的从初始状态到目标状态的路径的过程。与或图表示法的基础是问题归约，通过一系列分解或变换，将复杂问题逐步转化为比较简单的问题，直至可以直接求解的本原问题。与或图的求解过程是在与或图中搜索一个将原始问题变换为简单问题在变换为本原问题的、最优的或可行的归约步骤的过程。2.2.1状态空间表示法状态空间表示法是用“状态”和“算子”来表示问题的一种方法状态：用来描述问题求解过程中不同时刻的状况算子：表示对状态的操作，算子的每次使用就使问题由一种状态变换为另一种状态当达到目标状态时，由初始状态到目标状态所用算子的序列就是问题的一个解2.2.1状态空间表示法状态状态是描述问题求解过程中任一时刻状况的数据结构，一般用一组变量的有序组合表示：SK(SK0,SK1,…)当给每一分量以确定的值时，就得到一个具体的状态算子引起状态中某些分量发生变化，从而使问题由一个状态变为另一个状态的操作称为算子。产生式系统中，每一条产生式规则就是一个算子状态空间由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，一般用三元组表示:(S,F,C,I,G)S:所有状态构成的集合F:用于状态转换的算子的集合C:状态转换代价的聚合I:初始状态的集合G:目标状态的集合例:二阶HanoiTower（梵塔）问题设有三根柱子，在1号柱于上穿有A、B两个盘片，盘A小于盘B，盘A位于盘B的上面。要求把这两个盘片全部移到另一根柱子上，而且规定每次只能移动一片，任何时刻都不能使盘B位于盘A的上面。设SK=(SK0,SK1)表示问题的状态，SK0表示盘片A所在的柱号，SK1表示盘片B所在的柱号全部可能的状态: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).问题的初始状态集合S={S0},目标集合为G={S4,S8}算子分别用A(i,j),B(i,j)表示A(i,j):盘片A从柱i移到柱j；B(i,j):盘片B从柱i移到柱j全部可能的算子：A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2),B(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2)例:二阶HanoiTower（梵塔）问题9种状态，12种算子构成的状态空间转移图：2.2.1状态空间表示法总结：用状态空间方法表示问题时，首先必须定义状态的描述形式，通过使用这种描述形式可把问题的一切状态都表示出来。其次，还安定义一组算符，通过使用算符可把问题由一种状态转变为另一种状态。问题的求解过程是一个不断把算符作用于状态的过程。如果在使用某个算符后得到的新状态是目标状态，就得到问题的一个解：从初始状态到目标状态所用算符构成的序列。算符的一次使用，就使问题由一种状态转变为另一种状态。可能有多个算特序列都可使问题从初始状态变到目标状态，这就得到了多个解。把使用算符最少的解称为最优解。对任何一个状态，可使用的算符可能不止一个，因而由一个状态所生成的后继状态就可能有多个。当对这些后继状态使用算子生成更进一步状态时，首先应对哪一状态进行操作呢？这取决于搜索策略，不同搜索策略的操作顺序是不相同的。2.2.1状态空间表示法基于状态空间表示的问题求解算法Step1：确定问题状态的计算机描述形式，将所有可能的状态表示出来，并确定其中的初始状态和目标状态。Step2：确定促使状态发生转换的操作，并在计算机中将其表示为相应的算符。Step3：以状态为顶点，状态之间所允许的操作为有向边，获得‘图’形式的状态空间。Step4：应用图搜索方法，在状态空间中搜索从初始状态到目标状态的最优路径或可行路径。例:三阶HanoiTower（梵塔）问题例:三阶HanoiTower（梵塔）问题例:三阶HanoiTower（梵塔）问题2.2.2与或图表示法也称为问题归约方法：把初始问题通过一系列交换最终变为一个子问题集合，而这些于问题的解可以直接得到，从而解答了初始问题。分解：把一个复杂问题分解为若干个较为简单的子问题，每个子问题又可继续分解为若干个更为简单的子问题。重复此过程，直到不需要再分解或者不能再分解为止。然后对每个子问题分别进行求解，最后把各子问题的解复合起来就得到了原问题的解。问题的分解可以用图表示出来，称为与树。例如，把问题P分解为三个子问题P1、P2和P3，可以表示为下图：2.2.2与或图表示法等价变换：利用同构或同态的等价变换，把它变换成若干个较容易求解的新问题。若新问题中有一个可求解，则就得到了原问题的解。问题的等价变换过程也可用一个图表示出来，称为“或”树。与或树的结合称为与或图（树）。2.2.2与或图表示法本原问题：不能再分解或变换，而且直接可解的子问题称为本原问题。端节点与终止节点：在与／或树中，没有子节点的节点称为端节点；本原问题所对应的节点称为终止节点。显然，终止节点一定是端节点，但端节点不一定是终止节点。可解节点：在与／或树今，满足下列条件之一的节点：1)它是一个终止节点。2)它是一个“或”节点，且其子节点至少有一个是可解节点。3)它是一个“与”节点，且其子节点全部是可解节点。不可解节点：上面三个条件全不满足的节点。解树：由可解节点所构成的，并且由这些可解节点可推出初始节点(它对应于原始问题)为可解节点的子树称为解树。在解树中’定包含初始节点。例:三阶HanoiTower（梵塔）问题设有A、B、C三个盘片以及三根柱子，三个盘片按从小到大的顺序穿在1号柱上，要求把它们全部移到3号柱上，而且每次只能移动一个盘片，任何时刻都不能把大的盘片压在小的盘片上面，如图所示。例:三阶HanoiTower（梵塔）问题分析：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)又分别可分解为三个子问题例:三阶HanoiTower（梵塔）问题定义问题状态表示：设三元组(i,j,k)表示状态，其中i表示盘片C所在的柱号,j表示盘片B所在的柱号；k表示盘片A所在的柱号。初始问题可表示为：(1、1．1)(3，3，3)与／或树表示如图所示。(把图中7个终止节点(本原问题)按从左至右排列，得到了初始问题的解)2.2.2与或图表示法基于与或图表示的问题求解算法Step1：确定单个问题描述形式，可采用状态空间表示法。Step2：从原始问题开始，逐步进行分解和变换，直到本原问题，然后将全部分解和变换过程表示为与或图。Step3：从端顶点开始，逐步向上回溯，标注各顶点为可解或不可解顶点，直到标注原始顶点为可解顶点或不可解顶点为止Step4：当原始顶点被确定为可解顶点时，输出相应解图为问题的解。2.3搜索技术搜索技术是人工智能的基本技术之一,在人工智能各应用领域中被广泛地使用。早期的人工智能程序与搜索技术联系就更为紧密，几乎所有的早期的人工智能程序都是以搜索为基础的。例如，A.Newell(艾伦·纽厄尔)和H·A·Simon(西蒙)等人编写的LT(LogicTheorist)程序,J.Slagle写的符号积分程序SAINT,A·Newell和H·A·Simon写的GPS(GeneralProblemSolver)程序,H·Gelernter(格伦特尔)写的Geometrytheorem-provingmachine程序,R.Fikes(菲克斯)和N.Nilsson(尼尔逊)写的STRIPS(StanfordResearchInstituteProblemSolver)程序以及A.Samuel(塞缪尔)写的Chechers程序等,都使用了各种搜索技术。现在,搜索技术渗透在各种人工智能系统中,可以说没有哪一种人工智能的应用不用搜索方法,在专家系统、自然语言理解、自动程序设计、模式识别、机器人学、信息检索和博弈都广泛使用搜技术。2.3搜索技术搜索问题是AI核心理论问题之一一般一个问题可以用好几种搜索技术解决,选择一种好的搜索技术对解决问题的效率很有关系,甚至关系到求解问题有没有解。搜索方法好的标准,一般认为有两个：(1)搜索空间小;(2)解最佳。2.3搜索技术搜索从问题性质上来看,可分为一般搜索和博奕搜索,从处理方法上来看,可分为盲目搜索和启发式搜索。还可以分得更细。当所给定的问题用状态空间表示时,则求解过程可归结为对状态空间的搜索。当问题有解时,使用不同的搜索策略,找到解的搜索空间范围是有区别的。一般来说,对大空间问题,搜索策略是要解决组合爆炸的问题2.3搜索策略通常搜索策略的主要任务是确定如何选取规则的方式。有两种基本方式:一种是不考虑给定问题所具有的特定知识,系统根据事先确定好的某种固定排序,依次调用规则或随机调用规则,这实际上是盲目搜索的方法,一般统称为无信息引导的搜索策略。另一种是考虑问题领域可应用的知识,动态地确定规则的排序,优先调用较合适的规则使用,这就是通常称为启发式搜索策略或有信息引导的搜索策略。AI领域的搜索方法(1)求任一解路的搜索策略回溯法(Backtracking)爬山法(HillClimbing)宽度优先法