《人工智能AI讲稿5(搜索student).ppt》由会员分享，可在线阅读，更多相关《人工智能AI讲稿5(搜索student).ppt（86页珍藏版）》请在三一办公上搜索。
1、人工智能（Artificial Intelligence）基本原理,福州大学数学与计算机学院陈昭炯2023/6/13,第六章 搜索策略,基本概念 状态空间的搜索策略 与/或树的搜索策略 搜索的完备性与效率,一般图的搜索过程广度优先搜索深度优先搜索有界深度优先搜索代价树的广度优先搜索代价树的深度优先搜索启发式搜索A*算法,与/或树的一般搜索过程与/或树的广度优先搜索与/或树的深度优先搜索与/或树的有序搜索博弈树的启发式搜索剪枝技术,搜索的含义状态空间表示法与/或树表示法,搜索的含义依问题的实际情况寻找可利用的知识，构造代价较少的推理路径从而解决问题的过程离散的问题通常没有统一的求解方法搜索策略的
2、优劣涉及能否找到最好的解、计算时间、存储空间等搜索分为盲目搜索和启发式搜索盲目搜索：按预定的策略进行搜索，未用问题相关的或中间信息改进搜索。效率不高，难求解复杂问题，但不失可用性启发式搜索：搜索中加入问题相关的信息加速问题求解，效率较高，但启发式函数不易构造讨论的问题有哪些常用的搜索算法?问题有解时能否找到解?(完备性)找到的解是最佳的吗？(最优性)什么情况下可以找到最佳解？求解的效率如何?（时间、空间复杂度）,基本概念,状态空间表示法状态：描述问题求解中任一时刻的状况；变量的有序组合算符：一个状态另一状态的操作状态空间：状态，算符 表示,描述形式算符问题求解过程：初始状态：描述问题求解中的初
3、始状况算符：一个状态另一状态的操作目标测试：确定给定的状态是否为目标状态路径耗散函数：设定每一步算符操作的耗散值问题的解：从初始状态到目标状态的路径最优解：所有解中耗散值最小的解,例：二阶梵塔问题,状态描述：（SA,SB）可能状态：S0=(1,1),S=(1,2),S=(1,3),S=(2,1),Sg=(2,2),S=(2,3)S=(3,1),S=(3,2),Sg=(3,3)算符：A(i,j)将A从i轴移至j轴;B(i,j)将B从i轴移至j轴可能算符：A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2)B(1,2),B(1,3),B(2,1),B(2,3),B(3
4、,1),B(3,2),猴子摘香蕉问题,a,b,c,操作符：Goto(u):猴子走到u处(w,t,x,y,0)(u,t,x,y,0)Push(v):猴子推箱到v处(w,t,w,0,0)(v,t,v,0,0)Climb:猴子爬上箱子(w,t,w,0,0)(w,t,w,1,0)Grasp:猴子拿到香蕉(a,a,a,1,0)(a,a,a,1,1),状态：(w,t,x,y,z)w:猴子的水平位置 a,b,ct:天花板上香蕉对应的地面位置 a,b,cx:箱子的水平位置 a,b,cy:猴子是否在箱子上 0,1z:猴子是否拿到香蕉 0,1,初始状态：(c,a,b,0,0)目标状态：(a,a,a,1,1)可能状
5、态：(b,a,b,0,0)(c,a,c,1,0)(c,a,c,1,1),例：修道士与野人问题(1968)S0：河左岸有3个Missionaries和3个Cannibals,1条boat条件：1）M和C都会划船，船一次只能载2人 2）在任一岸上，M人数不得少于C的人数，否则被吃目标：安全抵达对岸,左岸：(m,c,b)：0m,c 3，b0,1 S0：(3,3,1)Sg：(0,0,0)状态总数：44232种，但合法状态16种,0 x+y2:(x,y)=(2,0),(0,2),(1,1),(1,0),(0,1),例：皇后问题,初始状态：棋盘上无皇后算符：将皇后添加到棋盘上的任一空格目标测试：8皇后都在
6、棋盘上，且互相攻击不到路径耗散函数：每一步耗散值1,将4个皇后放到棋盘中，使得彼此不会攻击到（不同行、不同列、不同对角线）,返回,8皇后，92种解找到一般n皇后问题复杂度为O(n)的算法(1989),2 8 31 6 47 5,1 2 38 47 6 5,例：八数码游戏 8-Puzzle（九宫重排问题）sliding-block puzzle,初始状态：任一状态都可为初始状态算符：将空位移向四个方向目标测试：确定当前状态是否为目标状态路径耗散函数：每一步耗散值1,其状态可以划分为两个不相交的集合。(证明)8数码，9！/2181440；15数码，1.3万亿；24数码,1025一般nn数码是NP完
7、全问题（1986）,例：TSP问题Traveling Salesman Problem,从某城市出发遍历所有n个城市一遍且仅一遍再回到出发地，求最短路径,初始状态：在某一城市算符：移向下一个未访问过的城市目标测试：是否处于出发地且访问过所有城市一次路径耗散函数：路程长度，旅行费用等,No general method of solution is knownNPhard(Karp,1972)有效的启发式算法（1973）完全多项式近似方案（1998）,与/或树表示法（分解，分治）,与树 或树,与或树,例：三阶梵塔问题,状态描述：（SC,SB,SA),(1,1,1)(3,3,3),(1,2,2,)
8、(3,2,2),(1,1,1)(1,2,2),(3,2,2)(3,3,3),(1,1,1)(1,1,3),(1,1,3)(1,2,3),(1,2,3)(1,2,2),(3,2,2)(3,2,1),(3,2,1)(3,3,1),(3,3,1)(3,3,3),本原问题:不可分解，直接可解的问题端节点：无子节点的节点终止节点：本原问题对应的节点，可解可解/不可解节点：端节点，或节点，与节点解树：始节点（可解）可解节点,若干应用实例,寻径问题：计算机网络的路由，军事行动的规划，飞机航线旅行规划系统，机器人导航（寻径问题拓广）旅行问题：电路板自动钻孔机的运动规划，仓库货物码放机 的运动规划超大规模集成电
9、路的布局：在一个芯片上放置上百万个元器件及连线，还要达到芯片面积最小、电路延迟最小、杂散电容最小和产量最大。单元布局和通道寻径（1991）自动装配排序：找到一个装配物体（电动机）各部件的次序蛋白质设计：寻找一个氨基酸序列，当该序列叠放在3D的蛋白质结构里，可治愈某种疾病因特网搜索：寻找问题的答案、相关信息等,一般图的搜索过程,OPEN表：存放刚生成的节点CLOSED表：存放当前将要扩展和前面已扩展的节点扩展一个节点：生成出该节点的所有后继节点，并给出它们 之间的耗散值。,状态空间的搜索策略,1）S0OPEN，S0G0，2）OPEN=Nil无解；否则3）OPEN的第一个节点CLOSED，记为n4
10、）节点n=目标得解；否则5）扩展节点n,M=n扩展出的子节点n 的先辈；G n-1M G n6)处理M，xM,考虑 if x G n-1,x OPEN;if x G n-1(已生成过),判断x的父节点是否需改变（依代价）if x G n-1 AND xCLOSED(已扩展过),判断x的后继节点的父指针是否需改变7）按某种搜索策略对OPEN表排序队列方式(FIFO)：广度优先;堆栈方式（LIFO）：深度优先8）转2）,已扩展(CLOSED)已生成，未扩展(OPEN),选中当前正扩展,已扩展(CLOSED)已生成，未扩展(OPEN),选中当前正扩展,已扩展(CLOSED)已生成，未扩展(OPEN)
11、,选中当前正扩展,已扩展(CLOSED)已生成，未扩展(OPEN),选中当前正扩展,1）不同的搜索策略只是OPEN表的排序不同，过程类似2）G称为搜索图，由节点及其父指针搜索树3）目标找到后，其路径由逐级上行的父指针构成4）盲目搜索仅适用于树结构，不出现图搜索中6）,一些基本概念和记号,节点深度：根节点深度=0其它节点深度=父节点深度+1,0,1,2,3,路径的代价（耗散值）一条路径的代价（耗散值）等于连接这条路径各节点间所有代价（耗散值）的总和。用C(xi,xj)表示从父节点xi到子节点xj的边代价（耗散值）。代价树：边上标有代价的树状结构图若干记号：S0初始态；Sg目标态；g(x)从S0到
12、节点x的代价；g(xj)=g(xi)+C(xi,xj)h(x)x到Sg最优路径的估计代价,广度优先搜索,1,G:=G0(G0=S0),OPEN:=(S0),CLOSED:=();2,LOOP:IF OPEN=()THEN EXIT(FAIL);3,n:=FIRST(OPEN);4,IF GOAL(n)THEN EXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)M,G n-1M G n;7,IF GOAL(at M)THEN EXIT(SUCCESS);8,ADD(M,OPEN),并标记M中的节点到n的指针;9,GO LOOP;ADD
13、(x,y):添加x至y的尾部,广度优先搜索,2 31 8 47 6 5,1,2,5,6,7,3,目标,8,4,生成的新节点按队列方式压入OPEN表底部（先进先出）,深度优先搜索,1,G:=G0(G0=S0),OPEN:=(S0),CLOSED:=();2,LOOP:IF OPEN=()THEN EXIT(FAIL);3,n:=FIRST(OPEN);4,IF GOAL(n)THEN EXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)M,G n-1M G n;7,IF 目标在M中 THEN EXIT(SUCCESS);8,ADD(OP
14、EN,M),并标记M中的节点到n的指针;9,GO LOOP;ADD(x,y):添加x至y的尾部,深度优先搜索,2 31 8 47 6 5,1,2,3,4,5,6,7,8,9,a,b,c,d,目标,广度优先搜索效率分析,每个节点有b个后继节点；解的深度为d,最坏情况已生成的节点数,b=10生成104个节点/s占用103 bytes/node,深度优先搜索效率分析,存储的节点数bd+1；b=10,d=12,存储空间118K；O(bd);百亿倍,深度优先搜索的性质,一般不能保证找到最优解当深度限制不合理时，可能找不到解（无穷分支）最坏情况时，搜索空间等同于穷举时间效率较低是一个通用的与问题无关的方法
15、,当问题有解时，一定能找到解是一个通用的与问题无关的方法最坏情况时，搜索空间等同于穷举时间、空间效率较低,广度优先搜索的性质,有界深度优先搜索（迭代深入）,设定深度界限dm，找不到时逐渐加深避免搜索陷入某一无穷分支死循环问题有解一定可以找到解，但不一定最优当搜索空间很大且解的深度未知时，首选的盲目搜索法,代价树广度优先搜索,每次扩展的子节点返送回OPEN时，都对OPEN表所有点按代价从小到大重新排序,代价树深度优先搜索,从刚扩展的子节点中选一个代价最小的送入CLOSED表中进行扩展,回溯搜索,每次只生成一个后继节点而不是所有的后继，内存O(d),(),回溯搜索例：皇后问题,皇后问题,(),Q,
16、(1,1),(),Q,Q,(1,1),(1,1)(2,3),(),Q,(1,1),(1,1)(2,3),(),Q,Q,(1,1),(1,1)(2,3),(1,1)(2,4),(),Q,Q,(1,1),(1,1)(2,3),(1,1)(2,4),Q,(1,1)(2,4)(3.2),(),Q,Q,(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(),Q,(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(),(1,1),(1,1
17、)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),Q,(1,2)(2,4),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),Q,(1,2)(2,4),Q,(1,2)(2,4)(3,1),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),Q,(1,2)(2,4),Q,(1,2)(2,4)(3,1),Q,(1,2)(2,4)(3,1)(
18、4,3),例：找一条从A到E的最短路径,E,E,B,D,E,C,E,D,B,C,A,3,3,3,4,4,4,5,5,2,2,代价树广度优先搜索,是否需遍历所有路径才可确定最短？,例：找一条从A到E的最短路径,E,E,B,D,E,C,E,D,B,C,A,3,3,3,4,4,4,5,5,2,2,代价树广度优先搜索,是否需遍历所有路径才可确定最短？,例：找一条从A到E的最短路径,E,E,B,D,E,C,E,D,B,C,A,3,3,3,4,4,4,5,5,2,2,代价树深度优先搜索,深度与广度搜索扩展的节点数相同,启发式搜索,设计一个与问题相关的估价函数，用于评价各节点的重要程度按照节点的重要性次序，
19、亦即估价函数从小到大的顺序扩展节点估价函数的形式：f(x)=g(x)+h(x)g(x)从S0到节点x已付出的代价；h(x)x到Sg最优路径的估计代价;g(x)比例越大，越倾向广度优先搜索，完备性较好而效率可能受影响；h(x)比例越大，越倾向深度优先搜索，效率可能较好；加权调整比例,引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。,例：B:Black;W:White;E:Empty;将B全移至W右边；至多移3位；移i位代价为i，i=1,2,3,BBBWWWE,h(x)=3每个W左边B的个数；还有？,BBBWWWE,BBBEWWW,BBBWEWW,BBBWWEW,3+27
20、,2+27,1+27,BBEWWBW,4+21,EBBWWBW,BEBWWBW,BBWEWBW,BBWWEBW,6+21,5+21,5+21,6+21,BWBEWBW,BWBWEBW,7+18,8+18,EWBBWBW,BWEBWBW,BWBBWEW,10+15,8+18,9+18,WEBBWBW,11+15,局部择优搜索（瞎子爬山法）,对刚扩展的子节点计算f(x)，选取其中f(x)最小的一个节点 CLOSED表进行扩展深度优先类搜索在此框架下可统一表示为：深度优先：记深度为d(x)，则f(x)=-d(x)代价树深度优先：f(x)=C(xi,xj),全局择优搜索,每次对OPEN表中所有节点计算
21、f(x)，选取其中最小的一个节点 CLOSED表进行扩展广优先类搜索在此框架下可统一表示为：广度优先：记深度为d(x)，则f(x)=d(x)代价树广度优先：f(x)=g(x),定义评价函数1：f1(n)=g(n)+h1(n)g(n)为从初始节点到当前节点的耗散值（深度）h1(n)为当前节点“不在位”的将牌数,2 8 31 6 47 5,1 2 38 47 6 5,例：九宫重排问题,h1(n)=4,2 8 31 6 47 5,1 2 3,45,7 6,8,2 8 31 6 47 5,s(4),A(6),B(4),C(6),D(5),E(5),F(6),G(6),H(7),I(5),J(7),K(
22、5),L(5),M(7),目标,1,2,3,4,5,6,全局择优搜索,定义评价函数2：f2(n)=g(n)+h1(n)g(n)为从初始节点到当前节点的耗散值（深度）h2(n)为数字移到目标处的距离总和,2 8 31 6 47 5,h2(n)111 2 5,1 2 38 47 6 5,2 8 31 6 47 5,s(5),A(7),B(5),C(7),D(7),E(5),F(7),I(5),J(7),K(5),L(5),M(7),目标,1,2,3,4,5,全局择优搜索,A*算法,评价函数的格式：f(n)=g(n)+h(n)f(n)：评价函数；h(n)：启发函数g*(n)：从S0到n的最短路径的耗
23、散值 h*(n)：从n到Sg的最短路径的耗散值 f*(n)=g*(n)+h*(n)：从S0经过n到Sg的最短路径的耗散值 g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值恒有：g(n)g*(n)且 g(n)不增如果满足可纳条件：h(n)h*(n)则称为A*算法。,九宫问题解1,九宫问题解2,A*算法的性质,A*算法是可纳的：对于可解状态空间图，A*算法在有限步内终止并找到最优解。在h(n)h*(n)的条件下，h(n)的值越大，携带的启发式信息越多，扩展的节点数越少，搜索效率越高。*若h(n)还满足如下的单调性（一致）条件（三角不等式）*：h(Sg)0 h(xi)-h
24、(xj)C(xi,xj)；xj 是xi 的后继子节点,则：1）若A*选择xn进行扩展,就有：g(xn)=g*(xn)2）由A*扩展的节点序列其f(n)值非递减 3）一般图的搜索算法可简化,8数码的两种启发式算法？,A*算法的不足与改进：大多数情况节点数为解长度的指数级，存储量过大，保留了所有生成的节点，不适用于大规模问题存储限制的A*算法启发式函数的精确度问题：,8数码问题扩展的节点数,与或树的搜索策略,与或树的一般搜索过程,搜索的目的是考察S0是否有解S0扩展（分解或等价变换）设置父指针选择节点,节点可解，其不可解的后裔节点可删去节点不可解，其全部后裔节点可删去,标示过程：1）判断祖先节点的
25、可解/不可解性2）删去无用的后裔节点：,：非终止节点：终止节点,与或树的广度优先搜索,：非终止节点：终止节点,与或树的广度优先搜索,：非终止节点：终止节点,与或树的广度优先搜索,：非终止节点：终止节点,与或树的广度优先搜索,：非终止节点：终止节点,：从OPEN中删去,与或树的广度优先搜索,：非终止节点：终止节点,：在CLOSED中，无需再考虑的节点,与或树的广度优先搜索,：非终止节点：终止节点,：在CLOSED中，无需再考虑的节点,与或树的广度优先搜索,：非终止节点：终止节点,：在CLOSED中，无需再考虑的节点,与或树的广度优先搜索,：非终止节点：终止节点,：在CLOSED中，无需再考虑的节
26、点,与或树的广度优先搜索,：非终止节点：终止节点,：在CLOSED中，无需再考虑的节点,与或树的广度优先搜索,：非终止节点：终止节点,：在CLOSED中，无需再考虑的节点,与或树的广度优先搜索,与或树的有序搜索过程,求代价最小解树的方法分析节点被扩展的代价，选择扩展代价最小的节点扩展解树的代价h(S0)计算准则,倒推，估算，每次刷新,希望树：由最有希望（依代价）成为最优解树的那一部分节点及其先辈（含S0）组成,:非终止节点:终止节点,:不可解端节点,1,1,3,1,1,5,6,2,2,2,2,2,11,13,3,4,6,8,0,0,0,0,0,和代价计算,右解树：h(S0)=8左解树：h(S0
27、)=13,S0,3,3,3,2,7,边代价为1：T树,8,每次扩展2层,S0,3,3,2,11,边代价为1：T树,8,2,2,3,2,6,7,7,S0,3,2,11,边代价为1：T树：从OPEN中 删去,8,2,2,3,2,6,7,7,2,0,0,2,6,2,3,S0,3,2,11,边代价为1：T树：从OPEN中 删去,8,2,2,3,2,6,7,7,0,0,2,3,：在CLOSED中，无需再考虑的节点,S0,2,11,边代价为1：T树：从OPEN中 删去,8,2,2,3,2,6,7,7,0,0,2,3,3,0,0,2,6,2,3,9,：在CLOSED中，无需再考虑的节点,博弈树的启发式搜索,
28、博弈过程：二人零和：博弈结果只有胜、负、平三种情况 全信息：当前及过往局势全开放 非偶然：双方都理智决定行为（选择最有利于己方的策略）博弈树构成 初始格局记为S0“AND”和“OR”逐层交替出现，己方扩展的为“OR”，对方为“AND”使己方获胜的终局为可解节点，对方获胜的为不可解节点极大极小分析法 端节点用估价函数估值，反推上层节点估值OR(Max),AND(Min)，直至根节点估值大的方案较好（按获利）博弈树扩展深度越大越精确，但计算量庞大，通常一定深度,例：一字棋，A方：a棋；B方：b棋；扩展深度：2层,估价函数e(p)定义：,p是A方胜局,p是B方胜局e(+p)-e(-p),p是未定局0
29、,p是和局,e(p),e(+p)：可使a成为三子一线的数目e(-p)：可使b成为三子一线的数目,-剪枝技术,边生成估值边计算倒推值，从而剪去某些分支的技术值：“AND”节点，当前子节点中最小值（上界）值：“OR”节点，当前子节点中最大值（下界）剪枝：IF“OR”节点X的值祖先“AND”节点的值 THEN 终止该“OR”节点后面的搜索，X的倒推值剪枝：IF“AND”节点X的值祖先“OR”节点的值 THEN 终止该“AND”节点后面的搜索，X的倒推值顺序：剪枝顺序自左至右或自右至左,2,8,4,2,2,1,1,-2,-2,2,2,5,9,5,5,2,2,1,1,1,-5,-5,1,1,1,2,搜索
30、的完备性与效率,完备性：若问题可解则搜索过程一定能找解，称这样的搜索过程为完备的，完备的搜索过程也称为搜索算法广度类，改进的有界深度，A*完备搜索效率之外显率(渗透率)：P=L/T1 L:S0Sg的最优路径长度;T:搜索生成的节点总数 P越小效率越低。P=1,搜索效率之有效分枝因数 定义：满足式：B+B2+BL=T 的数B 意义：每一有效节点平均生成的节点数目，越小越好 关联：解释：（可绘制如下关系图表）固定B，则L越大P越小，即有效分枝因数固定的情况下，最优解越远，搜索效率越低 固定L，则B越大P越小T越大，即最优解一定的情况下，有效分枝因数越大，搜索生成的节点总数越多，搜索效率越低,8数码问题不同搜索算法的有效分支因子比较,问题：盲目搜索为什么只适用于树状结构？对于有限状态结构，深度优先搜索为什么会出现无穷分支的情况？如何在盲目搜索中避免重复状态？对广度和深度优先算法这种策略有何不同？了解若干经典搜索问题的最新进展，如：皇后问题，滑块问题，TSP问题，规划问题，巡游问题等。是否存在比较通用的启发函数的构造方法？8数码问题的所有状态可以划分为两个互不相交的集合，如何说明？能否找到8数码问题更有效的启发式函数？A*算法除了具有完备性之外，是否在效率上优于一般的启发式算法？,
