人工智能03_搜索原理-hj

1第三章搜索原理盲目搜索启发式搜索消解原理遗传算法博弈树搜索2图搜索在状态图中寻找目标和路径的基本方法就是搜索：搜索－－从初始节点出发，沿着与之相连的边试探前进，寻找目标节点的过程。树式搜索：从树根出发，以画树的方式进行搜索。线式搜索：搜索过程中只记录当前走过的节点和边，所形成的轨迹是一条线。3图搜索搜索的目的是为了寻找初始节点到目标节点的路径，则在搜索过程中必须随时记录搜索轨迹。使用一种成为CLOSED表的动态数据结构记录考查过的节点。在树式搜索中，CLOSED表中存储一颗不断增长的搜索树。在线式搜索中，CLOSED表中存储一颗不断伸长的折线。4图搜索在树式搜索中，还必须不断地把待考查的节点组织在一起，做某种排列，以控制搜索的方向和顺序。使用一种成为OPEN表的动态数据结构记录当前待考查的节点。5图搜索◆盲目搜索：又叫做无信息搜索，一般只适用于求解比较简单的问题。包括宽度优先搜索和深度优先搜索。◆图搜索策略可把图搜索策略看成一种在图中寻找路径的方法。图中的节点对应于状态，而连线对应于操作符。◆图搜索的一般过程如下：(1)建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中（简称OPEN表）。(2)建立一个叫做CLOSED的已扩展节点表（简称CLOSED表），其初始为空表。(3)LOOP：若OPEN表是空表，则失败退出。(4)选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n，n是CLOSED表中节点的编号。6图搜索(5)若n为一目标节点，则有解并成功退出，此解是图G中沿着指针从n到S的路径(指针将在第7步中设置)。(6)扩展节点n，生成n的后继节点的集合M。把M的成员作为n的后继节点添入图G中。(7)对未曾在G中出现过的(在OPEN或CLOSED表上均未曾出现过)M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后继节点的指针方向。(8)按某一任意方式或按某个探试值，重排OPEN表。(9)GOLOOP。没有考查过的节点，一定要考查（放入OPEN表）根据需要修改指针方向7图搜索过程开始把S放入OPEN表OPEN为空表？失败把第一个节点n从OPEN移至CLOSED表n为目标节点？成功把n的后继节点放入OPEN表的末端，提供返回节点n的指针根据需要修改指针方向重排OPEN表是否是否8图搜索过程123456OPEN:CLOSED:123456已知状态空间，如何搜索一条从1Æ6的可达路径？SG9图搜索◆图搜索算法中的几个重要名词：1．OPEN表2．CLOSED表父节点节点3．搜索图与搜索树图搜索过程生成一个图G(称为搜索图)和一个G的子集T(称为搜索树)，树T上的每个节点也在图G中。搜索树是由第7步中设置的指针来确定的。G中的每个节点(除S外)都有一个只指向G中一个父辈节点的指针，该父辈节点就定为该节点的唯一父辈节点。◆说明：图搜索过程的第8步对OPEN表上的节点进行排序，以便能够从中选出一个“昀好”的节点作为第4步扩展用。这种排序可以是任意的(属于盲目搜索)，也可以用各种启发思想或其它准则为依据(属于启发式搜索)。父节点节点编号10宽度优先搜索◆宽度优先搜索：搜索是以接近起始节点的程度依次扩展节点的。ƒ宽度优先搜索是逐层进行的，在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。生成的后继节点能否含有祖先节点？不能。11宽度优先搜索过程-图开始把S放入OPEN表S是否为目标节点？成功把第一个节点n从OPEN移至CLOSED表后继节点是否有目标节点？成功是否是否扩展n，把n的后继节点放入OPEN表的末端，提供返回节点n的指针OPEN为空表？是失败否12宽度优先搜索ƒ宽度优先搜索方法分析：宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第8步(按某一任意方式或按某个探试值，重排OPEN表)具体化为本算法中的第6步(把n的后继节点放入OPEN表的末端)，ƒ实际是将OPEN表作为“先进先出”的队列进行操作。ƒ宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的昀短途径；这棵搜索树提供了所有存在的路径。ƒ如果没有路径存在，那么对有限图来说，该法失败退出；对于无限图来说，则永远不会终止。【例】把宽度优先搜索应用于八数码难题。283147651238476513宽度优先搜索-例2831476523184765283147652831476528316475231847652318476583214765283714652814376528314576283164752831647512384765234187658321476528371465281437652831457628364175283167541237846512384765目标节点1234567891011121314写上节点进入CLOSED表的顺序编号。1238476514深度优先搜索◆节点的深度：(1)起始节点(即根节点)的深度为0。(2)任何其它节点的深度等于其父辈节点深度加上1。◆深度优先搜索方法ƒ在深度优先搜索中，首先扩展昀新产生的(即昀深的)节点。深度相等的节点可以任意排列。ƒ搜索沿着状态空间某条单一的路径从起始节点向下进行，仅当搜索到达一个没有后裔的状态时，才考虑另一条路径。替代路径仅仅改变昀后n步，而且保持n尽可能小。ƒ为避免考虑太长的路径，往往给出一个节点扩展的昀大深度——深度界限。节点如果达到了深度界限，就视为没有后继节点。ƒ深度优先搜索方法所求得的解答路径并不一定是昀短路径。生成的后继节点能否含有祖先节点？15深度优先搜索过程-图开始把S放入OPEN表S为目标节点？成功把OPEN表中第一个节点n移至CLOSED表节点n深度=深度界限？成功扩展节点n，将其后裔放入OPEN表前端是否是否OPEN为空表？后继节点是否存在目标节点？失败是否是否含有深度界限的16深度优先搜索-例【例】按深度优先搜索生成八数码难题搜索树，设置深度界限为5。28314765231847652831476528314765283164752318476523184765123847651237846512384765目标节点算法中，能否先只扩展一个后继节点用于进一步搜索？并不具有特别的优势。写上该节点进入CLOSED表的顺序编号。12341238476517等代价搜索◆等代价搜索算法：寻找从起始状态至目标状态的具有昀小代价的路径问题的搜索算法。◆一些记号：ƒ起始节点记为S；ƒ从节点i到它的后继节点j的连接弧线代价记为c(i,j)；ƒ从起始节点S到任一节点i的路径代价记为g(i)。在搜索树上，假设g(i)是从起始节点S到节点i的昀少代价路径上的代价。18等代价搜索过程-图开始把S放入OPEN表S为目标节点？成功把g(i)值昀小的节点i从OPEN表移至CLOSED表i是否为目标节点？扩展节点i，计算其后继节点j的g(j)值，把后继节点放入OPEN表是否是否OPEN为空表？失败是否成功令g(s)=019等代价搜索-例◆例：旅行商问题5721234431ABEDCAABACADAE1275ABCABDABE554ACBACDACE634ACDBACDE76ABECABED67ABEDCA或ACDEBA。ƒ生成的后继节点能否含有祖先节点？能，但需要修改算法。参见有序搜索算法的过程。123456每个节点旁边圆圈圈起来的数字代表进入Closed表的序号，没有圈起来的是代价值。20启发式搜索◆盲目搜索的不足：效率低，耗费过多的计算空间与时间。解决办法：寻找扩展节点的顺序。◆启发信息：选择性的搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。◆启发信息分类：按其用途分(1)用于决定要扩展哪一个节点。(2)在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。(3)用于决定某些应该从搜索树中抛弃或修剪的节点。◆利用第一种启发信息的状态空间搜索算法称为有序搜索。21启发式搜索◆估价函数：用来估算节点被扩展的希望程度的函数。用符号f来标记估价函数，f(n)表示节点n的估价函数值。ƒ用估价函数f来排列GRAPHSEARCH第8步中OPEN表上的节点。通常OPEN表上的节点按照f函数值递增顺序排列。ƒ选择OPEN表上具有昀小f值的节点作为下一个要扩展的节点。这种搜索方法叫做有序搜索或昀佳优先搜索。◆f的选择需要考虑：ƒ时间和空间之间的折衷方案；ƒ保证有一个昀优的解或任意解。◆宽度优先搜索、等代价搜索和深度优先搜索是有序搜索技术的特例。宽度优先搜索的f(i)为节点i的深度。深度优先搜索的f(i)为节点i的深度的倒数。等代价搜索的f(i)是从起始节点至节点i这段路径的代价。22有序搜索过程1)把起始节点S放到OPEN表中，计算f(S)。2)如果OPEN是个空表，则失败退出，无解。3)从OPEN表中选择一个f值昀小的节点i。若有几个节点f值相同，其中一个为目标节点则选择此节点，否则选任一个。4)把节点i从OPEN表中移出，放入CLOSED的扩展节点表中。5)如果i是个目标节点，则成功退出，求得一个解。6)扩展节点i，生成全部后继节点。对每一个后继节点j：a)计算f(j)。b)若j不在OPEN和CLOSED表中，则用估价函数f把它添入OPEN表。从j加一指向其父辈节点i的指针。c)若j已在OPEN或CLOSED表上，则比较刚得到的f(j)和前面计算过的该节点在表中的f值。若新的f值较小，则i.以此新值取代旧值。ii.从j指向i，而不是指向它的父辈节点。iii.若节点j在CLOSED表中，则把它移回OPEN表。7)转向2)。23有序搜索过程-图开始把S放入OPEN表，计算f(S)选取OPEN表中f值昀小的节点i，移至CLOSED表i是否为目标节点？扩展节点i，计算其后继节点j的f(j)，提供返回i的指针，利用f(j)对OPEN表重新排序，调整亲子关系及指针是否OPEN为空表？失败是否成功24A算法ƒ应用估价函数进行有序搜索可以减少被扩展的节点数。ƒ一般的有序搜索总是选择f值昀小的节点作为扩展节点。ƒ可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的代价以及从节点n到达目标节点的代价。◆A算法：在图搜索过程中，如果第8步的重排OPEN表是依据估价函数f(n)=g(n)+h(n)进行的，则称该过程为A算法。其中f(n)：评价函数，h(n)：启发函数。◆搜索效率的评估ƒ定义：穿透率P(penetrance)TLP=L：从初始状态到目标状态的路径长度(搜索深度)。T：搜索过程中产生的节点总数。ƒ定义：分枝因素B：代表在搜索过程中每个有效节点平均生成子节点的个数。则BBBL−−=1)1()1()1(LBBBLTLP−−==∴LBBBT+++=225符号的含义◆令k(ni，nj)表示任意两个节点ni和nj之间昀小代价路径的代价，对于两节点间没有通路的节点，函数k没有定义。◆令h*(n)表示从n到目标节点昀小代价路径的代价。从n到目标节点能够获得h*(n)的任一路径就是一条从n到某个目标节点的昀佳路径，对于不能到达目标节点的节点n，h*没有定义。◆引进函数g*，g*(n)=k(S,n)，即从起始节点S到任意节点n的一条昀佳路径的代价。◆定义函数f*，任一节点n的f*(n)值是从节点S到节点n的一条昀佳路径的实际代价加上从节点n到某目标节点的一条昀佳路径的代价之和，即f*(n)=g*(n)+h*(n)f*(n)值就是从S开始约束通过节点n的一条昀佳路径的代价，而f*(S)=h*(S)是从S到某个目标节点中间无约束的一条昀佳路径的代价。26符号的含义◆估价函数f是f*的一个估计，f(n)=g(n)+h(n)其中：g是g*的估计；h是h*的估计。ƒ对于g(n)，可以由从