人工智能技术人工智能技术第三章第三章 搜索技术搜索技术 课程主要内容o第一章 绪论第一章 绪论o第二章 知识表示第二章 知识表示 o第三章 搜索技术第三章 搜索技术o第四章 推理技术第四章 推理技术o第五章 机器学习第五章 机器学习 o第六章 专家系统第六章 专家系统 第三章 搜索技术第三章 搜索技术o搜索概念搜索概念n搜索：搜索什么？在哪搜索：搜索什么？在哪里搜索？适用范围？里搜索？适用范围？n在状态空间，寻找一条在状态空间，寻找一条从初始节点从初始节点到到目标节点目标节点的路径A,47B1,77B3,52B2,65C2,87 C1,96D1,77 E1,57E2,92F1,32G1,27H1,51 搜索分类搜索分类1 1、、盲目式摸索：盲目式摸索：无信息搜索，搜索时按规定顺序无信息搜索，搜索时按规定顺序逐个考察节点，直到找到目标通用性强，但效逐个考察节点，直到找到目标通用性强，但效率低；适用于简单树状结构问题率低；适用于简单树状结构问题 包括：包括：宽度优先、深度优先、等代价搜索宽度优先、深度优先、等代价搜索2 2、、启发式搜索：启发式搜索：用到自身的某些信息，指导搜索用到自身的某些信息，指导搜索朝着最有希望的方向进行，搜索效率高。
朝着最有希望的方向进行，搜索效率高第三章 搜索技术第三章 搜索技术 o盲目搜索n只是可以区分出哪个是目标状态n一般是按预定的搜索策略进行搜索n没有考虑到问题本身的特性，这种搜索具有很大的盲目性，效率不高，不便于复杂问题的求解 o启发式搜索n是在搜索过程中加入了与问题有关的启发式信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解并找到最优解 第三章 搜索技术第三章 搜索技术搜索分类搜索分类 本章内容o3.1 3.1 盲目搜索盲目搜索o3.2 3.2 启发式搜索启发式搜索o3.3 3.3 博弈树搜索博弈树搜索o3.4 3.4 遗传算法遗传算法o3.5 3.5 模拟退火算法模拟退火算法o3.6 3.6 免疫算法免疫算法 A,47B1,77B3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51例例3.1 3.1 从王某家族的四代中找王从王某家族的四代中找王A A的后代且其寿的后代且其寿命为命为X=57X=57的人的人一、一、 图搜索策略图搜索策略王A:寿命47，有儿子王B1、王B3、王B2王B1:寿命77，有儿子王C1、王C2王B3:寿命52，有儿子王1王B2:寿命65，有儿子王E1、王E2王C1:寿命96王王C2:寿命寿命87，有儿子王，有儿子王F1王王D1:寿命寿命77，没有儿子，没有儿子王王E1：寿命：寿命57，有儿子王，有儿子王G1王王E2：寿命：寿命92，有儿子王，有儿子王H1王F1：寿命32王G1：寿命27，没有儿子王H1：寿命51 A,47B1,77B3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51例例3.1 3.1 从王某家族的四代中找王从王某家族的四代中找王A A的后代且其寿的后代且其寿命为命为X X的人的人( (设设X=57)X=57)一、一、 图搜索策略图搜索策略n搜索目标n搜索空间n搜索策略 3.1 盲目搜索盲目搜索一、一、 图搜索策略图搜索策略——在图中寻找路径的方法在图中寻找路径的方法1.1.两种数据结构两种数据结构 （（1 1））OPEN表表 存放已生成但还没考察的节点，即待考存放已生成但还没考察的节点，即待考察节点。
察节点 （（2））CLOSED表表存放考察过的节点，以及节点之间的关存放考察过的节点，以及节点之间的关系，如每个节点指向父节点的编号（返回指针）系，如每个节点指向父节点的编号（返回指针） CLOSED表中存放的就是一定搜索策略下的表中存放的就是一定搜索策略下的搜索树搜索树 2. 搜索树搜索树 搜索过程中经过（考搜索过程中经过（考察过）的节点和边，按原察过）的节点和边，按原图的连接关系，所构成一图的连接关系，所构成一个树型的有向图，称为个树型的有向图，称为搜搜索树索树 搜索树是一个搜索过搜索树是一个搜索过程的程的搜索轨迹搜索轨迹，或称之为，或称之为搜索空间搜索空间A,47B1,77B3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51 一、图搜索策略一、图搜索策略3.3.图搜索的一般过程图搜索的一般过程 (1) (1) 建立一个只含有起始节点建立一个只含有起始节点S S的搜索图的搜索图G G，把，把S S放到放到OPENOPEN表中 (2) (2) 建立一个建立一个CLOSEDCLOSED表，其初表，其初始为空表。
始为空表 (3) (3) LOOPLOOP：：若若OPENOPEN表是空表，表是空表，则失败退出则失败退出 A,47A 一、图搜索策略一、图搜索策略3.3.图搜索的一般过程图搜索的一般过程 (4) (4) 选择选择OPENOPEN表上的第一个节表上的第一个节点，把它从点，把它从OPENOPEN表移出并放进表移出并放进CLOSEDCLOSED表中称此节点为表中称此节点为节点节点n n (5) (5) 若若n n为一目标节点，则成为一目标节点，则成功退出此解此解是搜索图是搜索图G G中沿着指中沿着指针从针从n n到到S S这条路径这条路径而得到的而得到的( (指针指针在第在第7 7步中设置步中设置) ) A,47A 一、图搜索策略一、图搜索策略3.3.图搜索的一般过程图搜索的一般过程 (6) (6) 扩展节点扩展节点n n，生成后继节，生成后继节点 (7) (7) 把把n n的后继节点放入的后继节点放入OPENOPEN表的末端，提供返回节点表的末端，提供返回节点n n的指针的指针AA,47B1,77B3,52B2,65B1B2B33.3.图搜索的一般过程图搜索的一般过程 (6) (6) 扩展节点扩展节点n n，生成后继节，生成后继节点。
点 (7) (7) 把把n n的后继节点放入的后继节点放入OPENOPEN表的末端，提供返回节点表的末端，提供返回节点n n的指针的指针 (8) (8) 按某一任意方式或按某个按某一任意方式或按某个探试值，探试值，重排重排OPENOPEN表表 (9) GO (9) GO LOOPLOOP 3.1 盲目搜索4. 搜索过程框图搜索过程框图开始开始S0放入放入OPEN表表OPEN表空表空？？将将OPEN表中第一个节点表中第一个节点(n)移至移至CLOSE表表n是目标节点？是目标节点？修改指针方针，重排修改指针方针，重排OPEN表表扩展节点扩展节点n，把，把n的后继节点放入的后继节点放入OPEN表末端，提供指向表末端，提供指向节点节点n的指针的指针失败失败成功成功是是是是否否否否 5.5.图搜索方法分析：图搜索方法分析： （（1 1））策略：各种策略：各种搜索策略的搜索策略的区别区别主要体现在主要体现在OPENOPEN表排序准则表排序准则的不同的不同 （（2 2））成功：成功：每当扩展节点为每当扩展节点为目标节点时，宣告目标节点时，宣告成功结束成功结束。
这这时，能够时，能够重现这条重现这条成功路径成功路径，， （（3 3））失败：失败：当搜索树不再剩当搜索树不再剩有未被扩展的端节点时，过程就有未被扩展的端节点时，过程就以以失败告终失败告终在失败终止的情况在失败终止的情况下，从起始节点出发，一定达不下，从起始节点出发，一定达不到目标节点到目标节点 一、图搜索策略一、图搜索策略(Graph Search)(Graph Search)A,47B1,77B3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51 二、宽度优先搜索二、宽度优先搜索A,47B1,77B3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51例例3.1 3.1 从王某家族的四代中找王从王某家族的四代中找王A A的后代且其寿的后代且其寿命为命为X X的人的人( (设设X=57)X=57)搜索搜索8 8步找到步找到 3.1 盲目搜索二、宽度优先搜索二、宽度优先搜索p宽度优先搜索宽度优先搜索 搜索是以接近起始节点的搜索是以接近起始节点的程度依次扩展节点程度依次扩展节点。
p宽度优先搜索的基本思想宽度优先搜索的基本思想宽度优先搜索的基本思想宽度优先搜索的基本思想 深度深度优先搜索是严格按节优先搜索是严格按节点在树中的出现位置一层一点在树中的出现位置一层一层向下的搜索过程层向下的搜索过程 通过将通过将OPENOPEN表表设计为一个设计为一个队列来实现，将新生成的子队列来实现，将新生成的子节点放在节点放在OPENOPEN表的后面，保表的后面，保证证先生成的节点先考察先生成的节点先考察（（FIFOFIFO）） A,47B1,77B3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51 宽度优先搜索示意图宽度优先搜索示意图OPENOPEN表表节点节点父节点父节点ANULLB1AB3AB2AC2B1C1B1D1B3E1B2E2B2CLOSECLOSE表表编号编号节点节点 父节点父节点1ANULL2B1A3B3A4B2AAB1B3B2C2C1D1E1E2搜索图（搜索图（搜索树搜索树）） 二、宽度优先搜索二、宽度优先搜索p宽度优先搜索算法宽度优先搜索算法(1) (1) 把起始节点放到把起始节点放到OPENOPEN表中表中( (如果该起始节点为一目标节如果该起始节点为一目标节点，则求得一个解答点，则求得一个解答) )。
2) (2) 如果如果OPENOPEN是空表，则没有解，失败退出；否则继续是空表，则没有解，失败退出；否则继续3) (3) 把第一个节点把第一个节点( (节点节点n)n)从从OPENOPEN表表移出移出，并把它放入，并把它放入CLOSEDCLOSED的扩展节点表中的扩展节点表中4) (4) 扩展节点扩展节点n n若没有后继节点，则转向第若没有后继节点，则转向第(2)(2)步5) (5) 把把n n的所有后继节点放到的所有后继节点放到OPENOPEN表的表的末端末端，并提供从这些，并提供从这些后继节点回到后继节点回到n n的指针6) (6) 如果如果n n的任一个后继节点是个目标节点，则找到一个解的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第答，成功退出；否则转向第(2)(2)步 例例3.2 3.2 八数码问题八数码问题 操作规定操作规定: : 允许空格四周上、下、左、右的数允许空格四周上、下、左、右的数码块移入空格中，不许斜方向移动，不许返回先码块移入空格中，不许斜方向移动，不许返回先辈结点 二、宽度优先搜索二、宽度优先搜索 1 2 38 57 4 611 2 38 5 67 481 38 2 57 4 6101 2 38 4 5 7 671 2 38 4 57 6 6 1 38 2 57 4 6111 2 38 4 57 621 2 38 5 7 4 631 38 2 57 4 641 2 37 8 5 4 612 2 31 8 57 4 6131 2 38 47 6 5141 2 3 4 58 7 6151 28 5 37 4 6171 3 58 27 4 6188 1 3 2 57 4 6191 2 37 8 54 6202 31 8 5 7 4 6211 28 4 37 6 5221 2 3 8 57 4 651 28 5 37 4 69161 2 38 5 67 4 o宽度优先搜索的特点宽度优先搜索的特点：：nOPENOPEN表表是一个是一个队列队列，，先进先进先出（先出（FIFOFIFO））。
CLOSEDCLOSED表表是一个是一个顺序表顺序表，表中各节，表中各节点按顺序编号，正被考察点按顺序编号，正被考察的节点在表中编号最大的节点在表中编号最大 o宽度优先搜索的特点宽度优先搜索的特点：：n宽度优先搜索又称为宽度优先搜索又称为广度优先广度优先或或横向搜索横向搜索n宽度优先策略是宽度优先策略是完备完备的，的， 即只要问题的解存即只要问题的解存在，则在，则一定可以找到最优解一定可以找到最优解n宽度优先搜索策略与问题无关，具有宽度优先搜索策略与问题无关，具有通用性通用性n缺点搜索缺点搜索效率低效率低 深度优先搜索深度优先搜索A,47B1,77B3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51例例3.1 3.1 从王某家族的四代中找王从王某家族的四代中找王A A的后代且其寿的后代且其寿命为命为X X的人的人( (设设X=57)X=57)搜索搜索9 9步找到步找到 三、深度优先搜索三、深度优先搜索p节点扩展：最深节点节点扩展：最深节点p基本思想基本思想基本思想基本思想 一种自上向下的搜索过程，优一种自上向下的搜索过程，优先自己子节点集合中选择下一先自己子节点集合中选择下一个被考察的节点，不断向纵深个被考察的节点，不断向纵深方向前进，直到到达方向前进，直到到达叶子节点叶子节点或受到或受到深度限制深度限制时，才返回到时，才返回到上一级节点沿另一方向继续前上一级节点沿另一方向继续前进。
进 与宽度优先搜索算法与宽度优先搜索算法根本不根本不同同在于：将在于：将扩展的后继节点放扩展的后继节点放在在OPENOPEN表的前端（表的前端（LIFOLIFO））A,47B1,77B3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51 深度优先搜索示意图深度优先搜索示意图OPENOPEN表表节点节点父节点父节点CLOSECLOSE表表编号编号节点节点父节点父节点1ANULL2B1A3C2B14F1C25C1B16B3A7D1B38B2AAB1B3B2C2C1D1E1E2搜索图（搜索图（搜索树搜索树））ANULLB1AF1 1 1、、深度优先深度优先算法步骤：算法步骤：(1) (1) 初始结点初始结点S S放到未扩展节点放到未扩展节点OPENOPEN中；中； (2) (2) 若若OPENOPEN为空，则搜索失败，问题无解；为空，则搜索失败，问题无解； (3) (3) 弹出弹出OPENOPEN表中最顶端结点放到表中最顶端结点放到CLOSECLOSE表中，表中，并给出顺序编号并给出顺序编号n n；； (4) (4) 若若n n为目标结点为目标结点D D，则搜索成功，问题有解；，则搜索成功，问题有解； (5) (5) 若若n n无子结点，转无子结点，转(2)(2)；；(6) (6) 扩展扩展n n结点，将其所有子结点配上返回结点，将其所有子结点配上返回n n的指的指针，并按次序针，并按次序压入压入OPENOPEN堆栈堆栈，转，转(2) (2) 。
1 2 38 57 4 611 2 38 4 5 7 631 2 38 4 57 6 1 2 38 4 57 61 38 2 5 7 4 61 2 38 57 4 61 2 38 47 6 541 28 4 37 6 51 2 3 8 57 4 621 2 38 47 6 55深度优先搜索深度优先搜索 o深度优先搜索的特点深度优先搜索的特点nOPENOPEN表为表为堆栈，操作是后进先出（堆栈，操作是后进先出（LIFOLIFO））n深度优先又称深度优先又称纵向搜索纵向搜索n一般一般不容易保证找到最优解不容易保证找到最优解（如下图所示）（如下图所示）n防止搜索过程沿着无益的路径扩展下去，往往防止搜索过程沿着无益的路径扩展下去，往往给出一个节点扩展的最大深度给出一个节点扩展的最大深度————深度界限深度界限 2 2、、有界有界深度优先搜索深度优先搜索 引入搜索引入搜索深度限制深度限制值值d d，使深度优先搜索具有完备性，使深度优先搜索具有完备性 。
（（1 1）深度界限的选择很重要）深度界限的选择很重要 d d若太小，则达不到解的深度，得不到解；若太大，若太小，则达不到解的深度，得不到解；若太大，既浪费了计算机的存储空间与时间，降低了搜索效率由既浪费了计算机的存储空间与时间，降低了搜索效率由于解的路径长度事先难以预料，要恰当地给出于解的路径长度事先难以预料，要恰当地给出d d的值是比的值是比较困难的较困难的 （（2 2）即使能求出解，它也不一定是最优解即使能求出解，它也不一定是最优解 例例3.33.3：设定搜索深度限制：设定搜索深度限制d=5d=5的八数码问题的八数码问题 有界深度优先搜索示例有界深度优先搜索示例 有界深度优先有界深度优先算法步骤：算法步骤：(1)(1)初始结点初始结点S S放入堆栈放入堆栈OPENOPEN中；中；(2)(2)若若OPENOPEN为空，则搜索失败，问题无解；为空，则搜索失败，问题无解；(3)(3)弹出弹出OPENOPEN中栈顶结点中栈顶结点n n，放入，放入CLOSECLOSE表中，并表中，并给出顺序编号给出顺序编号n n；；(4)(4)若若n n为目标结点为目标结点D D，则搜索成功，问题有解；，则搜索成功，问题有解；(5)(5)若若n n的深度的深度d(n)=dd(n)=d，则转，则转(2) (2) ；；(6)(6)若若n n无子结点，即不可扩展，转无子结点，即不可扩展，转(2) (2) ；；(7)(7)扩展结点扩展结点n n，将其所有子结点配上返回，将其所有子结点配上返回n n的指的指针，并压入针，并压入OPENOPEN堆栈，转堆栈，转(2) (2) 。
3.2 启发式搜索启发式搜索盲目搜索的不足：盲目搜索的不足：效率低，耗费空间与时间效率低，耗费空间与时间启发式搜索：启发式搜索：利用问题本身特性信息（启发信息）利用问题本身特性信息（启发信息） 指导搜索过程是指导搜索过程是有序搜索有序搜索一、启发式搜索策略一、启发式搜索策略启发式信息启发式信息主要用途主要用途：： （（1 1）用于）用于确定要扩展的下一个节点确定要扩展的下一个节点，避免盲目扩展避免盲目扩展 （（2 2）用于）用于确定应该从搜索树中抛弃或修剪的节点确定应该从搜索树中抛弃或修剪的节点估价函数估价函数 f (n):估算节点估算节点n的希望程度的希望程度 f (n)可以是节点可以是节点n到目标节点的到目标节点的距离距离；或包括节；或包括节点点n的的路径长度路径长度 用估价函数用估价函数 f 来排列来排列OPENOPEN表上的节点表上的节点 应用某个算法选择应用某个算法选择OPENOPEN表上具有表上具有最小最小f 值的节点值的节点作为作为下一个要扩展的节点。
这种搜索方法叫做下一个要扩展的节点这种搜索方法叫做有序搜索有序搜索或或最佳最佳优先搜索优先搜索(best-first search)(best-first search)，而其算法就叫做，而其算法就叫做有序搜有序搜索算法索算法或或最佳优先算法最佳优先算法 二、有序搜索二、有序搜索 开始开始把把S放入放入OPEN表表OPEN为空表？为空表？失败失败选取选取OPEN表中表中f值最小值最小的节点的节点i，放入，放入CLOSED表表i=Sg？？成功成功是是是是扩展扩展i得后继节点得后继节点j，计算，计算f(j)，提，提供返回供返回i的指针，利用的指针，利用f(j)对对OPEN表重新排序调整父子关系及指针表重新排序调整父子关系及指针2 2、有序搜索算法框图、有序搜索算法框图 3 3、有序搜索算法讨论、有序搜索算法讨论 （（1 1））盲目搜索是有序搜索的盲目搜索是有序搜索的特例：启发信息为零特例：启发信息为零（（2 2）估价函数）估价函数 f 的选择的选择 f 的选择直接决定的选择直接决定有序搜索的有效性如果选择的有序搜索的有效性如果选择的 f 不不合适，有序搜索就可能失去一个最好的解甚至全部的解。
合适，有序搜索就可能失去一个最好的解甚至全部的解 f的选择涉及两个内容：的选择涉及两个内容：一是一个时间和空间之间的一是一个时间和空间之间的折衷方案折衷方案；；二是保证有一个最优的解或任意解二是保证有一个最优的解或任意解 例例3.4：：八数码难题估价函数八数码难题估价函数 估价函数取：估价函数取： f(n)=d(n)+W(n)其中：其中：d(n) 是搜索树中节点是搜索树中节点n的深度；的深度； W(n) 是是节点节点n的中错放的棋子个数的中错放的棋子个数 对于起始节点棋局，对于起始节点棋局，f=0+4=4 4 4、有序搜索算法举例、有序搜索算法举例2 861 2 8 31 6 4752 8 31 6 47 52 8 3147 6 52 8 31 6 47 52 8 31 47 6 5231 8 47 6 52 8 31 47 6 58 32 1 47 6 52 8 37 1 46 52 31 8 47 6 52 3 31 8 47 6 51 2 38 47 6 51 2 3847 6 51 2 37 8 46 5f=0+4=4f=1+5=6f=1+3=4f=1+5=6f=2+3=5f=2+3=5f=2+4=6f=3+3=6f=3+4=7f=3+2=5f=3+4=7f=4+1=5f=5+0=5f=5+2=7 f(n)=d(n)+W(n) 启发函数是对当前节点到达目标节点要付出的代当前节点到达目标节点要付出的代价价的估计。
在全局择优和局部择优搜索算法中，都没有考虑从初始节点到当前节点已经付出的实际代价初始节点到当前节点已经付出的实际代价 在很多实实际问题中，已经付出的实际代价是必须考虑的将两者同时考虑，用于指导搜索的算法称为A算法和算法和A*算法算法 三、三、 A* A*算法算法 1. 1. A算法算法估价函数估价函数f（（x）） : :为了防止单独利用启发函数误入歧途，将启发函数h（x）与代价函数g（x）相结合，即： f（（x）） ＝＝g（（x）＋）＋h（（x））Ø g（（x）代价函数）代价函数：：初始节点S0到达节点x处已付出的代价，有利于搜索纵向发展，提高搜索效率，但影响完备性Ø h（（x）启发函数）启发函数：节点x 到达目标节点Sg的接近程度估计值，有利于搜索横向发展，提高搜索的完备性，但影响搜索效率三、三、 A* A*算法算法 代价代价g（（x））的计算的计算 g（（x））表示从初始节点S0到节点x的代价： g（（ S0 0 ）＝）＝0 0 g（（ xj j ）＝）＝g（（ xi i ）＋）＋ c（（xi i，，xj j）） 其中，其中，c（（xi i，，xj j））表示父节点xi到子节点xj的代价ADCEB464332323462344632C1B1D1D2E1C2E2D3C3B2E4E36B33.2 启发式搜索 3.2 启发式搜索f（x） ＝g（x）＋h（x）g（x）：对某一确定的节点，是确定的值。
h（x）：不同的问题启发函数的定义不同，相同的问题也可以定义出不同的启发函数衡量h（x）优劣的标准是看其是否能够准确反映出节点x到达目标的难易程度（距离）估价函数定义探讨估价函数定义探讨 2. 2. A*算法算法 对A算法再限制其估价函数中的启发函数h(x)满足： 对所有的节点x均有： h（x） h* （x） 其中h* （x）是从节点x到目标节点的最小代价，这就称为A*算法 A*算法也称为最佳图搜索算法，利用A*算法，如果问题存在最优解，就保证能找到最优解 A*A*算法特性算法特性（（1））A*算法的可纳性：搜索算法能在有限步骤算法的可纳性：搜索算法能在有限步骤内终止，并找到最优解内终止，并找到最优解2））A*算法的最优性：在满足算法的最优性：在满足h(n)≤h*(n)的前提下的前提下, h(n)越大，携带的启发信息越多，搜索时扩展的越大，携带的启发信息越多，搜索时扩展的节点数越少，搜索效率越高节点数越少，搜索效率越高3））h(n)的单调性限制：可减少检测及调整的的单调性限制：可减少检测及调整的工作量，从而减少搜索代价工作量，从而减少搜索代价。