资源描述
13.1 图搜索策略图搜索策略3.2 盲目搜索盲目搜索3.3 启发式搜索启发式搜索3.4 消解原理消解原理3.5 规则演绎系统规则演绎系统第三章第三章 搜索推理技术搜索推理技术3.6 产生式系统产生式系统3.7非单调推理非单调推理3.8小结小结问题问题：知识表示有那些方法？知识表示的目的是：知识表示有那些方法？知识表示的目的是什么？构建智能系统的关键是什么？什么？构建智能系统的关键是什么？23.1 图搜索策略图搜索策略 思考：状态空间法的基本特点？基本推理方法？其思考：状态空间法的基本特点？基本推理方法？其求解结果是什么？简单回顾实例：猴子与香蕉。求解结果是什么？简单回顾实例：猴子与香蕉。3 用一个四元表列用一个四元表列（W，x，Y，z）表示这个问题状态表示这个问题状态 W W 猴子的水平位置猴子的水平位置 x x 当猴子在箱子顶上时取当猴子在箱子顶上时取 x=1x=1；否则取；否则取 x=0 x=0 Y Y 箱子的水平位置箱子的水平位置 z z 当猴子摘到香蕉时取当猴子摘到香蕉时取 z=1z=1；否则取；否则取 z=0z=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）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，climbboxV=c，climbbox3.1 图搜索策略5猴子和香蕉问题自动演示：猴子猴子香蕉香蕉箱子箱子 猴子猴子香蕉香蕉箱子箱子 Ha!Ha!3.1 图搜索策略思考：计算机的搜索策略？思考：计算机的搜索策略？6 图搜索控制策略图搜索控制策略:一种在图中寻找路径的方法。一种在图中寻找路径的方法。图中每个节点对应一个状态图中每个节点对应一个状态;每条连线对应一个操作符。每条连线对应一个操作符。图搜索过程图搜索过程（GraphSearchGraphSearch）3.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)OPEN CLOSED(1)(2)宽度优先8图搜索的一般过程如下：图搜索的一般过程如下：1）建立一个只含有起始节点）建立一个只含有起始节点S的搜索图的搜索图G，把，把S放到放到一个叫做一个叫做OPEN 的的未扩展节点表未扩展节点表中。中。2）建立一个叫做）建立一个叫做CLOSED的的已扩展节点已扩展节点表，其初始为表，其初始为空表空表.3）LOOP：若：若OPEN表是空表，则失败退出。表是空表，则失败退出。4）选择）选择OPEN表上的第一个节点，把它从表上的第一个节点，把它从OPEN表移表移出并放进出并放进CLOSED表中。称此节点为节点表中。称此节点为节点n 5）若）若n为一目标节点，则有解并成功退出，此解是为一目标节点，则有解并成功退出，此解是追踪图追踪图G中沿着指针从中沿着指针从n到到S这条路径这条路径而得到的而得到的(指针将指针将在第在第7步中设置步中设置)。3.1 图搜索策略96）扩展节点）扩展节点n，同时生成不是，同时生成不是n的祖先的那些后继节点的的祖先的那些后继节点的集合集合M。把。把M的这些成员作为的这些成员作为n的后继节点添入图的后继节点添入图G中。中。7）对那些未曾在）对那些未曾在G中出现过的中出现过的M成员设置一个通向成员设置一个通向n的指的指针。把针。把M的这些成员加进的这些成员加进OPEN表。对已经在表。对已经在OPEN或或CLOSED表上的每一个表上的每一个M成员，确定是否需更改通到成员，确定是否需更改通到n的指的指针方向。对已在针方向。对已在CLOSED表上的每个表上的每个M成员，确定是否需成员，确定是否需要更改图要更改图G中通向它的每个后裔节点的指针方向。中通向它的每个后裔节点的指针方向。8）按某一任意方式或按某个探试值，重排）按某一任意方式或按某个探试值，重排OPEN表。表。9）GO LOOP。3.1 图搜索策略10图搜索策略 图搜索的实质是从问题空间中找出一张包含目标节点的子图。图搜索的结果：1，一个完整的搜索图G。2一个解路径，用指针表示的解路径。Procedure Graph Search 1 G=G0(G0=s),open=(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中11 标记mj每个到n节点指针 确定是否需要修改已在open，closed中的每个节点到n的指针 确定是否需要修改已在closed中的每个节点的后继节点原来的指针。8 按照某种方式排列open表中的节点，go loop121314 思考：思考：（1）结果路径的形成中，为什么其节点顺序是明确的？）结果路径的形成中，为什么其节点顺序是明确的？（2）OPEN表中的节点具有什么特点？表中的节点具有什么特点？（3）CLOSED表中的节点具有什么特点？表中的节点具有什么特点？（4）对）对OPEN表节点的排序有何意义？表节点的排序有何意义？提出：盲目搜索与启发式搜索。提出：盲目搜索与启发式搜索。3.1 3.1 图搜索策略图搜索策略153.2 3.2 盲目搜索盲目搜索 盲目搜索又叫做盲目搜索又叫做无信息搜索无信息搜索，一般只适用于求解比较，一般只适用于求解比较简单的问题。简单的问题。特点：不需重排特点：不需重排OPENOPEN表；表；种类：宽度优先、深度优先、等代价搜索等。种类：宽度优先、深度优先、等代价搜索等。3.2.1 3.2.1 宽度优先搜索（宽度优先搜索（Breadth-firstBreadth-first）v 定义：定义：以接近起始节点的程度逐层扩展节点的搜索方法。以接近起始节点的程度逐层扩展节点的搜索方法。v 特点：特点：一种高代价搜索，但若有解存在，则必能找到它。一种高代价搜索，但若有解存在，则必能找到它。16SLOMFPQNFFF宽度优先搜索示意图171）把起始节点放到）把起始节点放到OPEN表中表中(如果该起始节点为一目标节点，如果该起始节点为一目标节点，则求得一个解答则求得一个解答)。2）如果）如果OPEN是个空表，则没有解，失败退出；否则继续。是个空表，则没有解，失败退出；否则继续。3）把第一个节点）把第一个节点(节点节点n)从从OPEN表移出，并把它放入表移出，并把它放入CLOSED的的扩展节点表中。扩展节点表中。4）扩展节点）扩展节点n。如果没有后继节点，则转向上述第。如果没有后继节点，则转向上述第(2)步。步。5）把）把n的所有后继节点放到的所有后继节点放到OPEN表的末端，并提供从这些后表的末端，并提供从这些后继节点回到继节点回到n的指针。的指针。6）如果）如果n的任一个后继节点是个目标节点，则找到一个解答，的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第成功退出；否则转向第(2)步。步。宽度优先搜索算法：宽度优先搜索算法：3.2 盲目搜索18开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表是否有后继节点是否有后继节点为目标节点？为目标节点？扩展扩展n，把，把n的后继节点放入的后继节点放入OPEN表的表的末末端，提供返回节点端，提供返回节点n的指针的指针失败失败成功成功图图3.2 宽度优先算法框图宽度优先算法框图是是否否是是否否3.2 盲目搜索思考：与原始算法比较异同，宽度优先的体现？思考：与原始算法比较异同，宽度优先的体现？19宽度优先算法 Procedrue breadth-First-Search 1 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 openadd(open，mj)/mj不在open，closed中20 标记每个到n节点指针，按照节点深度递增顺序排列open中的节点 8 go loop 理论上可以利用宽度优先搜索能够找到解，如果问题有解的话。讨论：宽度优先算法和深度优先算法可能出现组合爆炸。都没有利用任何启发式信息，所以称为无信息搜索策略。21：宽度优先例题：由一张桌子T、三个积木A、B、C组成一个积木世界，初始状态是A在B上，B在桌子上，C在桌子上；目标状态是：A、B、C依次从上到下排列在桌子上。如图22 解：1）状态描述（P1，P2，P3）表示按A、B、C顺序依次分别在P1,P2,P3上其中Pi是积木或者桌子。初始状态时（B、T、T）,目标状态 可以表示（B、C、T）2）定义操作:move(x,y)表示将积木x移到Y上 ；约束条件:a X顶部必须是空的 b 如果Y是积木，Y的顶部必须是空的 c 同一种状态出现不得多于一次。23 1）解题过程 2）open表和closed表 3）节点样子画出整个图G 和解路径 4）程序何时结束 5）改用深度优先如何？24 例子例子八数码难题（八数码难题（8-puzzle problem）1238456712384567（目标状态）（目标状态）（初始状态（初始状态）规定：规定：将牌移入空格的顺序为：从空格左边将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展先辈节点。从图可见，要扩展2626个节点，共个节点，共生成生成4646个节点之后才求得解（目标节点）。个节点之后才求得解（目标节点）。3.2 盲目搜索253.2 盲目搜索263.2.2 深度优先搜索深度优先搜索(Dephth-first)(Dephth-first)v 定义：定义：首先扩展最新产生的首先扩展最新产生的(即最深的即最深的)节点。节点。v 特点：特点：防止搜索过程沿着无益的路径扩展下去，往往给防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度出一个节点扩展的最大深度深度界限。深度界限。与宽度优先搜索算法最根本的不同在于：将扩展与宽度优先搜索算法最根本的不同在于：将扩展的后继节点放在的后继节点放在OPENOPEN表的前端表的前端。3.2 3.2 盲目搜索盲目搜索27深度优先搜索示意图SLOMFPQNFFF3.2 3.2 盲目搜索盲目搜索28开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表是否有后继节点是否有后继节点为目标节点？为目标节点？扩展扩展n，把，把n的后继节点放入的后继节点放入OPEN表的表的前前端，提供返回节点端，提供返回节点n的指针的指针失败失败成功成功图图3.6 深度优先算法框图深度优先算法框图是是否否是是否否3.2 盲目搜索节点节点n的深度等于最大深度？的深度等于最大深度？否否29深度优先算法 Procedrue depth-First-Search 1 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 openadd(open，mj)/mj不在open，closed中 标记mj每个到n节点指针，按照节点深度递减顺序排列open中的节点 8 go loop30示范：有界深度示范：有界深度(4)优先的八数码问题深度优先优先的八数码问题深度优先搜索树？搜索树？3.2 3.2 盲目搜索盲目搜索1238456712384567（目标状态）（目标状态）（初始状态（初始状态）313.2 3.2 盲目搜索盲目搜索32 讨论1：如果问题有解，用深度优先搜索算法，是否能够找到解？不一定.解空间是否有限？讨论2：本算法的改进之处是open中节点按照深度优先排列，但是没有对深度加以控制，可能造成搜索代价太大333.2.3 等代价搜索等代价搜索v 定义定义 是是宽度优先搜索宽度优先搜索的一种推广，不是沿着等长度路的一种推广，不是沿着等长度路径断层进行扩展，而是沿着等代价路径断层进行扩展。径断层进行扩展，而是沿着等代价路径断层进行扩展。搜索树中每条连接弧线上的有关代价搜索树中每条连接弧线上的有关代价,表示时间、表示时间、距离等花费。距离等花费。v 算法算法 在等价搜索算法中，把从节点在等价搜索算法中，把从节点i i到其后续节点到其后续节点j j的连的连接弧线记为接弧线记为c(I,j)c(I,j),把从起始节点把从起始节点S S到任一节点到任一节点I I的路径代的路径代价记为价记为g(i)g(i)。在搜索树上，假设。在搜索树上，假设g(i)g(i)也是从起始节点也是从起始节点S S到到节点的最少代价路径上的代价。节点的最少代价路径上的代价。3.2 3.2 盲目搜索盲目搜索思考：如何动态计算思考：如何动态计算g g(i i)?)?34开始开始把把S S放入放入OPENOPEN表表OPEN表为空表？表为空表？把把具有最小具有最小g(i)值的节点值的节点i从从OPEN表表移至移至CLOSED表表是否有后继节点是否有后继节点为目标节点？为目标节点？失败失败成功成功图图3.8 等代价搜索算法框图等代价搜索算法框图是是否否是是否否令令g(s)=0S S是否目标节点是否目标节点？是是成功成功否否3.2 3.2 盲目搜索盲目搜索扩展扩展i i，计算其后继节点，计算其后继节点j j的的g(j)，并把后继节点放入并把后继节点放入OPEN表表35课后例题讲解 1.设有如图所示的一棵与/或树，请用与/或树的宽度优先搜索及与/或树的深度优先搜索求出解树。36 解：（1）与/或树的宽度优先搜索 先扩展节点A，得到节点B和C；再扩展节点B,得节点t1、t2，因为t1、t2为可解节点，故节点B可解，从而可节点A可解。所以求得解树为：37（2）与/或树的深度优先搜索 先扩展节点A,得到节点B和C；再扩展节点C,得节点D和t5；t5为可解节点，再扩展节D，得节点t3、t4；t3、t4为可解节点，故节点D可解，因为节点D和t5可解故节点C可解，从而可节点A可解。所以求得解树为：38 2.下图是5个城市的交通图，城市之间的连线旁边的数字是城市之间路程的费用。要求从A城出发，经过其它各城市一次且仅一次，最后回到A城，请找出一条最优线路。等代价搜索393.3 启发式搜索启发式搜索启发式信息：启发式信息：用来加速搜索过程的问题领域信息，一般与有关问题用来加速搜索过程的问题领域信息，一般与有关问题具体领域背景有关，不一定具有通用性。具体领域背景有关，不一定具有通用性。启发式搜索：启发式搜索：利用启发式信息的搜索方法利用启发式信息的搜索方法特点：特点：重排重排OPENOPEN表，选择最有希望的节点加以扩展表，选择最有希望的节点加以扩展种类：有序搜索、种类：有序搜索、A A*算法等算法等v基本步骤：基本步骤：初始化，判断初始化，判断OPENOPEN表是否为空，选择节点表是否为空，选择节点n n，判断，判断n n是否是否目标节点，扩展节点目标节点，扩展节点n n，重排，重排OPENOPEN表、调整指针，循环。表、调整指针，循环。v各自特点：各自特点：重排重排OPENOPEN表的依据不同。表的依据不同。v盲目搜索可能带来组合爆炸。盲目搜索可能带来组合爆炸。思考思考：（1 1）图搜索方法的基本步骤？）图搜索方法的基本步骤？（2 2）宽度优先、深度优先、等代价方法的特点？）宽度优先、深度优先、等代价方法的特点？（3 3）盲目搜索的缺点？）盲目搜索的缺点？40有序搜索（有序搜索（Ordered SearchOrdered Search）总是选择总是选择“最有希望最有希望”的节点作为下一被扩展节点的节点作为下一被扩展节点估价函数（估价函数（Evaluation FunctionEvaluation Function）为获得某些节点为获得某些节点“希望希望”的启发信息，提供一个评定侯选扩展节点的方的启发信息，提供一个评定侯选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上法，以便确定哪个节点最有可能在通向目标的最佳路径上 。f f(n n)表示节点表示节点n n的估价函数值的估价函数值 应用节点应用节点“希望希望”程度（估价函数值）重排程度（估价函数值）重排OPENOPEN表；有序搜表；有序搜索也称为索也称为最佳优先搜索最佳优先搜索；估价函数举例：估价函数举例：（1 1）棋局的得分；）棋局的得分；（2 2）距离目标状态的距离量度；）距离目标状态的距离量度；（3 3）TSPTSP问题中的路径；问题中的路径；思考：思考：f f 函数的计算，重排序的方法？函数的计算，重排序的方法？3.3.1 3.3.1 启发式搜索策略和估价函数启发式搜索策略和估价函数3.3 3.3 启发式搜索启发式搜索413.3.2 有序搜索（有序搜索（Ordered SearchOrdered Search；BestBestfirst Searchfirst Search）v实质：实质：选择选择OPENOPEN表上具有最小表上具有最小 f f 值的节点作为下值的节点作为下一个要扩展的节点一个要扩展的节点。3.3 3.3 启发式搜索启发式搜索vNilssonNilsson（尼尔逊）方法：（尼尔逊）方法：一个节点的一个节点的“希望希望”越大，则其越大，则其 f f 值越小。被选择的节点是估价函数最值越小。被选择的节点是估价函数最小的节点。小的节点。思考：如果把宽度优先、深度优先、等代价搜索方法作思考：如果把宽度优先、深度优先、等代价搜索方法作为有序搜索的特例，那么它们的为有序搜索的特例，那么它们的 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 启发式搜索v算法算法43 八数码难题八数码难题（2 2）如下的八数码难题（）如下的八数码难题（8-puzzle problem8-puzzle problem）12384567（目标状态）（目标状态）12384567（初始状态）（初始状态）（3）八数码难题的有序搜索树见下图八数码难题的有序搜索树见下图：3.3 3.3 启发式搜索启发式搜索（1）估价函数设置：）估价函数设置：f(n)=d(n)+W(n)d(n):节点节点n的深度；的深度；W(n):错放的棋子数错放的棋子数 443.3 启发式搜索45f 函数的重要性函数的重要性 有序搜索的有效性直接取决于有序搜索的有效性直接取决于 f ,是提高搜索效率的关键；是提高搜索效率的关键；如果如果 f 不准确，可能失去最佳解，也可能失去全部解；不准确，可能失去最佳解，也可能失去全部解；f 一般选择策略一般选择策略 搜索时间与空间的折衷；搜索时间与空间的折衷；保证有解或有最佳解；保证有解或有最佳解；f 选择的三种典型情况：选择的三种典型情况：（1）最优解答：状态空间中有多条解答路径，求解最优解答，如）最优解答：状态空间中有多条解答路径，求解最优解答，如A*算法；算法；（2）搜索代价与解答质量的综合：问题类似于（）搜索代价与解答质量的综合：问题类似于（1），但搜索过程），但搜索过程可能超出时间与空间的界限。在适当的搜索实验中找到满意解答，可能超出时间与空间的界限。在适当的搜索实验中找到满意解答，并限制满意解答与最优解答的差异程度；如：并限制满意解答与最优解答的差异程度；如：TSP问题；问题；（3）最小搜索代价：不考虑解答的最优化（只有一个解答或多个）最小搜索代价：不考虑解答的最优化（只有一个解答或多个解答间无差异），尽量使搜索代价最小；如：定理证明。解答间无差异），尽量使搜索代价最小；如：定理证明。思考思考：（1）f 不能识别某些节点的真实不能识别某些节点的真实“希望希望”值会怎么样？值会怎么样？（2）f 过多估计了全部节点又会怎么样？过多估计了全部节点又会怎么样？3.3 3.3 启发式搜索启发式搜索463.3.3 A*算法 思考：经过节点思考：经过节点n n的最佳路径，怎么表示？的最佳路径，怎么表示？怎么求怎么求解最优解答解最优解答路径路径。估价函数估价函数f f*：对节点：对节点n n定义定义f f*(n n)=)=g g*(n n)+)+h h*(n n),表示从表示从S S开始通开始通过节点过节点n n的一条最佳路径的代价。其中的一条最佳路径的代价。其中g g*(n n)表示从起始节点表示从起始节点S S到到n n的最佳路径，的最佳路径，h h*(n n)表示从表示从n n到某目标节点的最佳路径。到某目标节点的最佳路径。估价函数估价函数f f ：f f(n n)=)=g g(n)+(n)+h h(n n)；其中其中g g是是g g*的估计的估计 ，h h是是h h*的的估计；估计；g g 的一个选择就是搜索树中从的一个选择就是搜索树中从 S S 到到 n n 的这段路径的代价；显然有的这段路径的代价；显然有g g(n)(n)g g*(n n)；h h 的依赖于领域的启发信息，比如八数码问题中的的依赖于领域的启发信息，比如八数码问题中的 WW(n n),h h 称为称为启发式函数；启发式函数；3.3 启发式搜索47 A A*算法：算法：定义定义1 1 在在GRAPHSEARCHGRAPHSEARCH过程中，如果第过程中，如果第8 8步的重排步的重排OPENOPEN表是依据表是依据f f(x x)=)=g g(x x)+)+h h(x x)进行的，则称该过程为进行的，则称该过程为A A算法算法。定义定义2 2 在在A A算法中，如果对所有的算法中，如果对所有的x x存在存在h(x)hh(x)h*(x),(x),则称则称h(x)h(x)为为h h*(x)(x)的的下界下界，它表示某种偏于保守的估计。，它表示某种偏于保守的估计。定义定义3 3 采用采用h h*(x)(x)的下界的下界h(x)h(x)为启发函数的为启发函数的A A算法，称为算法，称为A A*算算法法。当。当h=0h=0时，时，A A*算法就变为算法就变为等代价搜索算法等代价搜索算法。48A*算法总框图算法总框图开始开始把把S放入放入OPEN表，记表，记 f=hOPEN=NIL?失败失败BESTNODE是目是目标节点？标节点？成功成功扩展扩展BESTNODE，产生，产生后续节点后续节点SUCCESSOR否否否否 是是 是是A*子过程子过程选取选取OPEN表上未设置过的具有最小表上未设置过的具有最小 f 值值的节点的节点BESTNODE,放入放入CLOSED表中表中
展开阅读全文