《人工智能》搜索技术.ppt

第四章 搜索技术,状态空间法 问题归约法 博弈树搜索 局部搜索,How to find the best path in game ?,迷宫问题,s-s s s s s s-s-s-s s-s-s-s s s s s s s s-s-s-s-s,S0,Sg,搜索的挑战组合爆炸,魔方问题 博弈问题 皇后问题 行商问题 排课问题（调度问题） 背包问题 ,数码问题,（初始状态）,八数码难题（8-puzzle problem）,4.1 状态图概念,状态图的概念 状态图(状态空间图)实际上是一类问题的抽象表示。 许多智力问题(八数码问题、梵塔问题、旅行商问题、八皇后问题、农夫过河问题等)。 实际问题（如路径规划、定理证明、演绎推理、机器人行动规划等）都可以归结为在某一状态图中寻找目标或路径的问题。,农夫过河问题,有一个农夫带一条狼、一只羊和一棵白菜过河。如果没有农夫看管，则狼要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？,农夫过河问题状态空间法表示,以向量（人，狼，羊，菜）表示状态，其中每个变元可取0或1，取0表示在左岸（出发点），取1表示在右岸 初态是：（0，0，0，0） 终态是：（1，1，1，1） 非法中间状态有： （0，0，1，1），（0，1，1，0），（0，1，1，1）， （1，1，0，0），（1，0，0，1），（1，0，0，0）。,（1，0，0，1）,4.2 状态空间法,问题的状态空间表示(状态图表示) 状态空间的三元组(S, O, G)表示. S:初始状态集合; O: 操作集合; G:目标状态集合 状态空间的搜索策略(状态图搜索) 广度优先搜索, 深度优先搜索, 启发式搜索,状态空间表示的概念,例如下棋、迷宫及各种游戏。,Middle State,Goal State,三数码难题,初始棋局,目标棋局,1,八数码难题的宽度优先搜索树,状态图搜索,图搜索是指在状态图中寻找目标或路径的搜索。 所谓搜索，顾名思义，就是从初始节点出发，沿着与之相连的边试探地前进，寻找目标节点的过程(也可以反向进行)。,问题,状态图,搜索,解,解是由初始状态到目标状态的路径,状态图搜索相关问题,状态选择 解的性质：存在、分布、质量 搜索策略,图搜索策略,图搜索控制策略 一种在状态图中寻找路径的方法。 图中每个节点对应一个状态，每条连线对应一个操作符。 图搜索涉及两个主要数据结构： open表 closed表,OPEN 表,OPEN表是一种动态数据结构，专门登记当前待考查（待访问）的节点，也叫未扩展节点表 。,OPEN表,open表中，每个节点信息还包括指向父节点的返回指针（即父节点地址）,CLOSED 表,Closed表是一种动态数据结构，记录访问过的节点，也叫已扩展节点表 ，其初始为空表。,CLOSED表,开始,把S放入OPEN表,OPEN表为空表？,把第一个节点(n)从OPEN表移至CLOSED表,n为目标节点吗？,把n的后继节点放入OPEN表的末端，提供返回节点n的指针,修改指针方向,重排OPEN表,失败,成功,图搜索过程框图,是,是,否,否,搜索策略即体现在这里,按搜索轨迹分类,图式搜索：搜索过程中，搜索路径允许形成回路。 树式搜索：搜索过程中，搜索路径不允许形成回路。 线式搜索：扩展节点每次只扩展一个节点。,S,G,S,G,搜索树的概念,一个可以搜索出某个可行解的问题，如“农夫、白菜、羊、狼”和“八数码难题”等，虽然从表面上看上去和“树”这种结构无关，但是整个搜索过程中的可能试探点所行成的搜索空间总可以对应到一颗搜索树上去。 将各类形式上不同的搜索问题抽象并统一成为搜索树的形式，为算法的设计与分析带来巨大的方便。,（1，0，0，1）,由于搜索具有探索性，所以要提高搜索效率(尽快地找到目标节点)，或要找最佳路径(最佳解)就必须注意搜索策略。 对于状态图搜索，已经提出了许多策略，它们大体可分为盲目搜索（bland search)和启发式搜索（heuristic search）两大类。 盲目搜索是无向导搜索。 启发式搜索是有向导搜索，即利用启发信息（函数）引导去寻找问题解。,搜索策略分类,盲目搜索,盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。 种类： 宽度优先搜索 深度优先搜索 等代价搜索,图搜索策略,宽度优先,深度优先,启发式搜索,一种在图中寻找路径的方法。,宽度优先搜索策略,优先搜索状态空间中离初始状态近的节点(状态 特点:具有完备性, 占用空间 搜索算法 数据结构: OPEN表 : 先进先出队列,存放待扩展的节点. 节点(状态) 父节点编号(返回指针) CLOSED表 : 存放已被扩展过的节点. 编号 节点 父节点编号,开始,把S放入OPEN表,OPEN表为空表？,把第一个节点(n)从OPEN表移至CLOSED表,是否有后继节点 为目标节点？,扩展n，把n的后继节点放入OPEN表的末端，提供返回节点n的指针,失败,成功,宽度优先算法框图,是,否,是,否,算法,否,宽度优先搜索算法,Step1: 把初始节点S0放入OPEN表中; Step2: 若OPEN表为空,则搜索失败,退出. Step3: 移出OPEN表中第一个节点N放入CLOSED表 中, 并标以顺序号n; Step4: 若目标节点Sg=N, 则搜索成功,结束. Step5: 若N不可扩展, 则转Step2; Step6: 扩展N, 将生成的一组子节点配上指向N的指针后, 放入OPEN表尾部, 转 Step2;,例子 八数码难题（8-puzzle problem）,（初始状态）,规定：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。 从图可见，要扩展26个节点，共生成26个节点之后才求得解（目标节点）。,1,图 八数码难题的宽度优先搜索树,宽度优先搜索(Breadth-First Strategy),新的节点被插入到栈OPEN的后部,1,OPEN= (1),CLOSED=( ),6,7,8,9,10,11,12,13,14,15,宽度优先搜索(Breadth-First Strategy),新的节点被插入到栈OPEN的后部,1,OPEN= (2,3),CLOSED=(1 ),6,7,8,9,10,11,12,13,14,15,宽度优先搜索(Breadth-First Strategy),新的节点被插入到栈OPEN的后部,1,OPEN= (3,4,5),CLOSED=(1,2 ),6,7,8,9,10,11,12,13,14,15,宽度优先搜索(Breadth-First Strategy),新的节点被插入到栈OPEN的后部,1,OPEN= (4,5,10,11),CLOSED=(1,2,3 ),6,7,8,9,10,11,12,13,14,15,宽度优先搜索(Breadth-First Strategy),新的节点被插入到栈OPEN的后部,1,OPEN= (5,10,11,6,7),CLOSED=(1,2,3,4 ),6,7,8,9,10,11,12,13,14,15,宽度优先搜索(Breadth-First Strategy),新的节点被插入到栈OPEN的后部,1,OPEN= (10,11,6,7,8,9),CLOSED=(1,2,3,4,5 ),6,7,8,9,10,11,12,13,14,15,宽度优先搜索(Breadth-First Strategy),新的节点被插入到栈OPEN的后部,1,OPEN= (11,6,7,8,9, 12,13),CLOSED=(1,2,3,4,5,10 ),6,7,8,9,10,11,12,13,14,15,深度优先搜索策略,新节点优先扩展, 直到达到一定的深度限制.若找不到目标或无法在扩展时,回溯到另一节点继续扩展. 特点: 需要深度限制, 需要回溯控制, 省空间 探索算法: 数据结构: OPEN表 : 后进先出队列,存放待扩展的节点. CLOSED表 : 存放已被扩展过的节点. 除扩展后的子节点应放入到OPEN表的首部以外,与宽度优先算法一样.,深度优先算法框图,算法,开始,把S放入OPEN表,OPEN表为空表？,把第一个节点(n)从OPEN表移至CLOSED表,是否有后继节点 为目标节点？,扩展n，把n的后继节点放入OPEN表的前端，提供返回节点n的指针,失败,成功,是,否,是,否,深度优先搜索算法,Step1: 把初始节点S0放入OPEN表中; Step2: 若OPEN表为空,则搜索失败,退出. Step3: 移出OPEN中第一个节点N放入CLOSED表 中, 并标以顺序号n; Step4: 若目标节点Sg=N, 则搜索成功,结束. Step5: 若N不可扩展, 则转Step2; Step6: 扩展N, 将生成的一组子节点配上指向N的指针后, 放入OPEN表首部, 转 Step2;,深度优先搜索(Depth-First Strategy),新的节点被插入到栈OPEN的前部,1,CLOSED=( ),6,7,8,9,10,11,12,13,14,15,Depth-First Strategy,新的节点被插入到栈OPEN的前部,1,CLOSED=( 1 ),6,7,8,9,10,11,12,13,14,15,Depth-First Strategy,新的节点被插入到栈OPEN的前部,1,CLOSED=( 1,2 ),6,7,8,9,10,11,12,13,14,15,Depth-First Strategy,新的节点被插入到栈OPEN的前部,1,CLOSED=( 1,2,4 ),6,7,OPEN = (6,7, 5, 3),8,9,10,11,12,13,14,15,Depth-First Strategy,新的节点被插入到栈OPEN的前部,1,6,7,8,9,10,11,CLOSED=( 1,2,4,6 ),OPEN = (7, 5, 3),12,13,14,15,Depth-First Strategy,新的节点被插入到栈OPEN的前部,1,6,7,8,9,10,11,CLOSED=( 1,2,4,6,7 ),OPEN = (5, 3),12,13,14,15,Depth-First Strategy,新的节点被插入到栈OPEN的前部,1,2,3,4,5,6,7,8,9,10,11,CLOSED=( 1,2,4, 5,6,7 ),OPEN = (8,9,3),12,13,14,15,Depth-First Strategy,新的节点被插入到栈OPEN的前部,1,6,7,8,9,10,11,CLOSED=( 1,2,4,5, 6,7 ,8),OPEN = (9, 3),12,13,14,15,Depth-First Strategy,新的节点被插入到栈OPEN的前部,1,6,7,8,9,12,10,11,13,14,15,CLOSED=( 1,2,4, 5,6,7, 8,9),OPEN = (3),Depth-First Strategy,新的节点被插入到栈OPEN的前部,1,6,7,8,9,12,10,11,13,14,15,CLOSED=( 1,2,4, 5,6,7,8,9,3),OPEN = (10,11),Depth-First Strategy,新的节点被插入到栈OPEN的前部,1,6,7,8,9,10,11,CLOSED=( 1,2,4, 5,6,7,8,9,3,10),12,13,14,15,OPEN = (12,13,11),代价树搜索,代价树：搜索树中每条连接弧线上的有关代价,表示时间、距离等花费。 代价树搜索（等代价搜索） ：是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。,*若所有连接弧线具有相等代价，则简化为宽度优先搜索算法。,算法使用符号,c(i,j)：把从节点i到其后继节点j的连接弧线代价记为c(i,j) g(i)：把从起始节点S到任一节点i的路径代价记为g(i). 在搜索树（非循环路径）上，假设g(i)是从起始节点S到节点i的最少路径上的代价。 等代价搜索方法以g(i)的递增顺序扩展其节点。,开始,把S放入OPEN表,OPEN表为空表？,把具有最小g(i)值的节点i从OPEN表移至CLOSED表,是否有后继节点 为目标节点？,失败,成功,等代价搜索算法框图,是,否,是,否,令g(s)=0,S是否目标节点？,是,成功,否,开始,把S放入OPEN表,OPEN表为空表？,把具有最小g(i)值的节点i从OPEN表移至CLOSED表,是否有后继节点 为目标节点？,失败,成功,是,是,否,令g(s)=0,S是否目标节点？,是,成功,开始,把S放入OPEN表,OPEN表为空表？,把具有最小g(i)值的节点i从OPEN表移至CLOSED表,是否有后继节点 为目标节点？,失败,成功,是,是,否,令g(s)=0,S是否目标节点？,是,成功,扩展i，计算其后继节点j的g(j)，并把后继节点放入OPEN表,开始,把S放入OPEN表,OPEN表为空表？,把具有最小g(i)值的节点i从OPEN表移至CLOSED表,是否有后继节点 为目标节点？,失败,成功,是,是,否,令g(s)=0,S是否目标节点？,是,成功,等代价搜索算法,（1） 把起始节点放到未扩展节点表OPEN中。如果此起始节点为一目标节点，则求得一个解；否则令g（S）=0。 （2） 如果OPEN是个空表，则没有解而失败退出。 （3） 从OPEN 表中选择一个节点i，使其g（i）为最小。如果有几个节点都合格，那么就要选择一个目标节点作为节点 i（要是有目标节点的话）；否则，就从中选一个作为节点i。把节点i从OPEN表移至扩展节点表CLOSED中。 （4） 如果节点i为目标节点，则求得一个解。 （5） 扩展节点i。如果没有后继节点，则转向第（2）步。 （6） 对于节点i的每个后继节点j，计算g（j）=g（i）+c（i,j），并把所有后继节点j放进OPEN表。提供回到节点i的指针。 （7） 转向第（2）步。,g1,g2,g3,g4,等代价搜索,等代价搜索：沿等代价路径 断层进行扩展,比较宽度优先搜索与等代价搜索,等代价搜索算法,在每一步, 选择具有最低累计权值的点进行扩展,启发式搜索,盲目搜索的问题： “组合爆炸” 利用问题的某些控制信息(如解的特征)来引导搜索.这种控制信息称为搜索的启发信息. 利用启发式信息定义节点的启发函数 h(n) 特点: 深度优先, 效率高, 无回溯, 但不能保证得到最佳解 。 探索算法: 全局择优搜索(最好优先搜索), 局部择优搜索 数据结构：OPEN表 、 CLOSED表,启发信息 启发式搜索就是利用启发性信息进行制导的搜索。 启发性信息就是有利于尽快找到问题之解的信息。 按其用途划分，启发性信息一般可分为以下三类： (1)用于扩展节点的选择，即用于决定应先扩展哪一个节点，以免盲目扩展。 (2)用于生成节点的选择，即用于决定应生成哪些后续节点，以免盲目地生成过多无用节点。 (3)用于删除节点的选择，即用于决定应删除哪些无用节点，以免造成进一步的时空浪费。,重排OPEN表，使搜索沿某个被认为最有希望的路径扩展。 应用这种排序过程，需要某些估算节点“希望”的量度。 用来估算节点希望程度的量度，叫做估价函数（evaluation function），有时也叫作启发函数。 一个节点的“希望”（promise）有几种不同 的定义方法。 在状态空间问题中，一种方法是估算目标节点到此节点的距离； 估算全路径的长度或难度（包括此节点）。 我们用符号f来标记估价函数，用f（n）表示节点n的估价函数值。,启发函数,如何定义一个估价（启发）函数呢？估价（启发）函数并无固定的模式，需要具体问题具体分析。通常可以参考的思路有： （1） 一个节点到目标节点的距离或差异的度量； （2）一个节点处在最佳路径上的概率； （3）或者根据经验的主观打分。,启发函数,八数码难题（8-puzzle）,f1(T) = 恰好正确地处在目标状态的字码数目:,从实用角度，计算与目标的距离更有实际意义！,目标：,f3(T) = 不在目标位置的字码距离目标位置水平距离和垂直距离之和。 该函数给出了一个更好的距离评估,= 1 + 1 + 2 + 2 = 6,目标：,启发式搜索算法 启发式搜索要用启发函数来导航，其搜索算法就要在状态图一般搜索算法基础上再增加启发函数值的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。两种策略: 局部择优搜索 扩展节点N后仅对N的子节点按启发函数值大小以升序排序，再将它们依次放入OPEN表的首部。 全局择优搜索 在OPEN表中保留所有已生成而未考察的节点，并用启发函数h(x)对它们全部进行估价，从中选出最优节点进行扩展，而不管这个节点出现在搜索树的什么地方。,全局择优搜索算法,Step1: 把初始节点S0放入OPEN表中,计算h(S0); Step2: 若OPEN表为空,则搜索失败,退出. Step3: 移出OPEN中第一个节点N放入CLOSED表 中, 并标以顺序编号n; Step4: 若目标节点Sg=N, 则搜索成功,结束. Step5: 若N不可扩展, 则转Step2; Step6: 扩展N,计算每个子节点的函数值h(x),将所有子节点配上指向N的返回指针后放入OPEN表中, 再按函数值的升序重新排序OPEN表中的节点, 转 Step2;,全局择优搜索例子,九宫重排问题, 定义评价函数; h(n):目标格局与现格局(Sn)相比,位置不同的牌数 . 初始格局S0 目标格局Sg 2 8 3 1 2 3 1 4 = 8 4 7 6 5 7 6 5 h(S0) = 3,局部择优搜索算法,Step1: 把初始节点S0放入OPEN表中,计算h(S0); Step2: 若OPEN表为空,则搜索失败,退出. Step3: 移出OPEN中第一个节点N放入CLOSED表 中, 并标以顺序编号n; Step4: 若目标节点Sg=N, 则搜索成功,结束. Step5: 若N不可扩展, 则转Step2; Step6: 扩展N,计算每个子节点的函数值h(x),并将所有子节点按函数值的升序排序后, 配上指向N的返回指针放入OPEN表的首部, 转 Step2;,局部搜索算法,特点： 从单独的一个当前状态出发，通常只移动到与之相邻的状态，并且不保留解的路径。 优点： 需要很少的内存 经常能在很大或无限的状态空间中找到合理的解,爬山法（Hill climbing）,一种基本的局部启发式搜索方法 基本算法：扩展节点N后仅对N的子节点按启发函数值大小以升序排序，再将选择启发函数值最小的节点放入OPEN表的首部。（启发函数值越小离目标越近） 相当于深度优先算法+启发式搜索 线式搜索，不能回溯 向目标值增加的方向持续移动,启发式搜索:A算法,评价函数 f(x) = g(x) + h(x)，表示通过节点x的估计代价值。,n,m,S,G,g(n),g(m),h(n),h(m),比较f(n)和f(m) 大小，决定节点搜索顺序，即在OPEN表中的顺序,启发式搜索:A算法,评价函数 f(x) = g(x) + h(x) 当f(x) = g(x) 时，为宽度优先搜索 当f(x) = 1/g(x)时，为深度优先搜索 当f(x) = h(x) 时，为全局优先搜索,n,m,S,G,g(n),g(m),h(n),h(m),启发式搜索:A算法,评价函数的一般形式 : f(n) = g(n) + h(n) g(n):从S0到Sn的实际代价(搜索的横向因子) h(n):从N到目标节点的估计代价,称为启发函数 (搜索的纵向因子); 特点: 效率高, 无回溯, 搜索算法 OPEN表 : 存放待扩展的节点. CLOSED表 : 存放已被扩展过的节点.,启发式搜索:A算法,Step1: 把附有计算f(S0)初始节点S0放入OPEN表中; Step2: 若OPEN表为空,则搜索失败,退出. Step3: 移出OPEN中第一个节点N放入CLOSED表中, 并标以顺序编号n; Step4: 若目标节点Sg=N, 则搜索成功,结束. Step5: 若N不可扩展, 则转Step2; Step6: 扩展N, 生成一组附有f(x)的子节点,作完以下处理后,将余下子节点配上指向N的返回指针后放入OPEN表中, 再按函数值的升序重新排序OPEN表中的节点, 转 Step2; 删除重复节点和修改返回指针.,八数码难题（8-puzzle problem）,A算法的应用,八数码难题:评价函数,简单的评价函数 h(n)=d(n)+W(n) 其中：d(n)是搜索树中节点n的深度；W(n)用来计算对应于节点n的数据库中错放的棋子个数。,初始棋局f值等于0+4=4,5,7,2,3,4,5,1,八数码难题的搜索树,5,启发式搜索:A*算法,评价函数的一般形式: f(n) = g(n) + h(n) 且 h(n) = h*(n) g(n),h(n):定义同A算法; h*(n):从N到目标节点的最短路径; 称此时的A算法为A*算法. A*算法的特征: A*是可采纳的:只要最短路径存在,就一定能找出. 如果有 h1(n) = h2(n) = h*(n), 那么h2比h1展开更少的节点. 广度优先搜索是当h(n)=0时的A*算法的特例.,启发式搜索:A*算法,评价函数 f(x) = g(x) + h(x) ( 当h(n) = h*(n) ),n,S,G,g(n)=g*(n),h(n) = h*(n),A*算法要求保守估计： f(n) = f*(n),A*算法的定义,定义1 在图搜索过程中，如果重排OPEN表是依据f(x)=g(x)+h(x)进行的，则称该过程为A算法。 定义2 在A算法中，如果对所有的x存在h(x)h*(x)（低估）,则称h(x)为h*(x)的下界，它表示某种偏于保守的估计。 定义3 采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。,具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法的充分条件,1) 搜索树上存在着从起始点到终了点的最优路径。 2) 问题域是有限的。 3）所有结点的子结点的搜索代价值0。 4)： h(n)=h*(n),为什么A*算法低估h值,在A*算法中，对所有的x存在h(x)h*(x)（低估) 在A*算法中,只有对h值低估才能获得优化的搜索性能,为什么A*算法低估h值,举例：,在多估情况下：,为什么A*算法低估h值,举例：,如果h被低估:,2+1,启发式搜索算法A*,Step1: 把初始节点S0放入OPEN表中; Step2: 若OPEN表为空,则搜索失败,退出. Step3: 移出OPEN中第一个节点N放入CLOSED表 中, 并标以顺序号n; Step4: 若目标节点Sg=N, 则搜索成功,结束. Step5: 若N不可扩展, 则转Step2; Step6: 扩展N, 生成一组子节点, 对这组子节点作如下处 理后, 放入OPEN表, 按评价函数的升序重新排序 OPEN表, 转 Step2; 删除重复节点和修改返回指针处理.,八数码难题:,h1(T) 0 启发函数为0,注意: h3(T) h2(T) h1(T),目标：,曼哈顿距离,八数码难题举例,Robot navigation,Cost of one horizontal/vertical step = 1 Cost of one diagonal step = 2,f(N) = g(N) + h(N), with h(N) =距离目标位置水平距离和垂直距离之和,Robot Navigation,Robot Navigation,f(N) = h(N), with h(N) =距离目标位置水平距离和垂直距离之,Robot Navigation,0,2,1,1,5,8,7,7,3,4,7,6,7,6,3,2,8,6,4,5,2,3,3,3,6,5,2,4,4,3,5,5,4,6,5,6,4,5,f(N) = h(N), with h(N) =距离目标位置水平距离和垂直距离之,7,0,Robot Navigation,f(N) = g(N)+h(N), with h(N) = 距离目标位置水平距离和垂直距离之和,7+0,8+1,搜索算法小结,树搜索-盲目搜索-广度优先搜索 -深度优先搜索-有界深度优先 -代价树搜索 -启发式搜索-全局择优搜索(最好优先) -局部择优搜索(爬山法) -A算法( 基于: f(n)=g(n)+h(n) ) A*算法(最佳搜索: h(n) =h*(n),复习,什么是宽度优先、深度优先、代价树搜索？ 什么是启发信息、启发函数？ 什么是盲目搜索和启发式搜索？ 什么是A算法和A*算法？ A*算法有什么特点？,讨论,判断：A*算法中 1 比目标节点远的节点都不会被展开； 2 比目标节点近的节点都会被展开； 3 解是唯一的； 4 搜索的时间复杂度是指数的。 设评价函数为 f(N) =g(N) + h(N), 怎样才能保证搜索到最优解？设 f12(N) =K1 g(N) + K2 h(N)，讨论K1 ,K2对搜索结果的影响？ 如何进一步提高搜索效率？（双向、多起点、非确定),八数码难题（8-puzzle problem） 用A*算法搜索， 给出搜索树。,课堂练习,1 试用A*算法（ h(N) =距离目标位置水平距离和垂直距离之和）f(N) = g(N)+h(N) 对下图进行搜索,作业,规定允许动作：左、上、右、下,作业,利用启发式搜索，找出以下问题的解，并说明是否是最优解？（可选） 2 1 6 1 2 3 4 8 = 8 4 7 5 3 7 6 5 请针对TSP问题，提出启发式搜索策略，并对搜索效率进行分析？,4.3 问题归约法,问题归约的概念 问题归约的描述: 三元组(S0, O, P)表示. S0:初始问题; P:本原问题集合 O:操作算子集;将问题化成若干子问题. 问题归约的最终目标: 原问题 = 本原问题 状态空间法是问题归约法的特例. 问题归约的与或图表示,与或图表示,A,A,C6,C5,C4,C3,C2,C1,C6,C5,C4,C3,C2,C1,m1,m2,或节点,与节点,叶节点(或称:端节点),3连接弧,节点的可解性判别,A,C6,C5,C4,C3,C2,C1,m1,m2,或节点,与节点,可解节点的判别条件 叶节点可解 或节点可解当且仅当至少有一个子节点可解. 与节点可解当且仅当所有子节点都可解. 不可解节点的判别条件 没有子节点的非终止节点 或节点不可解当且仅当所有子节点不可解. 与节点不可解当且仅当至少有一个子节点不可解.,与或图的搜索,A,C6,C5,C4,C3,C2,C1,m1,m2,或节点,与节点,解图,求解与或图问题就是在与或图中搜索解图(或解树)的问题. 解图是原与或图的一个子图(与图) 搜索策略:无信息搜索与启发式搜索 搜索过程: 标记初始节点为可解节点(成功)或不可解节点(失败)的过程. 搜索算法:,与或树的搜索算法,1,Step1: S0 = OPEN表 Step2: OPEN -N- CLOSED (n) Step3: 如N可扩展: 扩展N=OPEN 标记可解节点=CLOSED 如初始节点可解,搜索成功,结束. 删去OPEN中有可解先辈的节点. Step4: N不可扩展: 标记不可解节点.如初始节点不可解, 搜索失败,退出. 删去OPEN中有不可解先辈的节点. To Step2.,5,4,A,t2,t3,t4,2,t1,B,3,问题归约的例子,积分问题的与或树 三阶梵塔问题的与或树 几何定理证明的与或树,4.4 博弈树搜索,博弈树的概念 博弈:下棋, 打牌等一类竞争性智力活动.最简单的是“二人零和,全信息,非偶然”博弈. 博弈树:描述博弈过程的与或树. 特点: 或与节点分层交替出现; 搜索空间指数增长,只能前推几步 极大极小过程 剪枝技术,(7,min) (6,1,max) (5,2,max) (4,3,max) (5,1,1,min) (4,2,1min) (3,2,2,min) (3,3,1,min) (4,1,1,1,max) (3,2,1,1,mix) (2,2,2,1,max) max 失败 (3,1,1,1,1,min) (2,2,1,1,1,min) min失败 (2,1,1,1,1,1,max) max失败 分币原则:每次要将一堆分为币数不等的两堆 . 胜负标准:交替分钱币,谁不能再分谁输.,分钱币游戏的博弈树,结论: ?,(7,min) (6,1,max) (5,2,max) (4,3,max) (5,1,1,min) (4,2,1min) (3,2,2,min) (3,3,1,min) (4,1,1,1,max) (3,2,1,1,max) (2,2,2,1,max) max失败 (3,1,1,1,1,min) (2,2,1,1,1,min) min失败 (2,1,1,1,1,1,max) max失败 . max 可解节点 min可解节点,分钱币游戏的博弈树,结论: max必胜,钱币为8，9时，结论如何？ 钱币为10 时，结论如何？ 钱币为 x 时，结论如何？,分钱币游戏思考题,极大极小过程,B,A,I,H,G,F,C,Q,P,O,N,M,L,K,I,E,D,MAX,MIN,2 8 1 3 -2 5 7 -1 1,R,2,5,-2,2,2,-1,5,倒推过程,-剪枝技术,B,A,I,H,G,F,C,Q,P,O,N,M,L,K,I,E,D,MAX,MIN,2 8 1 3 -2 5 7,R,2,5, 1,MAX节点的下界 2,MIN节点的上界2,5,剪枝,剪枝,-剪枝技术,MAX节点的倒退值 : 取后继节点估值的最大值. MAX节点的倒推下界值. MIN节点的倒退值 : 取后继节估值点的最小值. MIN节点的倒推上界值. 剪枝: 当MIN节点的值 祖先MAX节点的值时,不必展开MIN的其余子节点. 剪枝: 当MAX节点的值 祖先MIN节点的值时,不必展开MAX的其余子节点.,讨论,局部优先搜索与全局优先搜索的区别是什么? 什么是启发式搜索？A算法？A*算法？ 博弈树有什么特点? 利用博弈树分析九枚分钱币游戏的可能结论? -,4.5 局部搜索(Local Search)*,通过在当前解近旁的搜索,不断改善当前解,最终搜索到满足要求的最优解或次优解. 一般过程 Step1: 初始化. 求初始解x0=当前解x, k=1; Step2: 完善解. 在x的近旁N(x)中如果有更好解y, 则 更新解x:=y, k:=k+1; To Step2 否则,输出x, 停止搜索. 被用于大规模N-queen, SAT等问题的求解.,局部搜索法,初始解x0,x3,x4,x1,x2,x5,N(x0),N(x1),N(x5),局部搜索法的特征,局部搜索的要素 评价函数的确定 初始解的确定 N(x)的确定 解更新的方法 终止条件 特点：简单,高效,但不完备-局部最优解 改进方法:多起点、加入非确定性、 加入从局部最优解脱出的方法,Nqueen问题的求解,Q,Q,Q,Q,Q,Q,Q,Q,Nqueen问题的求解,(皇后 N,方案数): (4,2)