搜索
人工智能2003秋1一个智能系统搜索策略的优劣直接影响到系统的性能语推理效率。本章主要内容：搜索的基本概念；状态空间的盲目搜索；状态空间的启发式搜索；与或树的盲目搜索；与或树的启发式搜索；博奕树的启发式搜索；第5章搜索测略人工智能2003秋25.1搜索策略的基本概念5.1.1搜索的含义1.搜索定义:根据问题的实际情况，不断寻找可利用的知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索。2.组合爆炸问题：结构良好，理论上有算法可依的问题，如果问题或算法的复杂性较高（按指数形式增长），由于受计算机在时间和空间上的限制，无法付诸实用。人工智能2003秋35.1搜索策略的基本概念3.搜索类型：(1)根据是否使用启发信息分类：盲目搜索：按预定的控制策略进行，在搜索过程中获得的中间信息不改变控制策略。启发式搜索：在搜索过程中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。人工智能2003秋45.1搜索策略的基本概念(2)根据问题的表示方式分类：状态空间搜索：用状态空间法来求解问题所进行的搜索。与/或树搜索：用问题归约法来求解问题时所进行的搜索。人工智能2003秋55.1搜索策略的基本概念5.1.2状态空间法1.状态空间表示法（1）状态(state):表示问题求解过程中每一步问题状况的数据结构，形式的表示为：Sk={Sk0,Sk1,…)当对每一个分量都予以确定的值时，就得到了一个具体的状态。人工智能2003秋65.1搜索策略的基本概念（2）操作（operator)（算符）把问题从一种状态转换为另一种状态的手段。可以是一个机械步骤、一个运算、一条规则或一个过程。可理解为状态集合上的一个函数，描述了状态之间的关系。人工智能2003秋75.1搜索策略的基本概念（3）状态空间（statespace）描述一个问题的全部状态以及这些状态之间的相互关系。常用三元组表示:(S,F,G)S:为问题所有初始状态的集合。F:为操作的集合。G:为目标状态的集合。人工智能2003秋85.1搜索策略的基本概念状态空间图：赋值的有向图。节点表示问题的状态，有向边表示操作.2.状态空间问题求解任何以状态和操作为基础的问题求解方法都称为状态空间问题求解。简称为状态空间法。状态空间法的基本过程为：（1）为问题选择适当的“状态”及“操作”的形式化描述方法。人工智能2003秋95.1搜索策略的基本概念（2）从某个初始状态出发，每次使用一个“操作”，递增地建立起操作序列，直到达到目标状态为止。（3）从初始状态到目标状态所使用的算符序列就是问题的一个解。人工智能2003秋105.1搜索策略的基本概念3.状态空间的例子例5.1:二阶梵塔问题：设有三根钢针，它们的编号分别是1，2，3。在初始情况下，1号钢针上穿有A、B两个金片，A比B小，A位于B的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大片位于小片的上面。人工智能2003秋115.1搜索策略的基本概念解：设用Sk={Sk0,Sk1}表示问题的状态，其中，Sk0表示金片A所在的钢针号，Sk1表示金片B所在的钢针号。全部可能的问题状态共有以下9种：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)其中S0为初始状态，S4和S8为目标状态。人工智能2003秋125.1搜索策略的基本概念任何以状态和操作为基础的问题求解方法都称为状态空间问题求解。简称为状态空间法。状态空间法的基本过程为：（1）为问题选择适当的“状态”及“操作”的形式化描述方法。（2）从某个初始状态出发，每次使用一个“操作”，递增地建立起操作序列，直到达到目标状态为止。（3）从初始状态到目标状态所使用的算符序列就是问题的一个解。人工智能2003秋135.1搜索策略的基本概念例5.2修道士和野人问题.首先选取描述问题状态的方法。用一个三元组表示状态：S=(m,c,b)其中：m表示左岸的修道士数；c表示左岸的野人数；b表示左岸的船数；人工智能2003秋145.1搜索策略的基本概念右岸的状态由下式确定：右岸的修道士数m’=3-m；右岸的野人数c’=3-c；右岸的船数b’=1-b；m和c的取值分别为0，1，2，3之一；b的取值分别为0，1;共有4x4x2=32种状态。人工智能2003秋155.1搜索策略的基本概念3,32,12,31,21,3A(3,2)2,23,23,11,1B(1,2)A(1,3)二阶樊塔状态空间图人工智能2003秋165.1搜索策略的基本概念除去不合法的状态和修道士被野人吃掉的状态，余下的状态由16种：S0=(3,3,1),S1=(3,2,1),S2=(3,1,1),S3=(2,2,1),S4=(1,1,1),S5=(0,3,1),S6=(0,2,1),S7=(0,1,1),S8=(3,2,0),S9=(3,1,0),S10=(3,0,0),S11=(2,2,0),S12=(1,1,0),S13=(0,2,0),S14=(0,1,0),S15=(0,0,0),人工智能2003秋175.1搜索策略的基本概念需要考虑的操作有：（1）船至少有一个人（m或c）操作，离开岸边的m和c的减少数目应该等于到达岸边的m和c的增加数目；（2）每次操作船上的人数不得超过2个；（3）操作应保证不产生非法状态。操作由两部分组成：条件部分和动作部分。人工智能2003秋185.1搜索策略的基本概念用Qij表示从右岸到左岸的运人操作，可供选择的操作由10种，操作集为：F={P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20,}以P01和Q01为例说明操作的条件和动作：操作符号条件动作P01b=1,m=0或3,c≥1b=0,c=c-1Q01b=1,m=0或3,c≤2b=1,c=c+1人工智能2003秋195.1搜索策略的基本概念例5.3猴子摘香蕉问题.首先选取描述问题状态的方法。用一个四元组表示状态：S=(w,x,y,z)其中：w表示猴子的水平位置；x表示箱子的水平位置；y表示猴子是否在箱子上，当猴子在箱子上时y=1否则y=0；z表示猴子是否拿到香蕉，当拿到香蕉时z=1否则z=0；人工智能2003秋205.1搜索策略的基本概念所有可能的状态有：S0=(a,b,0,0),初始状态S1=(b,b,0,0),S2=(c,c,1,0),S3=(c,c,1,1),目标状态人工智能2003秋215.1搜索策略的基本概念允许的操作为：Goto(u):猴子走到位置u，即:(w,x,0,0)→(u,x,0,0)Pushbox(v):猴子推着箱子到水平位置v，即:(x,x,0,0)→(v,v,0,0)Climbbox:猴子爬上箱子，即:(x,x,0,0)→(x,x,1,0)Grasp:猴子拿到香蕉，即:(c,c,1,0)→(c,c,1,1)人工智能2003秋225.1搜索策略的基本概念问题的状态空间图见书P172,图5-3.由初始状态变为目标状态的操作序列为：{Goto(b),Pushbox©,Climbbox,Grasp}人工智能2003秋235.1搜索策略的基本概念5.1.3问题归约问题是不同于状态空间方法的另外一种形式化方法，基本思想是对问题进行分解或变换。当一个问题比较复杂时，直接求解比较困难，可以通过分解或变换，将其转化为一系列较简单的问题，然后通过对较简单的球接来实现对原问题的求解。1.问题的分解与等价变换当把一个问题归约为子问题时，可采用对原问题的分解或变换方法。人工智能2003秋245.1搜索策略的基本概念（1）分解如果一个问题P可以归约为一组子问题P1,P2,…,Pn，并且只有当所有子问题Pi(I=1,2,…,n)都有解时，原问题P才有解，任何一个子问题Pi(I=1,2,…,n)无解都会导致原问题P无解。称这种归约为问题的分解。分解所得到的子问题的“与”与原问题P等价。人工智能2003秋255.1搜索策略的基本概念（2）等价变换如果一个问题P可以归约为一组子问题P1,P2,…,Pn，并且这些子问题Pi(I=1,2,…,n)中只要有一个有解则原问题P就有解，只有当所有的子问题都无解时，原问题P才无解，称这种归约为问题的等价变换。简称变换。即变换所得的子问题的“或”与原问题P等价。人工智能2003秋265.1搜索策略的基本概念在实际问题的归约过程中，有可能需要同时采用变换和分解的方法。无论是分解还是变换，都是要将原问题归约为一系列本原问题。所谓本原问题是指那种不能分解（或不需要分解）或变换，且可以直接解答的子问题。本原问题可以作为终止归约的限制条件。人工智能2003秋275.1搜索策略的基本概念2.问题归约的“与或树”表示当把一个原问题归约为一系列本原问题的过程可以很方便的用一个“与或树”来表示。（1）与树（2）或树人工智能2003秋285.1搜索策略的基本概念（3）与/或树人工智能2003秋295.1搜索策略的基本概念（4）端节点与终止节点端节点：没有子节点的节点。终止节点：本原问题所对应的节点。（5）可解节点与不可解节点满足以下三个条件的为可解节点:•任何终止节点都是可解节点；•对“或”节点，当其子节点中至少有一个可解节点时，则该或节点就是可解节点；•对“与”节点，只有当其子节点全部为可解节点时，则该与节点才是可解节点。人工智能2003秋305.1搜索策略的基本概念满足以下三个条件的为不可解节点:•不为终止节点的端节点是不可解节点；•对“或”节点，若其全部子节点中为不可解节点时，则该或节点就是不可解节点；•对“与”节点，只要其子节点中有一个为不可解节点时，则该与节点才是不可解节点。人工智能2003秋315.1搜索策略的基本概念（6）解树由可解节点构成，并且由这些可解节点可以推出初始节点（对应着原始问题）为可解节点的子树为解树。在解树中一定包含初始节点。人工智能2003秋325.1搜索策略的基本概念人工智能2003秋335.1搜索策略的基本概念3.问题归约的例子例5.4:三阶梵塔问题：设有三根钢针，它们的编号分别是1，2，3。在初始情况下，1号钢针上穿有A、B、C三个金片，自上而下，有小到大，。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大片位于小片的上面。用归约法求解。人工智能2003秋345.1搜索策略的基本概念解：为了能够解决这一问题，首先需要定义该问题的形式化表示方法。用三元组（i,j,k)表示问题任何时刻的状态；用“→”表示状态的转换；i表示金片C的针号;j表示金片B的针号;k表示金片A的针号;人工智能2003秋355.1搜索策略的基本概念利用问题归约方法，原问题可分解为以下三个子问题:(1)把金片A及B移到2号钢针上的双金片移动问题：(1,1,1)→(1,2,2)(2)把金片C移到3号钢针上的单金片移动问题：(1,2,2)→(3,2,2)(1)把金片A及B移到3号钢针上的双金片移动问题：(3,2,2)→(3,3,3)人工智能2003秋365.1搜索策略的基本概念(1,1,1)→(3,3,3)(1,1,1)→(1,2,2)(3,2,2)→(3,3,3)(1,2,2)→(3,2,2)(3,3,1)→(3,3,3)(3,2,1)→(3,3,1)(3,2,2)→(3,2,1)(1,2,3)→(1,2,2)(1,1,3)→(1,2,3)(1,1,1)→(1,1,3)人工智能2003秋375.1搜索策略的基本概念原始问题的解：(1,1,1)→(1,1,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)人工智能2003秋385.2状态空间的盲目搜索状态空间的搜索策略可分为盲目搜索和启发式搜索。启发式搜索需要抽取与问题本身有关的特征信息，而信息抽取比较困难，所以盲目搜索仍不失