人工智能第五章

1第5章搜索求解策略25.1基本概念一、状态空间表示法•状态空间表示法是用“状态”和“算符”（“操作”）来表示问题的一种方法。•基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的(1)状态（state）：表示问题解法中每一步问题状况的数据结构；Q=[q0，q1，…，qn]TQ表状态，qi为状态分量(2)算符（operator）：把问题从一种状态变换为另一种状态的手段；称为操作符或算符。F：{f1,f2,……}(3)状态空间：由状态变量和操作表示的符号体系，包含了问题求解时全部可能状态及其相互关系。三元组表示（S，F，G）3例•设有三枚钱币，其排列处在“正，正，反”状态，现允许每次可翻动其中任意一个钱币，问只允许操作三次的情况下，如何翻动钱币使其变成“正，正，正”或“反，反，反”状态。•状态：(q1,q2,q3)“正面”用“1”表示，“反面”用“0”表示•初始状态集合：{（1,1,0）}•目标状态集合：{（1，1，1），(0,0,0)}•操作：f1：翻q1，f2：翻q2，f3：翻q3F={f1,f2,f3}4例：MC问题问题：3个传教士(Missionary)，3个野人(Cannibal)，一条船，可同时乘坐2个人，要求在任何时刻，在河的两岸，传教士人数不能少于野人的人数。问：如何过河？•状态：用三元组(m,c,b)表示左岸的传教士、野人和船数。m={0,1,2,3}，c={0,1,2,3}，b={0,1}共4×4×2＝32种状态其中有16种可行，14种不可行（危险），2种达不到。初始状态：S=（3，3，1）或S331目标状态：G=（0，0，0）或S000•操作符（规则）Pij（左右），qij（右左）左右：p01,p10,p11,p02,p20条件：船在左岸右左：q01,q10,q11,q02,q20条件：船在右岸F={p01,p10,p11,p02,p20,q01,q10,q11,q02,q20}5MC问题状态空间图ppassqquitq11q11q02(210)不合法p11(000)(330)达不到6二、与/或树（图）表示法1、分解：大问题分解为若干个易解子问题，子问题解决了，大问题也就解决了。ABC或图ABCD与图2、变换：大问题变成若干个易解子问题，只要有一个子问题解决了，大问题也就解决了。7一些关于与或图的术语HMBCDEFGAN父节点与节点弧线或节点子节点端节点8基本概念•本原问题：不能再分解或变换，而且直接可解的子问题。•终止节点：不能分解或变换，可直接求解•可解节点：–终止节点–“或”节点，其子节点至少有一个是可解节点–“与”节点，其子节点均为可解节点•不可解节点：–可解节点的三个条件都不满足的节点•解树：–由可解节点构成，并可推出初始节点为可解节点的子树9梵塔问题•可以分解为三个子问题：(1)最大盘以上由1至2(2)最大盘由1至3(3)其余盘由2至3•问题的形式化表示：三元组(I,j,k)I---C所在钢针号j----B所在钢针号k---A所在钢针号•问题：（1，1，1）（3，3，3）ABC123ABC12310三阶梵塔问题的与/或树（113）（123）（111）（113）（123）（122）（111）（333）（122）（322）（111）（122）（322）（333）（321）（331）（322）（321）（331）（333）11三、搜索•根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程。•类型：1、问题表示方式：–状态空间搜索–与/或树搜索2、是否使用启发式信息–盲目搜索：•按预定的控制策略进行搜索，在搜索过程中获得的中间结果不用来改进控制策略。–启发式搜索：•搜索过程中加入与问题有关的启发性信息。（动态地确定操作规则排序）125.2状态空间的搜索策略•基本思想：–初态作为当前节点进行扩展生成子节点，检查目标状态是否出现，不出现则按策略选一个子节点进行扩展直到目标状态出现或没有可供扩展的子节点。一、一般的图搜索过程：•OPEN表：存放尚未被扩展的节点•CLOSED表：存放已被扩展的节点13图搜索算法：1.把初始节点S放入OPEN表，建立一个仅包含S的图G（搜索图）2.如果OPEN表空，则以失败退出。3.把OPEN表中的第一个节点取出放入CLOSED表，称此节点为n.4.如果n是目标节点，则成功地结束，解路径可通过回溯G中从n到S的指针获得。5.扩展节点n，产生一组子节点。把不是n的祖先的那些子节点记作集合M，把M的这些成员作为n的后继节点加入G中。6.•对于M的那些未曾在G中出现的成员，建立到n的指针，并把这些成员加到OPEN表中。•对于那些已在G中出现的成员，决定是否要修改它指向父节点的指针。•对于那些已在G中出现且已扩展的成员，决定是否要修改其后继节点指向父节点的指针。7.按某种搜索策略重排OPEN表中的节点8.转第2步14图搜索的一般过程开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？扩展节点n，将其子节点处理后放入OPEN表，为每个子节点配置指向节点n的指针重排OPEN表失败成功是是否否节点n可扩展吗？否是15•说明：–这个一般的图搜索过程，通过不断循环生成一个显式表示的图G（搜索图）和一个G的子集T（搜索树）–树T是由（6）中标记的指针决定的，除根节点s外，G中每个节点只有一个指针指向G中的一个父节点–OPEN表中的节点（未扩展节点）是搜索树的端节点，即尚未被选作为扩展的节点；CLOSED表中的节点（已扩展节点），可以是已被扩展而不能生成后继节点的那些端节点，也可以是树中的非端节点–（7）中对OPEN表上的节点进行排序是为了在（3）中能选出一个“最好”的节点优先扩展，不同的排序方法可构成形式多样的专门搜索算法–如果隐含图是一棵树，不会（6）中讨论的特殊节点，否则可能这些节点–***上述算法的关键一步是（7），对OPEN表的排序，即决定节点的扩展顺序，典型的有两种节点扩展顺序，得到两种搜索算法（广度优先搜索、深度优先搜索）16二、宽度优先（广度优先）基本思想是：从节点S0开始，逐层地对节点进行扩展，并考察它是否为目标节点，在第n层节点没有全部考察完之前，不对第n+1层的节点进行扩展。OPEN表：按“先进先出”排特点：一种高代价搜索，但若有解存在，则必能找到它。17•例子八数码难题（8-puzzleproblem）1238456712384567（目标状态）（初始状态）规定：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展26个节点，共生成46个节点之后才求得解（目标节点）。181238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345图八数码难题的宽度优先搜索树1345612384567123845671238456712384567123845672324252627123678221238456712384567123845671238456712384567123845671238456714151617181920211238456719三、深度优先搜索•首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。•与宽度优先搜索算法最根本的不同在于：将扩展的后继节点放在OPEN表的前端。（先进后出）20问题•不一定能找到解•找到的解不一定是最佳解为了对深度优先搜索作改进,要解决两个问题：①回溯问题;②有圈造成死循环问题。21四、有界深度优先搜索•如果问题有解且路径长度≤dm,则一定可求得解；否则得不到解。•问题：dm不易确定–这种方法不一定能找到解路径（如果解路径的深度超出了限制深度）–另外它得到的解也不一定是最优解•改进–先定一个较小的dm，若未找到解且closed中有待扩展的节点，就将其送回open表。不断改进dm。–最优解：增设一表R，每找到一个解就将其放入R的前面。最后求得的解一定最优22五、代价树的广度优先搜索—分枝界限法•有些问题并不要求有应用算符序列为最少的解，而是要求具有某些特性的解。搜索树中每条连接弧线上的有关代价以及随之而求得的具有最小代价的解答路径。•代价树：各边标有代价值的树----一种加权树•代价计算g(x)-------sx代价g(x2)=g(x1)+c(x1,x2)•基本思想：OPEN表中的全部节点按代价从小到大排23代价树的广度优先搜索开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？扩展节点n，将其子节点处理后放入OPEN表，为每个子节点配置指向节点n的指针，计算各节点代价。把OPEN表中的全部节点按代价从小到大排失败成功是是否否节点n可扩展吗？否是24例•下图是一个交通图，设A城市是出发地，E城市是目的地，边上的数字代表两城市之间的交通费。试求从A到E最小费用的旅行路线。Ac1d1e2825六、代价树的深度优先搜索---爬山法•基本思想：将扩展的后继节点按边代价从小到大的顺序放在OPEN表的前端。•代价树的广度优先搜索法是完备的且找到的解一定是最优解•代价树的深度优先搜索法是不完备的且找到的解不一定是最优解26七、启发式搜索•问题提出：–从理论上讲穷举式搜索能解决任何状态空间问题，但很显然穷举搜索只能解决状态空间很小的简单问题，对于复杂问题会出现“组合爆炸”•n阶Hanoi塔问题的状态空间图中有2的n次方减1个结点；•博弈问题中，为了取胜可以将所有的算法都试一下，然后选择最佳走步。就所有可能的棋局数来讲，一字棋是9！=3.6*10^9，国际象棋是10^120，围棋是10^761。假设每步可以选择一种棋局，用极限并行速度（10^-104秒/步）计算，国际象棋的算法得用10^16年即1亿亿年才可以算完。•解决：–利用问题的启发性信息来引导搜索–减少搜索范围–降低问题复杂度•启发信息：进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。把利用启发信息的搜索方法叫做启发性搜索方法。27启发性信息类型1）用于扩展节点的选择–即决定下一个扩展节点,以免象在广度优先和深度优先搜索中那样盲目地扩展2）用于生成节点的选择–即用于决定生成哪个或哪几个后继节点,而不是生成所有的节点3）用于删除节点的选择–即决定用于从搜索树中抛弃或修剪的节点•我们讨论的主要是基于“扩展节点的选择”的启发式搜索，这种搜索总是选择“最有希望”的节点作为下一个被扩展的节点。这种搜索叫做有序搜索(orderedsearch)。1、估价函数------评估节点的方法–用来估算节点希望程度的量度，叫做估价函数28f(x)=g(x)+h(x)•其中:f(x):从初始节点S0到目标节点Sg的最优路径的代价估计值①g(x)为从初始节点S0到节点x的实际代价值。②h(x)为启发函数,是从节点x到目标节点Sg的最优路径的代价h*(n)的估计值。•g(x)、h(x)作用分析–一般地,在f(n)中,g(n)的比重越大,越倾向于宽度优先搜索方式;h(n)的比重越大,越倾向于深度优先搜索方式。–保持g(n)项就保持了搜索的宽度优先趋势,这有利于搜索的完备性,但影响搜索的效率。–在特殊情况下,如果只希望找到达到目标结点的路径而不关心已付出的代价,则g(n)的作用可以忽略。–h(n)g(n)时,也可以忽略g(n),这时有f(n)=h(n),这有利于搜索的效率,但影响搜索的完备性。29•定义h（x）的原则：–节点x处在最佳路径上的摡率–节点x与目标节点集之间的距离度量或差异度量–根据格局或状态的特点来打分•一般来说,评价一个结点的价值,必须综合考虑两方面的因素:已经付出的代价和将要付出的代价。•启发式算法通常由两部分组成:–启发