南邮自动化人工智能3-确定性推理.ppt

《南邮自动化人工智能3-确定性推理.ppt》由会员分享，可在线阅读，更多相关《南邮自动化人工智能3-确定性推理.ppt（50页珍藏版）》请在三一办公上搜索。

1、3.1 图搜索策略3.2 盲目搜索3.3 启发式搜索3.4 消解原理3.5 规则演绎系统,1,第三章 搜索推理技术,3.6 产生式系统3.7非单调推理3.8小结,问题：知识表示有那些方法？知识表示的目的是什么？构建智能系统的关键是什么？,3.1 图搜索策略,思考：状态空间法的基本特点？基本推理方法？其求解结果是什么？简单回顾实例：猴子与香蕉。,2,用一个四元表列（W，x，Y，z）表示这个问题状态W 猴子的水平位置x 当猴子在箱子顶上时取 x=1；否则取 x=0 Y 箱子的水平位置z 当猴子摘到香蕉时取 z=1；否则取 z=0算符：Goto（U），（W，0，Y，z）goto（U）（U，0，Y，z

2、）Pushbox（V），（W，0，W，z）pushbox（V）（V，0，V，z）Climbbox，（W，0，W，z）climbbox（W，1，W，z）Grasp，（c，1，c，0）grasp（c，1，c，1）,3,3.1 图搜索策略,4,(b，1，b，0),（U，0，b，0）,（V，0，V，0）,（c，1，c，0）,（U，0，V，0）,（c，1，c，1）,（a，0，b，0）,U=b，climbbox,猴子和香蕉问题的状态空间图,提问：人工搜索求解的解答？,目标状态,goto（U）,goto（U）,goto（U）,U=b,pushbox（V）,pushbox（V）,goto（U）,Vc，clim

3、bbox,V=c，climbbox,3.1 图搜索策略,5,猴子和香蕉问题自动演示：,3.1 图搜索策略,思考：计算机的搜索策略？,图搜索控制策略:一种在图中寻找路径的方法。图中每个节点对应一个状态;每条连线对应一个操作符。图搜索过程（GraphSearch）,6,3.1 图搜索策略,7,开始,把S放入OPEN表,OPEN表为空表？,把第一个节点(n)从OPEN表移至CLOSED表,n为目标节点吗？,把n的后继节点放入OPEN表的末端，提供返回节点n的指针,修改指针方向,重排OPEN表,失败,成功,图3.1 图搜索过程框图,是,是,否,否,3.1 图搜索策略,(1),(3),(4),(5),(

4、6),(7),(7),(8),(9),OPEN,CLOSED,(1),(2),宽度优先,图搜索的一般过程如下：,1）建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN 的未扩展节点表中。2）建立一个叫做CLOSED的已扩展节点表，其初始为空表.3）LOOP：若OPEN表是空表，则失败退出。4）选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n5）若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。,8,3.1 图搜索策略,6）扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的

5、这些成员作为n的后继节点添入图G中。7）对那些未曾在G中出现过的M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。8）按某一任意方式或按某个探试值，重排OPEN表。9）GO LOOP。,9,3.1 图搜索策略,图搜索策略,图搜索的实质是从问题空间中找出一张包含目标节点的子图。图搜索的结果：1，一个完整的搜索图G。2一个解路径，用指针表示的解路径。Procedure Graph Search1 G=G0(G0=s),o

6、pen=(s)/s:初始状态2 closed=()3Loop:if open=()then exit(fall)4 nfirst(open)remove(n,open),add(n,closed)5 if goal(n)then exit(success)6mj expand(n),/mj不含n的先辈节点7 openadd(open，mj)/mj不在open，closed中,2023/10/28,10,标记mj每个到n节点指针确定是否需要修改已在open，closed中的每个节点到n的指针确定是否需要修改已在closed中的每个节点的后继节点原来的指针。8 按照某种方式排列open表中的节点，

7、go loop,2023/10/28,11,2023/10/28,12,2023/10/28,13,思考：（1）结果路径的形成中，为什么其节点顺序是明确的？（2）OPEN表中的节点具有什么特点？（3）CLOSED表中的节点具有什么特点？（4）对OPEN表节点的排序有何意义？提出：盲目搜索与启发式搜索。,14,3.1 图搜索策略,3.2 盲目搜索,盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。特点：不需重排OPEN表；种类：宽度优先、深度优先、等代价搜索等。,15,16,S,L,O,M,F,P,Q,N,F,F,F,宽度优先搜索示意图,1）把起始节点放到OPEN表中(如果该起始节点为一

8、目标节点，则求得一个解答)。2）如果OPEN是个空表，则没有解，失败退出；否则继续。3）把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。4）扩展节点n。如果没有后继节点，则转向上述第(2)步。5）把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。6）如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。,17,宽度优先搜索算法：,3.2 盲目搜索,18,开始,把S放入OPEN表,OPEN表为空表？,把第一个节点(n)从OPEN表移至CLOSED表,是否有后继节点为目标节点？,扩展n，把n的后继节点放入OPEN表的

9、末端，提供返回节点n的指针,失败,成功,图3.2 宽度优先算法框图,是,否,是,否,3.2 盲目搜索,思考：与原始算法比较异同，宽度优先的体现？,2023/10/28,19,宽度优先算法,Procedrue breadth-First-Search1 G=G0(G0=s),open=(s),closed=()/s:初始状态2 Loop:if open=()then exit(fall)3 nfirst(open)4 if goal(n)then exit(success)5remove(n,open),add(n,closed)6mj expand(n),/mj不含n的先辈节点7 openad

10、d(open，mj)/mj不在open，closed中,2023/10/28,20,标记每个到n节点指针，按照节点深度递增顺序排列open中的节点 8 go loop 理论上可以利用宽度优先搜索能够找到解，如果问题有解的话。讨论：宽度优先算法和深度优先算法可能出现组合爆炸。都没有利用任何启发式信息，所以称为无信息搜索策略。,2023/10/28,21,：,宽度优先例题：由一张桌子T、三个积木A、B、C组成一个积木世界，初始状态是A在B上，B在桌子上，C在桌子上；目标状态是：A、B、C依次从上到下排列在桌子上。如图,2023/10/28,22,解：1）状态描述（P1，P2，P3）表示按A、B、C

11、顺序依次分别在P1,P2,P3上其中Pi是积木或者桌子。初始状态时（B、T、T）,目标状态 可以表示（B、C、T）2）定义操作:move(x,y)表示将积木x移到Y上；约束条件:a X顶部必须是空的 b 如果Y是积木，Y的顶部必须是空的 c 同一种状态出现不得多于一次。,2023/10/28,23,1）解题过程 2）open表和closed表3）节点样子画出整个图G 和解路径4）程序何时结束 5）改用深度优先如何？,例子八数码难题（8-puzzle problem）,24,（初始状态）,规定：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展26个

12、节点，共生成46个节点之后才求得解（目标节点）。,3.2 盲目搜索,25,3.2 盲目搜索,深度优先搜索(Dephth-first),26,定义：,首先扩展最新产生的(即最深的)节点。,特点：,防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度深度界限。与宽度优先搜索算法最根本的不同在于：将扩展的后继节点放在OPEN表的前端。,3.2 盲目搜索,深度优先搜索示意图,27,S,L,O,M,F,P,Q,N,F,F,F,3.2 盲目搜索,28,开始,把S放入OPEN表,OPEN表为空表？,把第一个节点(n)从OPEN表移至CLOSED表,是否有后继节点为目标节点？,扩展n，把n的后继

13、节点放入OPEN表的前端，提供返回节点n的指针,失败,成功,图3.6 深度优先算法框图,是,否,是,否,3.2 盲目搜索,节点n的深度等于最大深度？,否,2023/10/28,29,深度优先算法,Procedrue depth-First-Search1 G=G0(G0=s),open=(s),closed=()/s:初始状态2 Loop:if open=()then exit(fall)3 nfirst(open)4 if goal(n)then exit(success)5remove(n,open),add(n,closed)6mj expand(n),/mj不含n的先辈节点7 open

14、add(open，mj)/mj不在open，closed中标记mj每个到n节点指针，按照节点深度递减顺序排列open中的节点 8 go loop,示范：有界深度(4)优先的八数码问题深度优先搜索树？,30,3.2 盲目搜索,（初始状态）,31,3.2 盲目搜索,2023/10/28,32,讨论1：如果问题有解，用深度优先搜索算法，是否能够找到解？不一定.解空间是否有限？讨论2：本算法的改进之处是open中节点按照深度优先排列，但是没有对深度加以控制，可能造成搜索代价太大,等代价搜索,33,定义,是宽度优先搜索的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。搜索树中每

15、条连接弧线上的有关代价,表示时间、距离等花费。,算法,在等价搜索算法中，把从节点i到其后续节点j的连接弧线记为c(I,j),把从起始节点S到任一节点I的路径代价记为g(i)。在搜索树上，假设g(i)也是从起始节点S到节点的最少代价路径上的代价。,3.2 盲目搜索,思考：如何动态计算g(i)?,34,开始,把S放入OPEN表,OPEN表为空表？,把具有最小g(i)值的节点i从OPEN表移至CLOSED表,是否有后继节点为目标节点？,失败,成功,图3.8 等代价搜索算法框图,是,否,是,否,令g(s)=0,S是否目标节点？,是,成功,否,3.2 盲目搜索,扩展i，计算其后继节点j的g(j)，并把后

16、继节点放入OPEN表,课后例题讲解,1.设有如图所示的一棵与/或树，请用与/或树的宽度优先搜索及与/或树的深度优先搜索求出解树。,35,解：（1）与/或树的宽度优先搜索先扩展节点A，得到节点B和C；再扩展节点B,得节点t1、t2，因为t1、t2为可解节点，故节点B可解，从而可节点A可解。所以求得解树为：,36,（2）与/或树的深度优先搜索先扩展节点A,得到节点B和C；再扩展节点C,得节点D和t5；t5为可解节点，再扩展节D，得节点t3、t4；t3、t4为可解节点，故节点D可解，因为节点D和t5可解故节点C可解，从而可节点A可解。所以求得解树为：,37,2.下图是5个城市的交通图，城市之间的连线

17、旁边的数字是城市之间路程的费用。要求从A城出发，经过其它各城市一次且仅一次，最后回到A城，请找出一条最优线路。等代价搜索,38,3.3 启发式搜索,启发式信息：用来加速搜索过程的问题领域信息，一般与有关问题具体领域背景有关，不一定具有通用性。启发式搜索：利用启发式信息的搜索方法特点：重排OPEN表，选择最有希望的节点加以扩展种类：有序搜索、A*算法等,39,基本步骤：初始化，判断OPEN表是否为空，选择节点n，判断n是否目标节点，扩展节点n，重排OPEN表、调整指针，循环。各自特点：重排OPEN表的依据不同。盲目搜索可能带来组合爆炸。,思考：（1）图搜索方法的基本步骤？（2）宽度优先、深度优先

18、、等代价方法的特点？（3）盲目搜索的缺点？,有序搜索（Ordered Search）总是选择“最有希望”的节点作为下一被扩展节点估价函数（Evaluation Function）为获得某些节点“希望”的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。f(n)表示节点n的估价函数值 应用节点“希望”程度（估价函数值）重排OPEN表；有序搜索也称为最佳优先搜索；估价函数举例：（1）棋局的得分；（2）距离目标状态的距离量度；（3）TSP问题中的路径；思考：f 函数的计算，重排序的方法？,40,3.3.1 启发式搜索策略和估价函数,3.3 启发式搜索,41,有

19、序搜索（Ordered Search；Bestfirst Search）,实质：选择OPEN表上具有最小 f 值的节点作为下一个要扩展的节点。,3.3 启发式搜索,Nilsson（尼尔逊）方法：一个节点的“希望”越大，则其 f 值越小。被选择的节点是估价函数最小的节点。,思考：如果把宽度优先、深度优先、等代价搜索方法作为有序搜索的特例，那么它们的 f 函数如何计算？举例示范。,42,开始,把S放入OPEN表，计算估价函数 f(s),OPEN表为空表？,选取OPEN表中f值最小的节点i放入CLOSED表,i为目标节点吗？,扩展i，得后继节点j，计算f(j)，提供返回节点i的指针，利用f(j)对O

20、PEN表重新排序，调整亲子关系及指针,失败,成功,图3.9 有序搜索算法框图,是,否,是,否,3.3 启发式搜索,算法,八数码难题,43,（2）如下的八数码难题（8-puzzle problem）,（3）八数码难题的有序搜索树见下图：,3.3 启发式搜索,（1）估价函数设置：f(n)=d(n)+W(n)d(n):节点n的深度；W(n):错放的棋子数,44,3.3 启发式搜索,f 函数的重要性有序搜索的有效性直接取决于 f,是提高搜索效率的关键；如果 f 不准确，可能失去最佳解，也可能失去全部解；f 一般选择策略搜索时间与空间的折衷；保证有解或有最佳解；f 选择的三种典型情况：（1）最优解答：状

21、态空间中有多条解答路径，求解最优解答，如A*算法；（2）搜索代价与解答质量的综合：问题类似于（1），但搜索过程可能超出时间与空间的界限。在适当的搜索实验中找到满意解答，并限制满意解答与最优解答的差异程度；如：TSP问题；（3）最小搜索代价：不考虑解答的最优化（只有一个解答或多个解答间无差异），尽量使搜索代价最小；如：定理证明。思考：（1）f 不能识别某些节点的真实“希望”值会怎么样？（2）f 过多估计了全部节点又会怎么样？,45,3.3 启发式搜索,3.3.3 A*算法,思考：经过节点n的最佳路径，怎么表示？怎么求解最优解答路径。估价函数f*：对节点n定义f*(n)=g*(n)+h*(n),表

22、示从S开始通过节点n的一条最佳路径的代价。其中g*(n)表示从起始节点S到n的最佳路径，h*(n)表示从n到某目标节点的最佳路径。估价函数f：f(n)=g(n)+h(n)；其中g是g*的估计，h是h*的估计；g 的一个选择就是搜索树中从 S 到 n 的这段路径的代价；显然有g(n)g*(n)；h 的依赖于领域的启发信息，比如八数码问题中的 W(n),h 称为启发式函数；,46,3.3 启发式搜索,A*算法：定义1 在GRAPHSEARCH过程中，如果第8步的重排OPEN表是依据f(x)=g(x)+h(x)进行的，则称该过程为A算法。定义2 在A算法中，如果对所有的x存在h(x)h*(x),则称

23、h(x)为h*(x)的下界，它表示某种偏于保守的估计。定义3 采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。当h=0时，A*算法就变为等代价搜索算法。,47,A*算法总框图,48,开始,把S放入OPEN表，记 f=h,OPEN=NIL?,失败,BESTNODE是目标节点？,成功,扩展BESTNODE，产生后续节点SUCCESSOR,否,否,是,是,A*子过程,选取OPEN表上未设置过的具有最小 f 值的节点BESTNODE,放入CLOSED表中,49,SUC属于OPEN？,SUC属于CLOSED？,SUC=OLD，把它添加到BESTNODE的后续节点表中,g(SUC)g(OLD)?,重新确定OLD的父辈节点为BESTNODE，并修订父辈节点的g、f值，记下g（OLD）,计算f的值,把SUCCESSOR放入OPEN表，添进BESTNODE的后裔表,是,否,是,否,否,是,计算g(SUC)=g(BES)+h(BES,SUC),建立从SUCCESSOR返回BESTNODE的指针,A*算法子过程,思考：（1）宽度优先搜索、深度优先搜索与等代价搜索的关系？（2）有序与A*算法等搜索方法的关系？（3）等代价搜索与A*算法的关系？基于状态空间搜索算法的智能系统应用领域：问题求解（智能问题）：迷宫下棋软件：国际象棋，围棋，中国象棋等策略游戏：RPG，,50,