搜索
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）–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表中。称此节点为节点n•5）若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一个解路径，用指针表示的解路径。•ProcedureGraphSearch•1G=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中2019/8/110•标记mj每个到n节点指针•确定是否需要修改已在open，closed中的每个节点到n的指针•确定是否需要修改已在closed中的每个节点的后继节点原来的指针。8按照某种方式排列open表中的节点，goloop2019/8/1112019/8/1122019/8/113•思考：–（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盲目搜索思考：与原始算法比较异同，宽度优先的体现？2019/8/119宽度优先算法•Procedruebreadth-First-Search•1G=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中2019/8/120•标记每个到n节点指针，按照节点深度递增顺序排列open中的节点•8goloop•理论上可以利用宽度优先搜索能够找到解，如果问题有解的话。•讨论：宽度优先算法和深度优先算法可能出现组合爆炸。都没有利用任何启发式信息，所以称为无信息搜索策略。2019/8/121：•宽度优先例题：•由一张桌子T、三个积木A、B、C组成一个积木世界，初始状态是A在B上，B在桌子上，C在桌子上；目标状态是：A、B、C依次从上到下排列在桌子上。如图2019/8/122•解：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同一种状态出现不得多于一次。2019/8/123•1）解题过程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的深度等于最大深度？否2019/8/129深度优先算法•Procedruedepth-First-Search•1G=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盲目搜索2019/8/132•讨论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.设有如图所示的一棵与/或树，请用与/或树的宽度优先搜索及与/或树的深度优先搜索求出解树。35BCt1t2t3t4t5AD•解：（1）与/或树的宽度优先搜索I.先扩展节点A，得到节点B和C；II.再扩展节点B,得节点t1、t2，因为t1、t2为可解节点，故节点B可解，从而可节点A可解。III.所以求得解树为：36•（2）与/或树的深度优先搜索I.先扩展节点A,得到节点B和C；II.再扩展节点C,得节点D和t5；III.t5为可解节点，再扩展节D，得节点t3、t4；IV.t3、t4为可解节点，故节点D可解，因为节点D和t5可解故节点C可解，从而可节点A可解。V.所以求得解树为：37•2.下图是5个城市的交通图，城市之间的连线旁边的数字是城市之间路程的费用。要求从A城出发，经过其它各城市一次且仅一次，最后回到A城，请找出一条最优线路。•等代价搜索38A10B289C1163128D9E图1：交通路线图3.3启发式搜索•启发式信息：用来加速搜索过程的问题领域信息，一般与有关问题具体领域背景有关，不一定具有通用性。•启发式搜索：利用启发式信息的搜索方法–特点：重排OPEN表，选择最有希望的节点加以扩展–种类：有序搜索、A*算法等39基本步骤：初始化，判断OPEN表是否为空，选择节