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

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=0Y箱子的程度位置z 当猴子摘到香蕉时取z=1；否那么取z=0算符：Goto〔U〕，〔W，0，Y，z〕goto〔U〕〔U，0，Y，z〕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〕33.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〕V≠c，climbboxV=c，climbbox3.1图搜索战略5猴子和香蕉问题自动演示：

猴子香蕉箱子

猴子香蕉箱子

Ha!Ha!3.1图搜索战略思索：计算机的搜索战略？图搜索控制战略:一种在图中寻觅途径的方法。图中每个节点对应一个形状;每条连线对应一个操作符。图搜索过程〔GraphSearch〕63.1图搜索战略7开场把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目的节点吗？把n的后继节点放入OPEN表的末端，提供前往节点n的指针修正指针方向重排OPEN表失败胜利图3.1图搜索过程框图是是否否3.1图搜索战略(1)(3)(4)(5)(6)(7)(7)(8)(9)OPENCLOSED(1)(2)宽度优先图搜索的普经过程如下：1〕建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中。2〕建立一个叫做CLOSED的已扩展节点表，其初始为空表.3〕LOOP：假设OPEN表是空表，那么失败退出。4〕选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n5〕假设n为一目的节点，那么有解并胜利退出，此解是追踪图G中沿着指针从n到S这条途径而得到的(指针将在第7步中设置)。83.1图搜索战略6〕扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。7〕对那些未曾在G中出现过的M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对曾经在OPEN或CLOSED表上的每一个M成员，确定能否需更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定能否需求更改图G中通向它的每个后裔节点的指针方向。8〕按某一恣意方式或按某个探试值，重排OPEN表。9〕GOLOOP。93.1图搜索战略图搜索战略图搜索的本质是从问题空间中找出一张包含目的节点的子图。图搜索的结果：1，一个完好的搜索图G。2一个解途径，用指针表示的解途径。ProcedureGraphSearch1G=G0(G0=s),open=(s)//s:初始形状2closed=()3Loop:ifopen=()thenexit(fall)4n←first(open)remove(n,open),add(n,closed)5ifgoal(n)thenexit(success)6{mj}←expand(n),//mj不含n的先辈节点7open←add(open，mj)//mj不在open，closed中2024/1/1510标志mj每个到n节点指针确定能否需求修正已在open，closed中的每个节点到n的指针确定能否需求修正已在closed中的每个节点的后继节点原来的指针。8按照某种方式陈列open表中的节点，goloop2024/1/15112024/1/15122024/1/1513思索：〔1〕结果途径的构成中，为什么其节点顺序是明确的？〔2〕OPEN表中的节点具有什么特点？〔3〕CLOSED表中的节点具有什么特点？〔4〕对OPEN表节点的排序有何意义？提出：盲目搜索与启发式搜索。143.1图搜索战略3.2盲目搜索盲目搜索又叫做无信息搜索，普通只适用于求解比较简单的问题。特点：不需重排OPEN表；种类：宽度优先、深度优先、等代价搜索等。153.2.1宽度优先搜索〔Breadth-first〕定义：以接近起始节点的程度逐层扩展节点的搜索方法。特点：一种高代价搜索，但假设有解存在，那么必能找到它。16SLOMFPQNFFF宽度优先搜索表示图1〕把起始节点放到OPEN表中(假设该起始节点为一目的节点，那么求得一个解答)。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表的末端，提供前往节点n的指针失败胜利图3.2宽度优先算法框图是否是否3.2盲目搜索思索：与原始算法比较异同，宽度优先的表达？2024/1/1519宽度优先算法Procedruebreadth-First-Search1G=G0(G0=s),open=(s),closed=()//s:初始形状2Loop:ifopen=()thenexit(fall)3n←first(open)4ifgoal(n)thenexit(success)5remove(n,open),add(n,closed)6{mj}←expand(n),//mj不含n的先辈节点7open←add(open，mj)//mj不在open，closed中2024/1/1520

标志每个到n节点指针，按照节点深度递增顺序陈列open中的节点8goloop实际上可以利用宽度优先搜索可以找到解，假设问题有解的话。讨论：宽度优先算法和深度优先算法能够出现组合爆炸。都没有利用任何启发式信息，所以称为无信息搜索战略。2024/1/1521：宽度优先例题：由一张桌子T、三个积木A、B、C组成一个积木世界，初始形状是A在B上，B在桌子上，C在桌子上；目的形状是：A、B、C依次从上到下陈列在桌子上。如图2024/1/1522解：1〕形状描画〔P1，P2，P3〕表示按A、B、C顺序依次分别在P1,P2,P3上其中Pi是积木或者桌子。初始形状时〔B、T、T〕,目的形状可以表示〔B、C、T〕2〕定义操作:move(x,y)表示将积木x移到Y上；约束条件:aX顶部必需是空的b假设Y是积木，Y的顶部必需是空的c同一种形状出现不得多于一次。2024/1/15231〕解题过程2〕open表和closed表3〕节点样子画出整个图G和解途径4〕程序何时终了5〕改用深度优先如何？例子

八数码难题〔8-puzzleproblem〕241238456712384567〔目的形状〕〔初始形状〕规定：将牌移入空格的顺序为：从空格左边开场顺时针旋转。不许斜向挪动，也不前往先辈节点。从图可见，要扩展26个节点，共生成46个节点之后才求得解〔目的节点〕。3.2盲目搜索253.2盲目搜索3.2.2深度优先搜索(Dephth-first)26定义：首先扩展最新产生的(即最深的)节点。特点：防止搜索过程沿着无益的途径扩展下去，往往给出一个节点扩展的最大深度——深度界限。与宽度优先搜索算法最根本的不同在于：将扩展的后继节点放在OPEN表的前端。3.2盲目搜索深度优先搜索表示图27SLOMFPQNFFF3.2盲目搜索28开场把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表能否有后继节点为目的节点？扩展n，把n的后继节点放入OPEN表的前端，提供前往节点n的指针失败胜利图3.6深度优先算法框图是否是否3.2盲目搜索节点n的深度等于最大深度？否2024/1/1529深度优先算法Procedruedepth-First-Search1G=G0(G0=s),open=(s),closed=()//s:初始形状2Loop:ifopen=()thenexit(fall)3n←first(open)4ifgoal(n)thenexit(success)5remove(n,open),add(n,closed)6{mj}←expand(n),//mj不含n的先辈节点7open←add(open，mj)//mj不在open，closed中标志mj每个到n节点指针，按照节点深度递减顺序陈列open中的节点8goloop示范：有界深度(4)优先的八数码问题深度优先搜索树？303.2盲目搜索1238456712384567〔目的形状〕〔初始形状〕313.2盲目搜索2024/1/1532讨论1：假设问题有解，用深度优先搜索算法，能否可以找到解？不一定.解空间能否有限？讨论2：本算法的改良之处是open中节点按照深度优先陈列，但是没有对深度加以控制，能够呵斥搜索代价太大3.2.3等代价搜索33定义是宽度优先搜索的一种推行，不是沿着等长度途径断层进展扩展，而是沿着等代价途径断层进展扩展。搜索树中每条衔接弧线上的有关代价,表示时间、间隔等破费。算法在等价搜索算法中，把从节点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)=0S能否目的节点？是胜利否3.2盲目搜索扩展i，计算其后继节点j的g(j)，并把后继节点放入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可解。所以求得解树为：372.以下图是5个城市的交通图，城市之间的连线旁边的数字是城市之间路程的费用。要求从A城出发，经过其它各城市一次且仅一次，最后回到A城，请找出一条最优线路。等代价搜索383.3启发式搜索启发式信息：用来加速搜索过程的问题领域信息，普通与有关问题详细领域背景有关，不一定具有通用性。启发式搜索：利用启发式信息的搜索方法特点：重排OPEN表，选择最有希望的节点加以扩展种类：有序搜索、A*算法等39根本步骤：初始化，判别OPEN表能否为空，选择节点n，判别n能否目的节点，扩展节点n，重排OPEN表、调整指针，循环。各自特点：重排OPEN表的根据不同。盲目搜索能够带来组合爆炸。思索：〔1〕图搜索方法的根本步骤？〔2〕宽度优先、深度优先、等代价方法的特点？ 〔3〕盲目搜索的缺陷？有序搜索〔OrderedSearch〕总是选择“最有希望〞的节点作为下一被扩展节点估价函数〔EvaluationFunction〕为获得某些节点“希望〞的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有能够在通向目的的最正确途径上。

f(n)——表示节点n的估价函数值运用节点“希望〞程度〔估价函数值〕重排OPEN表；有序搜索也称为最正确优先搜索；估价函数举例：〔1〕棋局的得分；〔2〕间隔目的形状的间隔量度；〔3〕TSP问题中的途径；思索：f函数的计算，重排序的方法？403.3.1启发式搜索战略和估价函数3.3启发式搜索413.3.2有序搜索〔OrderedSearch；Best－firstSearch〕本质：选择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)对OPEN表重新排序，调整亲子关系及指针失败胜利图3.9有序搜索算法框图是否是否3.3启发式搜索算法八数码难题43〔2〕如下的八数码难题〔8-puzzleproblem〕12384567〔目的形状〕12384567〔初始形状〕〔3〕八数码难题的有序搜索树见以下图：3.3启发式搜索〔1〕估价函数设置： f(n)=d(n)+W(n)d(n):节点n的深度；W(n):错放的棋子数443.3启发式搜索f函数的重要性有序搜索的有效性直接取决于f,是提高搜索效率的关键；假设f不准确，能够失去最正确解，也能够失去全部解；f普通选择战略搜索时间与空间的折衷；保证有解或有最正确解；f选择的三种典型情况：〔1〕最优解答：形状空间中有多条解答途径，求解最优解答，如A*算法；〔2〕搜索代价与解答质量的综合：问题类似于〔1〕，但搜索过程能够超出时间与空间的界限。在适当的搜索实验中找到称心解答，并限制称心解答与最优解答的差别程度；如：TSP问题；〔3〕最小搜索代价：不思索解答的最优化〔只需一个解答或多个解答间无差别〕，尽量使搜索代价最小；如：定理证明。思索：〔1〕f不能识别某些节点的真实“希望〞值会怎样样？〔2〕f过多估计了全部节点又会怎样样？453.3启发式搜索3.3.3A*算法思索：经过节点n的最正确途径，怎样表示？怎样求解最优解答途径。估价函数f*：对节点n定义f*(n)=g*(n)+h*(n),表示从S开场经过节点n的一条最正确途径的代价。其中g*(n)表示从起始节点S到n的最正确途径，h*(n)表示从n到某目的节点的最正确途径。估价函数f：f(n)=g(n)+h(n)；其中g是g*的估计，h是h*的估计；g的一个选择就是搜索树中从S到n的这