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

《人工智能基础03--搜索技术剖析》由会员分享，可在线阅读，更多相关《人工智能基础03--搜索技术剖析（105页珍藏版）》请在金锄头文库上搜索。

1、合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 1/103 目录 o 第一章 绪论 o 第二章 知识表示 o 第三章 搜索技术 o 第四章 推理技术 o 第五章 机器学习 o 第六章 专家系统 o 第七章 自动规划系统 o 第八章 自然语言理解 o 第九章 智能控制 o 第十章 人工智能程序设计 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 2/103 o 盲目搜索 o 启发式搜索 o 博弈树搜索 o 遗传算法 o 模拟退火算法 o 免疫算法 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 3/103 3.1

2、 盲目搜索 盲目搜索：即 无信息搜索 宽度优先与深度优先 3.1.1 图搜索策略 图搜索策略可看作一种在图中寻找路径的方法。初始节点 和目标节点分别代表初始数据库和满足终止条件的数据库。求 得把一个数据库变换为另一数据库的规则序列问题就等价于求 得图中的一条路径问题。研究图搜索的一般策略，能够给出图 搜索过程的一般步骤。 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 4/103 3.1 盲目搜索 3.1.1 图搜索策略 例3.1 从王某家族的四代中找王A的后代且其寿命为X的人 A,47 B1,77B3,52 B2,65 C2,87C1,96D1,77E1,57E2

3、,92 F1,32G1,27H1,51 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 5/103 3.1 盲目搜索 3.1.1 图搜索策略 1.图搜索(GRAPHSEARCH)的一般过程 (1) 建立一个只含有起始节点S的搜索图G，把S放到一个叫做 OPEN的未扩展节点表中。 (2) 建立一个叫做CLOSED的已扩展节点表，其初始为空表。 (3) LOOP：若OPEN表是空表，则失败退出。 (4) 选择OPEN表上的第一个节点，把它从OPEN表移出并放进 CLOSED表中。称此节点为节点n。 (5) 若n为一目标节点，则有解并成功退出，此解是追踪图G中 沿着指针从

4、n到S这条路径而得到的(指针将在第7步中设置)。 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 6/103 3.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

5、成员，确定是否需要更改图G中通向它 的每个后裔节点的指针方向。 (8) 按某一任意方式或按某个探试值，重排OPEN表。 (9) GO LOOP。 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 7/103 3.1 盲目搜索 节点父辈节点 3.1.1 图搜索策略 2.图搜索算法的几个重要名词 （1）OPEN表与CLOSE表 OPEN表 CLOSED表 编号节点父辈节点 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 8/103 3.1 盲目搜索 3.1.1 图搜索策略 3. 搜索图与搜索树 搜索过程框图 开 始 初始化：S放入OPEN表，C

6、LOES表置空, n=1 OPEN表中的第一个结点n移至CLOSE表 若n的后继未曾在搜索图G中出现，则将其放入OPEN 表的末端，并提供返回结点n的指针, 置n=n+1 根据后继结点在搜索图G中的出现情况 修改指针方向 依某种准则重新排序OPEN表 失败 成功 N Y N OPEN为空表NULL ？ n=目标结点D吗 ? Y 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 9/103 3.1 盲目搜索 3.1.1 图搜索策略 4.图搜索方法分析： 图搜索过程的第8步对OPEN表上的节点进行排序，以便 能够从中选出一个“最好”的节点作为第4步扩展用。这种排序 可以是

7、任意的即盲目的(属于盲目搜索)，也可以用以后要讨论 的各种启发思想或其它准则为依据(属于启发式搜索)。每当被 选作扩展的节点为目标节点时，这一过程就宣告成功结束。这 时，能够重现从起始节点到目标节点的这条成功路径，其办法 是从目标节点按指针向S返回追溯。当搜索树不再剩有未被扩 展的端节点时，过程就以失败告终(某些节点最终可能没有后 继节点，所以OPEN表可能最后变成空表)。在失败终止的情况 下，从起始节点出发，一定达不到目标节点。 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 10/103 3.1 盲目搜索 3.1.2 宽度优先搜索 定义3.1 如果搜索是以接近起

8、始节点的程度依次扩展节点的， 那么这种搜索就叫做宽度优先搜索（breadth-first search) 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 11/103 3.1 盲目搜索 3.1.2 宽度优先搜索 宽度优先搜索算法 (1) 把起始节点放到OPEN表中(如果该起始节点为一目标节点 ，则求得一个解答)。 (2) 如果OPEN是个空表，则没有解，失败退出；否则继续。 (3) 把第一个节点(节点n)从OPEN表移出，并把它放入 CLOSED的扩展节点表中。 (4) 扩展节点n。如果没有后继节点，则转向上述第(2)步。 (5) 把n的所有后继节点放到OPEN表的

9、末端，并提供从这些后 继节点回到n的指针。 (6) 如果n的任一个后继节点是个目标节点，则找到一个解答， 成功退出；否则转向第(2)步。 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 12/103 3.1 盲目搜索 3.1.2 宽度优先搜索 例3.2 八数码问题 操作规定: 允许空格四周上、下、左、右的数码块移入空格 中，不许斜方向移动，不许返回先辈结点。 初始布局S和目标状态D如下图所示： 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 13/103 3.1 盲目搜索 2 8 3 14 7 6 5 2 8 3 1 4 7 6 5 23

10、 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 75 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 1 2345 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 14/103 3.1 盲目搜索 3.1.2 宽度优先搜索 例3.2 八数码问题 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 15/10

11、3 3.1 盲目搜索 3.1.3 深度优先搜索 深度优先算法步骤： (1) 初始结点S放到未扩展节点OPEN中； (2) 若OPEN为空，则搜索失败，问题无解； (3) 弹出OPEN表中最顶端结点放到CLOSE表中，并给出 顺序编号n； (4) 若n为目标结点D，则搜索成功，问题有解； (5) 若n无子结点，转(2)； (6) 扩展n结点，将其所有子结点配上返回n的指针，并按 次序压入OPEN堆栈，转(2) 。 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 16/103 3.1 盲目搜索 2 8 3 1 6 4 75 2 8 3 1 6 4 7 5 2 8 3 1

12、4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 6 7 5 4 2 8 3 16 7 5 4 2 8 1 6 3 7 5 4 28 1 6 3 7 5 4 1 2 3 4 5 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 17/103 3.1 盲目搜索 3.1.3 深度优先搜索 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 18/103 3.1 盲目搜索 3.1.3 深度优先搜索 有界深度优先搜索： 引入搜索深度限制值d，使深度优先搜索过程具有完备性 。 设定搜索深度限制d=5，问题同深度优先算法中的八数码问题 (2)

13、。 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 19/103 3.1 盲目搜索 3.1.3 深度优先搜索 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 20/103 3.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)

14、扩展结点n，将其所有子结点配上返回n的指针，并压入 OPEN堆栈，转(2) 。 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 21/103 3.1 盲目搜索 3.1.4 等代价搜索 宽度优先搜索可被推广用来解决寻找从起始状态至目标状态 的具有最小代价的路径问题，这种推广了的宽度优先搜索算法 叫做等代价搜索算法。 等代价搜索中的几个记号 起始节点记为S； 从节点i到它的后继节点j的连接弧线代价记为c(i，j)； 起始节点S到任一节点i的路径代价记为g(i)。 如果所有的连接弧线具有相等的代价，那么等代价算法就 简化为宽度优先搜索算法。 合肥工业大学合肥工业大学 人工

15、智能与数据挖掘研究室人工智能与数据挖掘研究室 22/103 3.2 启发式搜索 盲目搜索的不足：效率低，耗费空间与时间。 启发式搜索：利用问题域特性的信息（启发信息）进行搜索。 3.2.1 启发式搜索策略 启发式信息按用途分为三种： （1）用于确定要扩展的下一个节点，避免盲目扩展。 （2）在扩展一个节点的过程中，用于确定要生成哪一个或哪 几个后继节点，避免盲目生成所有可能节点。 （3）用于确定某些应该从搜索树中抛弃或修剪得节点。 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 23/103 3.2 启发式搜索 有序搜索（ordered search）：利用第一种启发

16、信息，总是 选择“最有希望”的节点作为下一个被扩展的节点。 估价函数（evaluation function )：估算节点“希望”的量度 ，这种量度叫做估价函数。 建立估价函数的一般方法：试图确定一个处在最佳路径上 的节点的概率；提出任意节点与目标集之间的距离量度或差别 量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决 定棋局的得分数。这些特点被认为与向目标节点前进一步的希 望程度有关。 f(n)表示节点n的估价函数值 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 24/103 3.2 启发式搜索 3.2.2 有序搜索 用估价函数f来排列GRAPHSEARCH第8步中OPEN表上 的节点。应用某个算法(例如等代价算法)选择OPEN表上具有 最小f值的节点作为下一个要扩展的节点。这种搜索方法叫做 有序搜索或最佳优先搜索(best-first search)，而其算法就叫做 有序搜索算法或最佳优先算法。 合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室 25/103 3.2 启发式搜索 3.2.2 有序搜索 有序