人工智能2012(3)

第三章搜索推理技术3.6规则演绎系统3.7产生式系统3.8系统组织技术3.9不确定性推理3.10非单调推理3.1图搜索策略3.2盲目搜索3.3启发式搜索3.4博弈树的启发式搜索3.5消解原理3.1图搜索策略•图搜索控制策略一种在图中寻找路径的方法。图中每个节点对应一个状态，每条连线对应一个操作符。这些节点和连线(即状态与操作符)又分别由产生式系统的数据库和规则来标记。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。一般图搜索过程状态空间搜索的基本思想是：先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了该问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或没有可供扩展的节点为止。搜索术语（用图来描述状态空间）•节点：对应于状态描述•节点深度：根节点的深度为0,其他节点的深度规定为父节点深度加1,即dn+1=dn+1。•扩展节点：应用操作符将上一状态（节点ni）变迁到下一状态（节点nj），ni表示被扩展节点，nj即是由ni扩展出的子节点。•路径：从节点ni到nk的路径是由相邻节点间的弧线构成的折线，通常要求路径是无环的，否则会导致搜索过程进入死循环。•搜索图：在搜索解答路径的过程中只画出搜索时直接涉及到的节点和弧线，构成所谓的搜索图。•Open表：存放已经生成但未扩展节点•Close表：存放已扩展或将要扩展的节点•S0表示问题的初始状态•G表示搜索过程所得到的搜索图•M表示当前扩展节点新生成的且不为自己先辈的子节点集。开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向重排OPEN表失败成功图3.1图搜索过程框图是是否否图搜索过程图树/不修改指针;图/修改指针;修改指针:找最优解3.2盲目搜索•特点：不需重排OPEN表•种类：宽度优先、深度优先、等代价搜索等。3.2.1宽度优先搜索定义以接近起始节点的程度逐层扩展节点的搜索方法。特点：一种高代价搜索，但若有解存在，则必能找到它。算法开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表是否有后继节点为目标节点？扩展n，把n的后继节点放入OPEN表的末端，提供返回节点n的指针失败成功图3.2宽度优先算法框图是否是否3.2盲目搜索例：八数码难题3×3九宫棋盘，放置数码为1-8的8个棋牌，剩下一个空格，只能通过棋牌向空格的移动来改变棋盘的布局。求解的问题——给定初始布局（即初始状态）和目标布局（即目标状态），如何移动棋牌才能从初始布局到达目标布局解答路径——就是一个合法的走步序列用宽度优先搜索方法解决该问题：为问题状态的表示建立数据结构：3×3的一个矩阵，*矩阵元素Sij∈{0,1,…,8}；其中1≤i,j≤3，*数字0指示空格，*数字1-8指示相应棋牌。制定操作算子集：*直观方法——为每个棋牌制定一套可能的走步：左、上、右、下四种移动。这样就需32个操作算子。*简易方法——仅为空格制定这4种走步，因为只有紧靠空格的棋牌才能移动。*空格移动的唯一约束是不能移出棋盘。初始状态S0：23目标状态Sg：12318480476576523184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标8234187654宽度优先搜索91011121314151617从图中得，解的路径是：S0→→→38173.2.2深度优先搜索定义首先扩展最新产生的(即最深的)节点。算法防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度——深度界限。与宽度优先搜索算法最根本的不同在于：将扩展的后继节点放在OPEN表的前端。（算法框图见教材）3.2盲目搜索例：八数码难题231847652318476528314765231847652831476528316475283147652831647528316475123784651238476528364175123412384765目标深度优先搜索…………2318476523184765283147652318476528314765283164752831476528316475283164752837146583214765281437652831457612378465123847652836417528316754832147652837146528143765283145761234567891011121312384765目标设深度界限dm=4例：八数码难题3.2.3等代价搜索定义是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。算法若所有连接弧线具有相等代价，则简化为宽度优先搜索算法。3.2盲目搜索3.3启发式搜索•特点：重排OPEN表，选择最有希望的节点加以扩展•种类：有序搜索(A算法)、A*算法等3.3.1启发式搜索策略和估价函数盲目搜索可能带来组合爆炸启发式信息用来加速搜索过程的有关问题领域的特征信息。包括：用于决定要扩展的下一个节点的信息；在扩展一个节点时，用于决定要生成哪一个或哪几个后继节点的信息；用于决定某些应该从搜索树中抛弃或修剪的节点的信息；启发式搜索使用启发式信息指导的搜索过程称为启发式搜索.估价函数用来估算节点处于最佳求解路径上的希望程度的函数f(n)=g(n)+h(n)n——搜索图中的某个当前被扩展的节点；f(n)——从初始状态节点s,经由节点n到达目标节点ng，估计的最小路径代价；g(n)——从s到n的实际路径代价；h(n)——从n到ng,估计的最小路径代价。例——八数码难题估价函数：f(n)=d(n)+w(n)其中：d(n)为n的深度w(n)为不在位的棋子数如起始节点283164705则起始节点S0的估价函数值为：f(S0)=0+4=43.3.2有序搜索实质选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。3.3启发式搜索(1)全局择优搜索：选择OPEN表上具有最小f值的节点作为下一个要扩展的节点，即总是选择最有希望的节点作为下一个要扩展的节点。(2)局部择优搜索：从刚生成的子节点中选择具有最小f值的节点作为下一个要扩展的节点。开始把S放入OPEN表，计算估价函数f(s)OPEN表为空表？选取OPEN表中f值最小的节点i放入CLOSED表i为目标节点吗？扩展i，得后继节点j，计算f(j)，提供返回节点i的指针，利用f(j)对OPEN表重新排序，调整亲子关系及指针失败成功图3.9有序搜索算法框图是否是否3.3启发式搜索算法•例子八数码难题（8-puzzleproblem）12384567（目标状态）12384567（初始状态）八数码难题的有序搜索树见下图：3.3启发式搜索5714563123845671238456712384567（4）（6）（6）2123845671238456712384567（6）（5）（5）1238456712384567（5）（7）1238456712384567（6）（7）12384567（5）8132456712384567（5）（7）图3.10八数码难题的有序搜索树123846（4）73.3启发式搜索53.3.3A*算法•估价函数的定义：对节点n定义f*(n)=g*(n)+h*(n),表示从S开始约束通过节点n的一条最佳路径的代价。希望估价函数f定义为：f(n)=g(n)+h(n)——g是g*的估计，h是h*的估计3.3启发式搜索g*(n)：从s到n的最小路径代价值h*(n)：从n到g的最小路径代价值f*(n)=g*(n)+h*(n)：从s经过n到g的最小路径的总代价值g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值g(n)通常选择为当前所找到的从初始节点S到节点n的“最佳”路径的代价值，显然有g(n)g*(n)在A算法中，如果满足条件：(1)g(n)是对g*(n)的估计，且g(n)0；(2)h(n)是h*(n)的下界，即对任意节点n均有0≤h(n)≤h*(n)则A算法称为A*算法A*算法的定义：定义1在GRAPHSEARCH过程中，如果第8步的重排OPEN表是依据f(n)=g(n)+h(n)进行的，则称该过程为A算法。定义2在A算法中，如果对所有的n存在h(n)≤h*(n),则称h(n)为h*(n)的下界，它表示某种偏于保守的估计。定义3采用h*(n)的下界h(n)为启发函数的A算法，称为A*算法。当h=0时，A*算法就变为有序搜索算法。A*算法的可纳性对任一个图，存在从S到目标的路径，如果一个搜索算法总是结束在一条从S到目标的最佳路径上，则称此算法是可采纳的。算法A*保证只要最短路径存在，就一定能找出这条路径，所以算法A*是可纳的。A*算法应用举例八数码难题估价函数：f(n)=d(n)+w(n)其中：d(n)为n的深度w(n)为不在位的棋子数取h(n)=w(n),则有w(n)≤h*(n),h(n)满足A*算法的限制条件。1238476528316475初始状态目标状态在八数码难题中,令估价函数f(n)=d(n)+p(n)启发函数h(n)=p(n),p(n)为不在位的棋子与其目标位置的距离之和，则有p(n)≤h*(n),满足A*算法的限制条件。283164752831476528316475283164752318476528314765283147652318476523184765123847651238476512378465目标12345h=5,g=0,f=5h=6,g=1,f=7h=4,g=1,f=5h=6,g=1,f=7h=5,g=2,f=7h=3,g=2,f=5h=5,g=2,f=7h=2,g=3,f=5h=4,g=3,f=7h=1,g=4,f=5h=0,g=5,f=5w(n)——不在位的棋子数，不够贴切，错误选用节点加以扩展。p(n)——更接近于h*(n)的h(n)，其值是节点n与目标状态节点相比较，每个错位棋子在假设不受阻拦的情况下，移动到目标状态相应位置所需走步的总和。p(n)比w(n)更接近于h*(n)，因为p(n)不仅考虑了错位因素，还考虑了错位的距离（移动次数）。说明h值越大,启发功能越强,搜索效率越高.特别地(1)h(n)=h*(n)搜索仅沿最佳路径进行,效率最高.(2)h(n)=0无启发信息,盲目搜索,效率低.(3)h(n)h*(n)是一般的A算法,效率高,但不能保证找到最佳路径.有时为求解难题取h(n)h*(n),以提高效率.3.4博弈树的启发式搜索–参与搜索的不只是一个主体，而包括对抗的多方(对弈)–任何一方在选择自己的行为时，都要将对方可能采取的对策考虑在内–由此而产生的搜索树称为博弈树(博弈图)博奕:两棋手按一定规则轮流走步,双方都知道对方的走步,当满足一定条件时,走步结束,这时,或一方取胜,或为和局.1.博弈问题我方（指程序方，叫MAX）每走一着棋（半回合），都力图使自己通向取胜的目标。轮到MAX走棋时，由于它掌握着出棋的主动权，只要此时的各种走法中有一个能通向胜局，它就会毫不客气地出这一着。因此由MAX方出棋的结点具有或结点的性质。对手（叫MIN，是一个回合的对棋者）每走一着棋（半回合），都力图干扰MAX的选择，使其偏离取胜的目标。轮到MIN走棋时，由于它掌握着对棋的主动权，因此只要此时的全部着法中有一个能导致败局，它就会毫不客气地出这一着。因此由MIN对棋的结点具有与终点的性质。所以-