《人工智能 AI讲稿5(搜索student)》由会员分享，可在线阅读，更多相关《人工智能 AI讲稿5(搜索student)（87页珍藏版）》请在金锄头文库上搜索。
1、人工智能（人工智能（Artificial Intelligence）基本原理基本原理福州大学数学与计算机学院福州大学数学与计算机学院陈昭炯陈昭炯8/8/20242021/7/11第六章第六章 搜索策略搜索策略基本概念基本概念 状态空间的搜索策略状态空间的搜索策略 与与/或树的搜索策略或树的搜索策略 搜索的完备性与效率搜索的完备性与效率一般图的搜索过程一般图的搜索过程广度优先搜索广度优先搜索深度优先搜索深度优先搜索有界深度优先搜索有界深度优先搜索代价树的广度优先搜索代价树的广度优先搜索代价树的深度优先搜索代价树的深度优先搜索启发式搜索启发式搜索A*算法算法与与/或树的一般搜索过程或树的一般搜索过
2、程与与/或树的广度优先搜索或树的广度优先搜索与与/或树的深度优先搜索或树的深度优先搜索与与/或树的有序搜索或树的有序搜索博弈树的启发式搜索博弈树的启发式搜索 剪枝技术剪枝技术搜索的含义搜索的含义状态空间表示法状态空间表示法与与/或树表示法或树表示法2021/7/12搜索的含义搜索的含义依问题的实际情况寻找可利用的知识，构造代价较少的推理路径从依问题的实际情况寻找可利用的知识，构造代价较少的推理路径从而解决问题的过程而解决问题的过程离散的问题通常没有统一的求解方法离散的问题通常没有统一的求解方法搜索策略的优劣涉及能否找到最好的解、计算时间、存储空间等搜索策略的优劣涉及能否找到最好的解、计算时间、
3、存储空间等搜索分为盲目搜索和启发式搜索搜索分为盲目搜索和启发式搜索盲目搜索：按预定的策略进行搜索，未用问题相关的或中间信息改盲目搜索：按预定的策略进行搜索，未用问题相关的或中间信息改进搜索。效率不高，难求解复杂问题，但不失可用性进搜索。效率不高，难求解复杂问题，但不失可用性启发式搜索：搜索中加入问题相关的信息加速问题求解，效率较高，启发式搜索：搜索中加入问题相关的信息加速问题求解，效率较高，但启发式函数不易构造但启发式函数不易构造讨论的问题讨论的问题有哪些常用的搜索算法有哪些常用的搜索算法? 问题有解时能否找到解问题有解时能否找到解?(完备性完备性)找到的解是最佳的吗？找到的解是最佳的吗？(最
4、优性最优性) 什么情况下可以找到最佳解什么情况下可以找到最佳解？求解的效率如何求解的效率如何?（时间、空间复杂度）（时间、空间复杂度）基本概念基本概念2021/7/13状态空间表示法状态空间表示法状态：描述问题求解中任一时刻的状况；变量的有序组合状态：描述问题求解中任一时刻的状况；变量的有序组合算符：一个状态算符：一个状态另一状态的操作另一状态的操作状态空间：状态空间：状态，算符状态，算符 表示表示 ,描述形式算符描述形式算符问题求解过程：问题求解过程：初始状态：描述问题求解中的初始状况初始状态：描述问题求解中的初始状况算符：一个状态算符：一个状态另一状态的操作另一状态的操作目标测试：确定给定
5、的状态是否为目标状态目标测试：确定给定的状态是否为目标状态路径耗散函数：设定每一步算符操作的耗散值路径耗散函数：设定每一步算符操作的耗散值问题的解问题的解：从初始状态到目标状态的路径：从初始状态到目标状态的路径最优解最优解：所有解中耗散值最小的解：所有解中耗散值最小的解2021/7/14例：二阶梵塔问题例：二阶梵塔问题状态描述：状态描述：（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从
6、从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,1), B(3,2)2021/7/15猴子摘香蕉问题猴子摘香蕉问题abc2021/7/16操作符：操作符：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: 猴子
7、拿到香蕉猴子拿到香蕉 (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)可能状态：可能状态：(b,a,b,0,0) (c,a,c,1,0) (c,a,c,1,1) 2021/7/17例：修道士与野人问题例：修道士与野人问题(1968)S0：
8、河左岸有：河左岸有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种种2021/7/18(3,3,1)(3,1,0)(2,2,0)(3,2,0)(3,2,1)(3,0,0)(3,1,1)(1,1,0)(2,2,
9、1)(0,2,0)(0,3,1)(0,1,0)(0,2,1)(0,0,0)0x+y2:(x,y)=(2,0), (0,2),(1,1),(1,0),(0,1)(1,1,1)2021/7/19例：皇后问题例：皇后问题初始状态：棋盘上无皇后初始状态：棋盘上无皇后算符：将皇后添加到棋盘上的任一空格算符：将皇后添加到棋盘上的任一空格目标测试：目标测试：8皇后都在棋盘上，且互相攻击不到皇后都在棋盘上，且互相攻击不到路径耗散函数：每一步耗散值路径耗散函数：每一步耗散值1将将4个皇后放到棋盘中，个皇后放到棋盘中，使得彼此不会攻击到使得彼此不会攻击到（不同行、不同列、（不同行、不同列、不同对角线）不同对角线）
10、返回返回8皇后，皇后，92种解种解找到一般找到一般n皇后问题复杂度为皇后问题复杂度为O(n)的算法的算法(1989)QQQQ2021/7/1102 8 31 6 47 51 2 38 47 6 5例：八数码游戏例：八数码游戏 8-Puzzle（九宫重排问题）（九宫重排问题） sliding-block puzzle初始状态：任一状态都可为初始状态初始状态：任一状态都可为初始状态算符：将空位移向四个方向算符：将空位移向四个方向目标测试：确定当前状态是否为目标状态目标测试：确定当前状态是否为目标状态路径耗散函数：每一步耗散值路径耗散函数：每一步耗散值1其状其状态可以划分可以划分为两个不相交的集合。
11、两个不相交的集合。(证明证明)8数数码， 9！/2181440 ；15数数码，1.3万万亿；24数数码,1025一般一般nn数码是数码是NP完全完全问题（1986）2021/7/111例：例：TSP问题问题Traveling Salesman Problem从某城市出发遍历所有从某城市出发遍历所有n个城市个城市一遍且仅一遍再回到出发地，求一遍且仅一遍再回到出发地，求最短路径最短路径初始状态：在某一城市初始状态：在某一城市算符：移向下一个未访问过的城市算符：移向下一个未访问过的城市目标测试：是否处于出发地且访问过所有城市一次目标测试：是否处于出发地且访问过所有城市一次路径耗散函数：路程长度，旅行
12、费用等路径耗散函数：路程长度，旅行费用等No general method of solution is knownNPhard(Karp,1972)有效的启发式算法（有效的启发式算法（1973）完全多项式近似方案（完全多项式近似方案（1998）2021/7/112与与/或树表示法（分解，分治）或树表示法（分解，分治）与树与树 或树或树与或树与或树2021/7/113例：三阶梵塔问题例：三阶梵塔问题状态描述：状态描述：（ SC,SB, SA)(1,1,1) (3,3,3)(1,2,2,)(3,2,2)(1,1,1) (1,2,2)(3,2,2) (3,3,3)(1,1,1) (1,1,3)(1
13、,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)2021/7/114本原问题本原问题:不可分解，不可分解，直接可解的问题直接可解的问题端节点端节点：无子节点的节：无子节点的节点点终止节点终止节点：本原问题对：本原问题对应的节点，可解应的节点，可解可解可解/不可解节点不可解节点：端：端节点，或节点，与节点节点，或节点，与节点解树解树：始节点（可解）：始节点（可解）可解节点可解节点2021/7/115若干应用实例若干应用实例寻径问题：计算机网络的路由，军事行动的规划，飞机航寻径问题：计算机网络的路由，
14、军事行动的规划，飞机航线旅行规划系统，机器人导航（寻径问题拓广）线旅行规划系统，机器人导航（寻径问题拓广）旅行问题：电路板自动钻孔机的运动规划，仓库货物码放旅行问题：电路板自动钻孔机的运动规划，仓库货物码放机机 的运动规划的运动规划超大规模集成电路的布局：在一个芯片上放置上百万个元超大规模集成电路的布局：在一个芯片上放置上百万个元器件及连线，还要达到芯片面积最小、电路延迟最小、杂散器件及连线，还要达到芯片面积最小、电路延迟最小、杂散电容最小和产量最大。单元布局和通道寻径（电容最小和产量最大。单元布局和通道寻径（1991）自动装配排序：找到一个装配物体（电动机）各部件的次自动装配排序：找到一个装
15、配物体（电动机）各部件的次序序蛋白质设计：寻找一个氨基酸序列，当该序列叠放在蛋白质设计：寻找一个氨基酸序列，当该序列叠放在3D的的蛋白质结构里，可治愈某种疾病蛋白质结构里，可治愈某种疾病因特网搜索：寻找问题的答案、相关信息等因特网搜索：寻找问题的答案、相关信息等2021/7/116一般图的搜索过程一般图的搜索过程OPEN表：存放刚生成的节点表：存放刚生成的节点CLOSED表：存放当前将要扩展和前面已扩展的节点表：存放当前将要扩展和前面已扩展的节点扩展一个节点：生成出该节点的所有后继节点，并给出它们扩展一个节点：生成出该节点的所有后继节点，并给出它们 之间的耗散值。之间的耗散值。状态节点状态节点
16、 父节点父节点编号编号状态节点状态节点父节点父节点状态空间的搜索策略状态空间的搜索策略2021/7/1171）S0OPEN，S0G0，2）OPEN=Nil无解；否则无解；否则3）OPEN的第一个节点的第一个节点CLOSED，记为，记为n4）节点）节点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 xC
17、LOSED(已扩展过已扩展过), 判断判断x的后继节点的父的后继节点的父指针是否需改变指针是否需改变7）按某种搜索策略对）按某种搜索策略对OPEN表排序表排序队列方式队列方式(FIFO)：广度优先：广度优先; 堆栈方式（堆栈方式（LIFO）：深度优先）：深度优先8）转）转2）2021/7/118已扩展已扩展 ( CLOSED ) 已生成，未扩展已生成，未扩展(OPEN)选中当前正扩展选中当前正扩展2021/7/119已扩展已扩展 ( CLOSED ) 已生成，未扩展已生成，未扩展(OPEN)选中当前正扩展选中当前正扩展2021/7/120已扩展已扩展 ( CLOSED ) 已生成，未扩展已生成
18、，未扩展(OPEN)选中当前正扩展选中当前正扩展2021/7/121已扩展已扩展 ( CLOSED ) 已生成，未扩展已生成，未扩展(OPEN)选中当前正扩展选中当前正扩展2021/7/1221）不同的搜索策略只是）不同的搜索策略只是OPEN表的排序不同，过程类似表的排序不同，过程类似2）G称为搜索图，由节点及其父指针称为搜索图，由节点及其父指针搜索树搜索树3）目标找到后，其路径由逐级上行的父指针构成）目标找到后，其路径由逐级上行的父指针构成4）盲目搜索仅适用于树结构，不出现图搜索中）盲目搜索仅适用于树结构，不出现图搜索中6）一些基本概念和记号一些基本概念和记号节点深度：节点深度：根节点深度根
19、节点深度=0其它节点深度其它节点深度=父节点深度父节点深度+101232021/7/123路径的代价（耗散值）路径的代价（耗散值）一条路径的代价（耗散值）等于连接这条路径各节一条路径的代价（耗散值）等于连接这条路径各节点间所有代价（耗散值）的总和。用点间所有代价（耗散值）的总和。用C(xi, xj)表示从父节表示从父节点点xi到到子节点子节点xj的边代价（耗散值）的边代价（耗散值） 。代价树：边上标有代价的树状结构图代价树：边上标有代价的树状结构图若干记号：若干记号：S0初始态；初始态；Sg目标态；目标态；g(x)从从S0到节点到节点x的代价；的代价；g(xj)=g(xi)+ C(xi, xj
20、)h(x)x到到Sg最最优路径的估计代价优路径的估计代价2021/7/124广度优先搜索广度优先搜索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), 并标记并标
21、记M中的节点中的节点到到n的指针的指针;9, GO LOOP;ADD(x,y):添加添加x至至y的尾部的尾部2021/7/125广度优先搜索广度优先搜索2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目标
22、目标82 3 41 8 7 6 54生成的新节点按队列方式压入生成的新节点按队列方式压入OPEN表底部（先进先出）表底部（先进先出）2021/7/126深度优先搜索深度优先搜索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中中 THE
23、N EXIT(SUCCESS);8, ADD(OPEN,M), 并标记并标记M中的节点中的节点到到n的指针的指针;9, GO LOOP;ADD(x,y):添加添加x至至y的尾部的尾部2021/7/127深度优先搜索深度优先搜索2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6
24、 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 6123456789abcd1 2 3 8 47 6 5目标目标2021/7/128广度优先搜索效率分析广度优先搜索效率分析每个节点有每个节点有b个后继节点；解的深度为个后继节点；解的深度为d最坏情况已生成的节点数最坏情况已生成的节点数深度深度 节点数节点数 时间时间 内存内存 2 1100 0.11s 1 M 4 111，100 11s 106 M 6 107 19m 10 G(KM) 8 109 31h 1
25、 T(KG) 10 1011 129d 101 T(KG) 12 1013 35y 10 P(KT) 14 1015 3523y 1 E(KP)b=10生成生成104个节点个节点/s占用占用103 bytes/node深度优先搜索效率分析深度优先搜索效率分析存储的节点数存储的节点数bd+1；b=10,d=12, 存储空间存储空间118K；O(bd);百亿倍百亿倍2021/7/129深度优先搜索的性质深度优先搜索的性质一般不能保证找到最优解一般不能保证找到最优解当深度限制不合理时，可能找不到解（无穷分支）当深度限制不合理时，可能找不到解（无穷分支）最坏情况时，搜索空间等同于穷举最坏情况时，搜索空
26、间等同于穷举时间效率较低时间效率较低是一个通用的与问题无关的方法是一个通用的与问题无关的方法当问题有解时，一定能找到解当问题有解时，一定能找到解是一个通用的与问题无关的方法是一个通用的与问题无关的方法最坏情况时，搜索空间等同于穷举最坏情况时，搜索空间等同于穷举时间、空间效率较低时间、空间效率较低广度优先搜索的性质广度优先搜索的性质2021/7/130有界深度优先搜索（迭代深入）有界深度优先搜索（迭代深入）设定深度界限设定深度界限dm，找不到时逐渐加深找不到时逐渐加深避免搜索陷入某一无穷分支死循环避免搜索陷入某一无穷分支死循环问题有解一定可以找到解，但不一定最优问题有解一定可以找到解，但不一定最
27、优当搜索空间很大且解的深度未知时，首选的盲目搜索法当搜索空间很大且解的深度未知时，首选的盲目搜索法代价树广度优先搜索代价树广度优先搜索每次扩展的子节点返送回每次扩展的子节点返送回OPEN时，都对时，都对OPEN表所有表所有点按代价从小到大重新排序点按代价从小到大重新排序代价树深度优先搜索代价树深度优先搜索从刚扩展的子节点中选一个代价最小的送入从刚扩展的子节点中选一个代价最小的送入CLOSED表中进行扩展表中进行扩展回溯搜索回溯搜索每次只生成一个后继节点而不是所有的后继，内存每次只生成一个后继节点而不是所有的后继，内存O(d)2021/7/131( )回溯搜索例：皇后问题回溯搜索例：皇后问题皇后
28、问题皇后问题2021/7/132( )Q(1,1)2021/7/133( )QQ(1,1)(1,1) (2,3)2021/7/134( )Q(1,1)(1,1) (2,3)2021/7/135( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)2021/7/136( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)Q(1,1) (2,4) (3.2)2021/7/137( )QQ(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)2021/7/138( )Q(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4)
29、(3.2)2021/7/139( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)2021/7/140( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)2021/7/141( )(1,1)(1,1) (2,3)(1,1) (2,4)(1,1) (2,4) (3.2)Q(1,2)Q(1,2) (2,4)2021/7/142( )(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)2021/7/
30、143( )(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) (4,3)2021/7/144例：找一条从例：找一条从A到到E的最短路径的最短路径EEBDECEDBCA3334445522代价树广度优先搜索代价树广度优先搜索是否需遍历所有路径才可确定最短？是否需遍历所有路径才可确定最短？2021/7/145例：找一条从例：找一条从A到到E的最短路径的最短路径EEBDECEDBCA3334445522代价树广度优先搜索代价树广度优先搜索是否需遍历所有路
31、径才可确定最短？是否需遍历所有路径才可确定最短？2021/7/146例：找一条从例：找一条从A到到E的最短路径的最短路径EEBDECEDBCA3334445522代价树深度优先搜索代价树深度优先搜索深度与广度搜索扩展的深度与广度搜索扩展的节点数相同节点数相同2021/7/147启发式搜索启发式搜索设计一个与问题相关的估价函数，用于评价各节点的重设计一个与问题相关的估价函数，用于评价各节点的重要程度要程度按照节点的重要性次序，亦即估价函数从小到大的顺序按照节点的重要性次序，亦即估价函数从小到大的顺序扩展节点扩展节点估价函数的形式：估价函数的形式：f(x)=g(x)+h(x) g(x)从从S0到节
32、点到节点x已付出的代价；已付出的代价； h(x)x到到Sg最优路径的最优路径的估计估计代价代价;g(x)比例越大，越倾向广度优先搜索，完备性较好而效比例越大，越倾向广度优先搜索，完备性较好而效率可能受影响；率可能受影响；h(x)比例越大，越倾向深度优先搜索，效率可能较好；比例越大，越倾向深度优先搜索，效率可能较好；加权调整比例加权调整比例,引入启发知识，在保证找到最佳解的情引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。况下，尽可能减少搜索范围，提高搜索效率。2021/7/148例：例： B:Black; W:White; E:Empty;将将B全移至全移至W右边；至
33、多移右边；至多移3位；移位；移i位代价为位代价为i ，i=1,2,3BBBWWWEh(x)=3每个每个W左边左边B的个数的个数；还有？；还有？BBBWWWEBBBEWWWBBBWEWWBBBWWEW3+272+271+27BBEWWBW4+21EBBWWBWBEBWWBWBBWEWBWBBWWEBW6+215+215+216+21BWBEWBWBWBWEBW7+188+18EWBBWBWBWEBWBWBWBBWEW10+158+189+18WEBBWBW11+152021/7/149局部择优搜索（瞎子爬山法）局部择优搜索（瞎子爬山法）对刚扩展的子节点计算对刚扩展的子节点计算f(x)，选取其中选
34、取其中f(x)最小的一个节点最小的一个节点 CLOSED表进行扩展表进行扩展深度优先类搜索在此框架下可统一表示为：深度优先类搜索在此框架下可统一表示为：深度优先：记深度为深度优先：记深度为d(x)，则则f(x)=-d(x)代价树深度优先：代价树深度优先：f(x)=C(xi ,xj )全局择优搜索全局择优搜索每次对每次对OPEN表中所有节点计算表中所有节点计算f(x)，选取其中最小的一个选取其中最小的一个节点节点 CLOSED表进行扩展表进行扩展广优先类搜索在此框架下可统一表示为：广优先类搜索在此框架下可统一表示为：广度优先：记深度为广度优先：记深度为d(x)，则则f(x)=d(x)代价树广度优
35、先：代价树广度优先：f(x)=g(x)2021/7/150定义评价函数定义评价函数1：f1(n) = g(n) + h1(n)g(n)为从初始节点到当前节点的耗散值（深度）为从初始节点到当前节点的耗散值（深度）h1(n)为当前节点为当前节点“不在位不在位”的将牌数的将牌数 2 8 31 6 47 51 2 38 47 6 5例：九宫重排问题例：九宫重排问题h1(n) =4 2 8 31 6 47 51 2 3457 6 82021/7/1512 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47
36、6 52 8 31 47 6 52 8 37 1 4 6 5 8 32 1 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目标目标123456全局择优搜索全局择优搜索2021/7/152定义评价函数定义评价函数2：f2(n) = g(n) + h1(n)g(n)为从初始节点到当前节点的耗散值（深度）为从初始节点到当前节点的耗散值（深度）h2(n)为数字移到目标处的距离总和为数字移到目
37、标处的距离总和 2 8 31 6 47 5h2(n)111 2 51 2 38 47 6 52021/7/1532 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 31 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5s(5)A(7)B(5)C(7)D(7)E(5)F(7)I(5)J(7)K(5)L(5)M(7)目标目标12345全局择优搜索全局择优搜索2021/7/154A*算法
38、算法评价函数的格式：评价函数的格式：f(n) = g(n) + h(n)f(n)：评价函数；评价函数；h(n)：启发函数启发函数g*(n)：从从S0到到n的的最短最短路径的耗散值路径的耗散值 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*算法。算法。九宫问题解九
39、宫问题解1九宫问题解九宫问题解22021/7/155A*算法的性质算法的性质A*算法是可纳的：对于可解状态空间图，算法是可纳的：对于可解状态空间图，A*算法在有限步算法在有限步内终止并找到最优解。内终止并找到最优解。在在h(n)h*(n)的条件下，的条件下， h(n)的值越大，携带的启发式信息的值越大，携带的启发式信息越多，扩展的节点数越少，搜索效率越高。越多，扩展的节点数越少，搜索效率越高。*若若h(n)还满足如下的单调性（一致）条件还满足如下的单调性（一致）条件（三角不等式）（三角不等式）*： h(Sg)0 h(xi)- h(xj) C(xi ,xj ) ；xj 是是xi 的的后继子节点后
40、继子节点则：则：1）若）若A*选择选择xn进行扩展进行扩展,就有：就有：g(xn)= g*(xn) 2）由）由A*扩展的节点序列其扩展的节点序列其f(n)值非递减值非递减 3）一般图的搜索算法可简化）一般图的搜索算法可简化8数码的两种启发式算法数码的两种启发式算法？2021/7/156A*算法的不足与改进算法的不足与改进：大多数情况节点数为解长度的指数级，大多数情况节点数为解长度的指数级，存储量过大，保留了所有生成的节点，不适用于大规模问题存储量过大，保留了所有生成的节点，不适用于大规模问题存储限制的存储限制的A*算法算法启发式函数的精确度问题启发式函数的精确度问题：解的深度解的深度迭代有界深
41、度迭代有界深度A*(h1)A*(h2)24681012141618202224101126806384471273644035613203993227539130130567276180943913561218253973113211363676121916418数码问题数码问题扩展的节点扩展的节点数数2021/7/157与或树的搜索策略与或树的搜索策略与或树的一般搜索过程与或树的一般搜索过程搜索的目的是考察搜索的目的是考察S0是否有解是否有解S0扩展（分解或等价变换）扩展（分解或等价变换）设置父指针设置父指针选择节点选择节点节点可解，其不可解的后裔节点可删去节点可解，其不可解的后裔节点可删去
42、节点不可解，其全部后裔节点可删去节点不可解，其全部后裔节点可删去标示过程：标示过程：1）判断祖先节点的可解）判断祖先节点的可解/不可解性不可解性2）删去无用的后裔节点：）删去无用的后裔节点：2021/7/158：非终止节点非终止节点 ：终止节点：终止节点与与或或树树的的广广度度优优先先搜搜索索2021/7/159：非终止节点非终止节点 ：终止节点：终止节点与与或或树树的的广广度度优优先先搜搜索索2021/7/160：非终止节点非终止节点 ：终止节点：终止节点与与或或树树的的广广度度优优先先搜搜索索2021/7/161：非终止节点非终止节点 ：终止节点：终止节点与与或或树树的的广广度度优优先先搜
43、搜索索2021/7/162：非终止节点非终止节点 ：终止节点：终止节点：从：从OPEN中删去中删去与与或或树树的的广广度度优优先先搜搜索索2021/7/163 ：非终止节点非终止节点 ：终止节点：终止节点：在：在CLOSED中，无需再考虑的节点中，无需再考虑的节点与与或或树树的的广广度度优优先先搜搜索索2021/7/164 ：非终止节点非终止节点 ：终止节点：终止节点：在：在CLOSED中，无需再考虑的节点中，无需再考虑的节点与与或或树树的的广广度度优优先先搜搜索索2021/7/165 ：非终止节点非终止节点 ：终止节点：终止节点：在：在CLOSED中，无需再考虑的节点中，无需再考虑的节点与与
44、或或树树的的广广度度优优先先搜搜索索2021/7/166 ：非终止节点非终止节点 ：终止节点：终止节点：在：在CLOSED中，无需再考虑的节点中，无需再考虑的节点与与或或树树的的广广度度优优先先搜搜索索2021/7/167 ：非终止节点非终止节点 ：终止节点：终止节点：在：在CLOSED中，无需再考虑的节点中，无需再考虑的节点与与或或树树的的广广度度优优先先搜搜索索2021/7/168 ：非终止节点非终止节点 ：终止节点：终止节点：在：在CLOSED中，无需再考虑的节点中，无需再考虑的节点与与或或树树的的广广度度优优先先搜搜索索2021/7/169与或树的有序搜索过程与或树的有序搜索过程求代价
45、最小解树的方法求代价最小解树的方法分析节点被扩展的代价，选择扩展代价最小的节点扩展分析节点被扩展的代价，选择扩展代价最小的节点扩展解树的代价解树的代价h(S0)计算准则计算准则倒推，估算，每次刷新倒推，估算，每次刷新希望树：由最有希望（依代价）成为最优解树的那一部分节希望树：由最有希望（依代价）成为最优解树的那一部分节点及其先辈（含点及其先辈（含S0）组成组成2021/7/170 :非终止节点非终止节点 :终止节点终止节点:不可解端节点不可解端节点1131156222221113346800000和代价计算和代价计算右解树：右解树：h(S0)=8左解树：左解树：h(S0)=132021/7/1
46、71S033327边代价为边代价为1 ：T树树8每次扩展每次扩展2层层2021/7/172S033211边代价为边代价为1 ：T树树822326772021/7/173S03211边代价为边代价为1 ：T树树 ：从：从OPEN中中 删去删去8223267720026232021/7/174S03211边代价为边代价为1 ：T树树 ：从：从OPEN中中 删去删去822326770023：在：在CLOSED中，无需中，无需再考虑的节点再考虑的节点2021/7/175S0211边代价为边代价为1 ：T树树 ：从：从OPEN中中 删去删去82232677002330026239：在：在CLOSED中，
47、无需中，无需再考虑的节点再考虑的节点2021/7/176博弈树的启发式搜索博弈树的启发式搜索博弈过程：博弈过程： 二人零和：博弈结果只有胜、负、平三种情况二人零和：博弈结果只有胜、负、平三种情况 全信息：当前及过往局势全开放全信息：当前及过往局势全开放 非偶然：双方都理智决定行为（选择最有利于己方的策略）非偶然：双方都理智决定行为（选择最有利于己方的策略）博弈树构成博弈树构成 初始格局记为初始格局记为S0 “AND”和和“OR”逐层交替出现，己方扩展的为逐层交替出现，己方扩展的为“OR”，对方为对方为“AND” 使己方获胜的终局为可解节点，对方获胜的为不可解节点使己方获胜的终局为可解节点，对方
48、获胜的为不可解节点极大极小分析法极大极小分析法 端节点用估价函数估值，反推上层节点估值端节点用估价函数估值，反推上层节点估值OR(Max),AND(Min)，直至根节点直至根节点估值大的方案较好（按获利）估值大的方案较好（按获利）博弈树扩展深度越大越精确，但计算量庞大，通常一定深度博弈树扩展深度越大越精确，但计算量庞大，通常一定深度2021/7/177例：一字棋，例：一字棋，A方：方：a棋；棋；B方：方：b棋；扩展深度：棋；扩展深度：2层层ab估价函数估价函数e(p)定义：定义：, p是是A方胜局方胜局, p是是B方胜局方胜局e(+p)-e(-p), p是未定局是未定局0, p是和局是和局e(
49、p)a bab aab abe(+p)：可使：可使a成为三子一线的数目成为三子一线的数目e(-p )：可使：可使b成为三子一线的数目成为三子一线的数目2021/7/1782021/7/1792021/7/180 - 剪枝技术剪枝技术边生成估值边计算倒推值，从而剪去某些分支的技术边生成估值边计算倒推值，从而剪去某些分支的技术 值：值：“AND”节点，当前子节点中最小值（上界）节点，当前子节点中最小值（上界） 值：值：“OR”节点，当前子节点中最大值（下界）节点，当前子节点中最大值（下界） 剪枝：剪枝： IF“OR”节点节点X的的 值值祖先祖先“AND”节点的节点的 值值 THEN 终止该终止该“
50、OR”节点后面的搜索，节点后面的搜索， X的倒推值的倒推值 剪枝：剪枝： IF“AND”节点节点X的的 值值祖先祖先“OR”节点的节点的 值值 THEN 终止该终止该“AND”节点后面的搜索，节点后面的搜索， X的倒推值的倒推值顺序：剪枝顺序自左至右或自右至左顺序：剪枝顺序自左至右或自右至左2021/7/1812842211-2-2225955221 11-5-51 1122021/7/182搜索的完备性与效率搜索的完备性与效率完备性：若问题可解则搜索过程一定能找解，称这完备性：若问题可解则搜索过程一定能找解，称这样的搜索过程为完备的，完备的搜索过程也称为搜索样的搜索过程为完备的，完备的搜索过
51、程也称为搜索算法算法广度类，改进的有界深度，广度类，改进的有界深度，A *完备完备搜索效率之外显率搜索效率之外显率(渗透率渗透率)：P=L/T1 L:S0Sg的最优路径长度的最优路径长度; T:搜索生成的节点总数搜索生成的节点总数 P越小效率越低。越小效率越低。P=1 2021/7/183搜索效率之有效分枝因数搜索效率之有效分枝因数 定义：满足式：定义：满足式：B+B2+BL=T 的数的数B 意义：每一有效节点平均生成的节点数目，越小越好意义：每一有效节点平均生成的节点数目，越小越好 关联：关联： 解释：（解释：（可绘制如下关系图表）可绘制如下关系图表） 固定固定B，则则L越大越大P越小，即有
52、效分枝因数固定的情况下，越小，即有效分枝因数固定的情况下，最优解越远，搜索效率越低最优解越远，搜索效率越低 固定固定L，则则B越大越大P越小越小T越大，即最优解一定的情况下，越大，即最优解一定的情况下，有效分枝因数越大，搜索生成的节点总数越多，搜索效率有效分枝因数越大，搜索生成的节点总数越多，搜索效率越低越低2021/7/184解的深度解的深度迭代有界深度迭代有界深度A*(h1)A*(h2)246810121416182022242.452.872.732.802.792.78 - - - - - -1.791.481.341.331.381.421.441.451.461.471.481.4
53、81.791.451.301.241.221.241.231.251.261.271.281.268数码问题不同搜索算法的有效分支因子比较数码问题不同搜索算法的有效分支因子比较2021/7/185问题问题：盲目搜索为什么只适用于树状结构？盲目搜索为什么只适用于树状结构？对于有限状态结构，深度优先搜索为什么会出现无穷分支的情对于有限状态结构，深度优先搜索为什么会出现无穷分支的情况？况？如何在盲目搜索中避免重复状态？对广度和深度优先算法这种如何在盲目搜索中避免重复状态？对广度和深度优先算法这种策略有何不同？策略有何不同？了解若干经典搜索问题的最新进展，如：皇后问题，滑块问题，了解若干经典搜索问题的最新进展，如：皇后问题，滑块问题，TSP问题，规划问题，巡游问题等。问题，规划问题，巡游问题等。是否存在比较通用的启发函数的构造方法？是否存在比较通用的启发函数的构造方法？8数码问题的所有状态可以划分为两个互不相交的集合，如何说数码问题的所有状态可以划分为两个互不相交的集合，如何说明？明？能否找到能否找到8数码问题更有效的启发式函数？数码问题更有效的启发式函数？A*算法除了具有完备性之外，是否在效率上优于一般的启发式算法除了具有完备性之外，是否在效率上优于一般的启发式算法？算法？2021/7/186 结束语结束语若有不当之处，请指正，谢谢！若有不当之处，请指正，谢谢！
