人工智能基础03--搜索技术79

合肥工业大学人工智能与数据挖掘研究室1/79目录第一章绪论第二章知识表示第三章搜索技术第四章推理技术第五章机器学习第六章专家系统第七章自动规划系统第八章自然语言理解第九章智能控制第十章人工智能程序设计合肥工业大学人工智能与数据挖掘研究室2/793.1盲目搜索盲目搜索：即无信息搜索宽度优先与深度优先3.1.1图搜索策略图搜索策略可看作一种在图中寻找路径的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。研究图搜索的一般策略，能够给出图搜索过程的一般步骤。合肥工业大学人工智能与数据挖掘研究室3/793.1盲目搜索3.1.1图搜索策略例3.1从王某家族的四代中找王A的后代且其寿命为X的人A,47B1,77A3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51合肥工业大学人工智能与数据挖掘研究室4/793.1盲目搜索3.1.1图搜索策略1.图搜索(GRAPHSEARCH)的一般过程(1)建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中。(2)建立一个叫做CLOSED的已扩展节点表，其初始为空表。(3)LOOP：若OPEN表是空表，则失败退出。(4)选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。(5)若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。合肥工业大学人工智能与数据挖掘研究室5/793.1盲目搜索3.1.1图搜索策略1.图搜索(GRAPHSEARCH)的一般过程(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。合肥工业大学人工智能与数据挖掘研究室6/793.1盲目搜索节点父辈节点3.1.1图搜索策略2.图搜索算法的几个重要名词（1）OPEN表与CLOSE表OPEN表CLOSED表编号节点父辈节点合肥工业大学人工智能与数据挖掘研究室7/793.1盲目搜索3.1.1图搜索策略3.搜索图与搜索树搜索过程框图开始初始化：S放入OPEN表，CLOES表置空,n=1OPEN表中的第一个结点n移至CLOSE表若n的后继未曾在搜索图G中出现，则将其放入OPEN表的末端，并提供返回结点n的指针,置n=n+1根据后继结点在搜索图G中的出现情况修改指针方向依某种准则重新排序OPEN表失败成功NYNOPEN为空表NULL？n=目标结点D吗?Y合肥工业大学人工智能与数据挖掘研究室8/793.1盲目搜索3.1.1图搜索策略4.图搜索方法分析：图搜索过程的第8步对OPEN表上的节点进行排序，以便能够从中选出一个“最好”的节点作为第4步扩展用。这种排序可以是任意的即盲目的(属于盲目搜索)，也可以用以后要讨论的各种启发思想或其它准则为依据(属于启发式搜索)。每当被选作扩展的节点为目标节点时，这一过程就宣告成功结束。这时，能够重现从起始节点到目标节点的这条成功路径，其办法是从目标节点按指针向S返回追溯。当搜索树不再剩有未被扩展的端节点时，过程就以失败告终(某些节点最终可能没有后继节点，所以OPEN表可能最后变成空表)。在失败终止的情况下，从起始节点出发，一定达不到目标节点。合肥工业大学人工智能与数据挖掘研究室9/793.1盲目搜索3.1.2宽度优先搜索定义3.1如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索（breadth-firstsearch)合肥工业大学人工智能与数据挖掘研究室10/793.1盲目搜索3.1.2宽度优先搜索宽度优先搜索算法(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4)扩展节点n。如果没有后继节点，则转向上述第(2)步。(5)把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。(6)如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。合肥工业大学人工智能与数据挖掘研究室11/793.1盲目搜索3.1.2宽度优先搜索例3.2八数码问题操作规定:允许空格四周上、下、左、右的数码块移入空格中，不许斜方向移动，不许返回先辈结点。初始布局S和目标状态D如下图所示：2674138516748325SD合肥工业大学人工智能与数据挖掘研究室12/793.1盲目搜索3.1.2宽度优先搜索例3.2八数码问题283147652318476528314765832147652837146583214765832147652814376523184765283145762318476528316475813247658342176581324765813247658326417528374615281637542837146528316754123847651237846523418765234185762814376524813765283145762836417528315746813264752837461523784615283746152837165428316754283641752831457628143765234187651238476528371465283164752831647528314765S1234512131110987614151617222324252618192021D合肥工业大学人工智能与数据挖掘研究室13/793.1盲目搜索3.1.3深度优先搜索深度优先算法步骤：(1)初始结点S放到未扩展节点OPEN中；(2)若OPEN为空，则搜索失败，问题无解；(3)弹出OPEN表中最顶端结点放到CLOSE表中，并给出顺序编号n；(4)若n为目标结点D，则搜索成功，问题有解；(5)若n无子结点，转(2)；(6)扩展n结点，将其所有子结点配上返回n的指针，并按次序压入OPEN堆栈，转(2)。合肥工业大学人工智能与数据挖掘研究室14/793.1盲目搜索3.1.3深度优先搜索2831647528316475283147652831647528316754283167542816375428163754281637542681375426813754268137542681537426815374268153742681574326158743268157432561874326158743261587432561874325618743256148732561487325614873256147382561473825146738S12345678910111213141516251467382451673825146738245167382451673824513678245136782451367817181920合肥工业大学人工智能与数据挖掘研究室15/793.1盲目搜索3.1.3深度优先搜索有界深度优先搜索：引入搜索深度限制值d，使深度优先搜索过程具有完备性。设定搜索深度限制d=5，问题同深度优先算法中的八数码问题(2)。合肥工业大学人工智能与数据挖掘研究室16/793.1盲目搜索3.1.3深度优先搜索28316475128316475228316754328163754428316475283147652831476528314765231847652318476523184765123847652341876512378465123847652341876523418576281437652481376528143765281437652831457628314576283157462831457683216754283716542831675428316754283156742318675423186754283156742831567428163754268137542816375423186754523262734332829302524192021151289DS18221716141311107636353231合肥工业大学人工智能与数据挖掘研究室17/793.1盲目搜索3.1.3深度优先搜索有界深度优先算法步骤：(1)初始结点S放入堆栈OPEN中；(2)若OPEN为空，则搜索失败，问题无解；(3)弹出OPEN中栈顶结点n，放入CLOSE表中，并给出顺序编号n；(4)若n为目标结点D，则搜索成功，问题有解；(5)若n的深度d(n)=d，则转(2)；(6)若n无子结点，即不可扩展，转(2)；(7)扩展结点n，将其所有子结点配上返回n的指针，并压入OPEN堆栈，转(2)。合肥工业大学人工智能与数据挖掘研究室18/793.1盲目搜索3.1.4等代价搜索宽度优先搜索可被推广用来解决寻找从起始状态至目标状态的具有最小代价的路径问题，这种推广了的宽度优先搜索算法叫做等代价搜索算法。等代价搜索中的几个记号起始节点记为S；从节点i到它的后继节点j的连接弧线代价记为c(i，j)；起始节点S到任一节点i的路径代价记为g(i)。如果所有的连接弧线具有相等的代价，那么等代价算法就简化为宽度优先搜索算法。合肥工业大学人工智能与数据挖掘研究室19/793.2启发式搜索盲目搜索的不足：效率低，耗费空间与时间。启发式搜索：利用问题域特性的信息（启发信息）进行搜索。3.2.1启发式搜索策略启发式信息按用途分为三种：（1）用于确定要扩展的下一个节点，避免盲目扩展。（2）在扩展一个节点的过程中，用于确定要生成哪一个或哪几个后继节点，避免盲目生成所有可能节点。（3）用于确定某些应该从搜索树中抛弃或修剪得节点。合肥工业大学人工智能与数据挖掘研究室20/793.2启发式搜索有序搜索（orderedsearch）：利用第一种启发信息，总是选择“最有希望”的节点作为下一个被扩展的节点。估价函数（evaluationfunction)：估算节点“希望”的量度，这种量度叫做估价函数。建立估价函数的一般方法：试图确定一个处在最佳路径上的节点的概率；提出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。f(n)——表示节点n的估价函数值合肥工业大学人工智能与数据挖掘研究室21/793.2启发式搜索3.2.2有序搜索用估价函数f来排列GRAPHSEARCH第8步中OPEN表上的节点。应用某个算法(例如等代价算法)选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。这种搜索方法叫做有序搜索或最佳优先搜索(best-firstsearch)，而其算法就叫做有序搜索算法或最佳优先算法。合肥工业大学人工智能与数据挖掘研究室22/793.2启发式搜索3.2.2有序搜索有序状态空间搜索算法：(1)把起始节点S放到OPEN表中，计算f(S)并把其值与节点S联系起来。(2)如果OPEN是个空表，则失败退出，无解。(3)从OPEN表中选择一个f值最小的节点i。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点i。(4)把节点i从OPEN表中移出，并把它放入CLOSED的扩展节点表中。合肥工业大学人工智能与数据挖掘研究室23/793.2启发式搜索3.2