您好、欢迎来到现金彩票网!
当前位置:秒速时时彩计划 > 随机归约 >

第五章讲 启发式搜索课件ppt

发布时间:2019-06-07 06:33 来源:未知 编辑:admin

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  5.3.2 宽度优先搜索策略 宽度优先搜索:以接近起始结点的程度为依据进行逐层扩展的搜索方法。(用队列的存储结构,类似于树的按层次遍历的过程。 特点:逐层搜索;高价搜索:若解存在,必能找到。 例2 通过搬动积木块,希望从初始状态达到一个目的状态,即三块积木堆叠在一起。 B C A A B C (a) 初始状态 (b) 目的状态 积木问题 5.3.2 宽度优先搜索策略 操作算子为MOVE(X,Y):把积木X搬到Y(积木或桌面)上面。 MOVE(A,Table):“搬动积木A到桌面上”。 操作算子可运用的先决条件: (1)被搬动积木的顶部必须为空。 (2)如果 Y 是积木,则积木 Y 的顶部也必须为空。 (3)同一状态下,运用操作算子的次数不得多于一次。 5.3.2 宽度优先搜索策略 A B A B A C C B A C C C B A B C A B A C B A A B C B C B C C A B A MOVE(A,TABLE) MOVE(C,A) MOVE(A,C) MOVE(B,A) MOVE(B,C) MOVE(C,A) MOVE(C,B) MOVE(C,B) MOVE(A,B) 0 S 1 S 2 S 3 S 4 S 5 S 6 S 7 S 8 S 9 S 10 S 没有后裔, 失败退出 积木问题的宽度优先搜索树 5.3.2 宽度优先搜索策略 5.3.2 宽度优先搜索策略 open表(NPS表):已经生成出来但其子状态未被搜索的状态。 closed表( PS表和NSS表的合并):记录了已被生成扩展过的状态。 重复 OPEN表 CLOSE表 0 S0 [ ] 1 2 3 4 。。 。。。 重复 OPEN表 CLOSE表 0 S0 [ ] 1 [S1,S2,S3] [S0] 2 3 4 。。 。。。 重复 OPEN表 CLOSE表 0 S0 [ ] 1 [S1,S2,S3] [S0] 2 [S2,S3,S4,S5,S6,S7] [S1,S0] 3 4 。。 。。。 重复 OPEN表 CLOSE表 0 S0 [ ] 1 [S1,S2,S3] [S0] 2 [S2,S3,S4,S5,S6,S7] [S1,S0] 3 [S3,S4,S5,S6,S7] [S2,S1,S0] 4 。。 。。。 重复 OPEN表 CLOSE表 0 S0 [ ] 1 [S1,S2,S3] [S0] 2 [S2,S3,S4,S5,S6,S7] [S1,S0] 3 [S3,S4,S5,S6,S7] [S2,S1,S0] 4 [S4,S5,S6,S7,S8] [S3,S2,S1,S0] 。。 。。。 5.3.3 深度优先搜索策略 0 S 1 2 3 4 5 6 7 8 9 10 11 12 13 K K 深度优先搜索法中状态的搜索次序 0 S 1 2 3 4 5 6 7 8 9 10 11 12 13 K K 深度优先搜索:首先扩展最新产生的节点,深度相等的节点可以任意排列的搜索方法。(用堆栈的数据结构) 特点:搜索沿着状态空间的某单一路径沿着起始点向下进行下去,仅当搜索到达一个没有后裔的状态时,才选择另一条替代路径。 5.3.3 深度优先搜索策略 深度优先搜索并不能保证第一次搜索到的某个状态时的路径是到这个状态的最短路径,为防止搜索过程沿着无益的路径扩展下去,给出一个节点扩展的最大深度—深度界限。 为了保证找到解,应选择合适的深度限制值,或采取不断加大深度限制值的办法,反复搜索,直到找到解。 与宽度优先搜索根本的不同点:将扩展的后继节点放在OPEN表的最前端。 例3 卒子穿阵问题,要求一卒子从顶部通过下图所示的阵列到达底部。卒子行进中不可进入到代表敌兵驻守的区域(标注1),并不准后退。假定深度限制值为5。 阵列图 5.3.3 深度优先搜索策略 0 S 1 S ) 1 , 1 ( 2 S ) 2 , 1 ( 3 S ) 2 , 2 ( 4 S ) 1 , 2 ( 5 S ) 1 , 3 ( 6 S ) 2 , 3 ( 7 S ) 3 , 2 ( 8 S ) 3 , 1 ( 9 S ) 2 , 1 ( 14 S ) 4 , 1 ( 10 S ) 2 , 2 ( 11 S ) 1 , 2 ( 12 S ) 1 , 3 ( 13 S ) 3 , 2 ( 15 S ) 4 , 2 ( 16 S ) 4 , 3 ( 17 S ) 4 , 4 ( 18 S ) 4 , 1 ( 死 死 解 0 S 1 S ) 1 , 1 ( 2 S ) 2 , 1 ( 3 S ) 2 , 2 ( 4 S ) 1 , 2 ( 5 S ) 1 , 3 ( 6 S ) 2 , 3 ( 7 S ) 3 , 2 ( 8 S ) 3 , 1 ( 9 S ) 2 , 1 ( 14 S ) 4 , 1 ( 10 S ) 2 , 2 ( 11 S ) 1 , 2 ( 12 S ) 1 , 3 ( 13 S ) 3 , 2 ( 15 S ) 4 , 2 ( 16 S ) 4 , 3 ( 17 S ) 4 , 4 ( 18 S ) 4 , 1 ( 死 死 深度限制 解 open表:S17、S18 closed表:S0~S16 卒子穿阵的深度优先搜索树 5.3.3 深度优先搜索策略 死 死 S20 (2,4) S19 (2,4) S21 (4,4) 最优解 5.3.2 宽度优先搜索策略 重复 OPEN表 CLOSE表 0 S0 [ ] 1 [S1,S2,S8,S18] [S0] 2 [S2,S8,S18] [S1,S0] 3 [S3,S8,S18] [S2,S1,S0] 4 [S4,S7,S8,S18] [S3,S2,S1,S0] 5 [S5,S7,S8,S18] [S4,S3,S2,S1,S0] 6 [S6,S7,S8,S18] [S5,S4,S3,S2,S1,S0] 7 [S8,S18] [S7,S6,S5,S4,S3,S2,S1,S0] 。。。 。。。 。。。 5.3.3 深度优先搜索策略 一般情况下,深度优先搜索法占内存少但速度较慢,广度优先搜索算法占内存多但速度较快,在距离和深度成正比的情况下能较快地求出最优解。 因此在选择用哪种算法时,要综合考虑。决定取舍。 深度搜索和宽度搜索 深度搜索与宽度搜索的控制结构和产生系统很相似,唯一的区别在于对扩展节点选取上。 由于其保留了所有的前继节点,所以在产生后继节点时可以去掉一部分重复的节点,从而提高了搜索效率。 这两种算法每次都扩展一个节点的所有子节点,而不同的是,深度搜索下一次扩展的是本次扩展出来的子节点中的一个,而广度搜索扩展的则是本次扩展的节点的兄弟节点。 在具体实现上为了提高效率,所以采用了不同的数据结构。 第5章 搜索求解策略 5.1 搜索的概念 5.2 状态空间知识表示方法 5.3 盲目的图搜索策略 5.4 启发式图搜索策略 5.5 与/或图搜索策略 盲目图搜索策略特点: 1)不需要重排OPEN表; 2)没有启发信息的一种搜索形式; 3)一般只适用于求解简单的问题。 5.4 启发式图搜索策略 5.4 启发式图搜索策略 5.4.1 启发式策略 5.4.2 启发信息和估价函数 5.4.3 A搜索算法 5.4.4 A*搜索算法及其特性分析 为什么需要启发式搜索? 盲目搜索的不足: 效率低,耗费过多的计算时间和空间; 可能产生组合爆炸; 什么可以做启发信息? 用来简化搜索过程有关具体问题领域的特性信息叫做启发信息; 利用启发式信息进行搜索的方法就是启发式搜索方法 特点:重排OPEN表,选择最有希望的节点加以扩展; 种类:A算法,A*算法等 5.4 启发式图搜索策略 5.4.1 启发式策略 运用启发式策略的两种基本情况: (1)一个问题由于在问题陈述和数据获取方面固有 的模糊性,可能会使它没有一个确定的解。 (2)虽然一个问题可能有确定解,但是其状态空间 特别大,搜索中生成扩展的状态数会随着搜索 的深度呈指数级增长。 5.4.1 启发式策略 “启发”(heuristic):关于发现和发明操作算子及搜索方法的研究。 在状态空间搜索中,启发式被定义成一系列操作算子,并能从状态空间中选择最有希望到达问题解的路径。 启发式策略:利用与问题有关的启发信息进行搜索。 例4 一字棋。在九宫棋盘上,从空棋盘开始,双方轮流在棋盘上摆各自的棋子 ? 或 ? (每次一枚),谁先取得三子一线(一行、一列或一条对角线 启发式策略 ? 和 ? 能够在棋盘中摆成的各种不同的棋局就是问题空间中的不同状态。 9个位置上摆放{空, ? , ?}有 39 种棋局。 可能的走法 : 9!。 ? ? ? ? ? 启发式策略的运用 ? ? ? 5.4.1 启发式策略 启发式搜索下缩减的状态空间 5.4.1 启发式策略 5.4.2 启发信息和估价函数 求解问题中能利用的大多是非完备的启发信息: (1)求解问题系统不可能知道与实际问题有关的全部信息,因而无法知道该问题的全部状态空间,也不可能用一套算法来求解所有的问题。 (2)有些问题在理论上虽然存在着求解算法,但是在工程实践中,这些算法不是效率太低,就是根本无法实现。 一字棋:9!,西洋跳棋:1078,国际象棋:10120,围棋:10761。 假设每步可以搜索一个棋局,用极限并行速度(10-104年/步)来处理,搜索一遍国际象棋的全部棋局也得1016年即1亿亿年才可以算完! 5.4.2 启发信息和估价函数 启发信息按运用的方法分类: (1)陈述性启发信息:更准确地描述状态 (2)过程性启发信息:一系列操作算子 (3)控制性启发信息:控制策略 5.4.2 启发信息和估价函数 估价函数:任务是估计待搜索结点的“有希望”程度,并依次给它们排定次序(在open表中)。 估价函数f (n) :从初始结点经过n结点到达目的 结点的路径的最小代价估计值,其一般形式是 f (n)= g(n) + h (n) g(n):从初始节点到节点n的实际代价 h(n): 从节点n到目标节点的最优路径的估计代价 一般地,在f(n)中, g(n)的比重越大,越倾向于宽度优先搜索方式,而 h (n)的比重越大,表示启发性能越强。 设初始节点S0和目标节点Sg分别如下图的初始棋局和目标棋局所示。 2 8 3 1 6 4 7 5 1 2 3 8 4 7 6 5 初始状态 目标状态 例5 八数码的估价函数 设计方法有多种,并且不同的估价函数对求解八数码问题有不同的影响。 最简单的估价函数:取一格局与目的格局相比,其位置不符的数码数目:f(S0)=5 较好的估价函数:各数码移到目的位置所需移动的距离的总和:f(S0)=6 第三种估价函数:对每一对逆转数码乘以一个倍数。f(S0)=0 第四种估价函数:克服了仅计算数码逆转数目策略的局限,将位置不符数码数目的总和与3倍数码逆转数目相加。f(S0)=0. 5.4.2 启发信息和估价函数 5.4.2 启发信息和估价函数 估价函数:设计一个好的估价函数有相当的难度,是一个经验问题,判断和直觉是很重要的因素。 设计估价函数的目标是利用有限的信息做出精确的估价 衡量估计函数的好坏最终标准取决于具体应用时的搜索效果。 5.4.3 A搜索算法 启发式图搜索法——A算法和A*算法 爬山法:(Pearl,1984)在搜索过程中先扩展当前的状态,然后再评估他的孩子,而后选择最佳的孩子做进一步扩展,不保留他的兄弟姐妹和双亲,当搜索遇到比其孩子更佳的状态则停止。 最佳优先搜索:对OPEN表的状态进行排序,排序的依据是按状态与目标“接近程度”的某种启发式估计,每一轮循环考虑OPEN表中最有希望的状态。 A算法:使用估价函数的最佳优先搜索。 5.4.3 A搜索算法 A算法的基本特点: 如何寻找并设计一个与问题有关的 h(n) 及构出 f(n)= h(n)+ g(n) , 然后以f(n) 的大小来排列待扩展状态的次序,每次选择f(n) 值最小者进行扩展。 open表:保留所有已生成而未扩展的状态。 closed表:记录已扩展过的状态。 进入open表的状态是根据其估值的大小插入到表中合适的位置,每次从表中优先取出启发估价函数值最小的状态加以扩展。 A算法流程图 开始 把S0放入OPEN表中,计算f(S0) OPEN=NIL? 选取OPEN表中f最小的节点i 放入CLOSED表中 i=G ? 扩展i得后继节点j,计算f(j),提供返回i的指针,把 节点j送回OPEN表,利用f(j)对OPEN表进行重 排,调整亲子关系和指针。 失败 成功 5.4.3 A搜索算法 Y N Y N 延边大学计算机科学与技术学科 延边大学计算机科学与技术学科 延边大学计算机科学与技术学科 延边大学计算机科学与技术学科 第5章 搜索求解策略 5.1 搜索的概念 5.2 状态空间的搜索策略 5.3 盲目的图搜索策略 5.4 启发式图搜索策略 5.5 与/或图搜索策略 ? 例1 三数码问题(3 puzzle problem)。 1 2 3 3 1 2 初始棋局 目标棋局 第5章 搜索求解策略 问题求解: 问题的表示。 选择一种相对合适的求解方法。 问题求解的基本方法:搜索法、归约法、归结法、推理法及产生式等。 状态空间表示法 搜索策略: (1)盲目搜索:宽度优先搜索、深度优先搜索 (2)启发式搜索:A算法和A*搜索; 第5章 搜索求解策略 搜索中需要解决的基本问题: (1)是否一定能找到一个解。 (2)是否终止运行或是否会陷入一个死循环。 (3)找到的解是否是最佳解。 (4)时间与空间复杂性如何。 5.1.1 搜索的基本问题与主要过程 5.1.1 搜索的基本问题与主要过程 搜索的主要过程: (1) 从初始或目的状态出发,并将它作为当前状态。 (2) 扫描操作算子集,将适用当前状态的一些操作算子作用于当前状态而得到新的状态,并建立指向其父结点的指针 。 (3) 检查所生成的新状态是否满足结束状态,如果满足,则得到问题的一个解,并可沿着有关指针从结束状态反向到达开始状态,给出一解答路径;否则,将新状态作为当前状态,返回第(2)步再进行搜索。 5.1.2 搜索策略 1. 搜索方向: (1) 数据驱动:从初始状态出发的正向搜索。 正向搜索——从问题给出的条件(一个用于状态转换的操作算子集合)出发。 逆向搜索:先从想达到的目的入手,看哪些操作算子能产生该目的以及应用这些操作算子产生目的时需要哪些条件。 (2) 目的驱动:从目的状态出发的逆向搜索。 5.1.2 搜索策略 (3) 双向搜索 双向搜索:从开始状态出发作正向搜索,同时又从目的状态出发作逆向搜索,直到两条路径在中间的某处汇合为止。 5.1.2 搜索策略 2. 盲目搜索与启发式搜索: (1)盲目搜索:在不具有对特定问题的任何有关信息的条件下,按固定的步骤(依次或随机调用操作算子)进行的搜索。 (2)启发式搜索:考虑特定问题领域可应用的知识,动态地确定调用操作算子的步骤,优先选择较适合的操作算子,尽量减少不必要的搜索,以求尽快地到达结束状态。 5.1.2 搜索策略 3.人工智能的主要搜索策略: 求最佳解的搜索策略: 大英博物馆法(British museum); 宽度优先法(Breadth-first search); 分支界定法(Branch and Bound); 最佳图搜索法(A*); 动态规划法(Dynamic Programing); 5.1.2 搜索策略 3.人工智能的主要搜索策略: 求与或关系解图的搜索法: 一般的与或图关系解的搜索法;(AO*) 极大极小法(Minimax); ?-?剪枝法( ?-? Pruning); 启发式剪枝法(Heuristic Pruning) 第5章 搜索求解策略 5.1 搜索的概念 5.2 状态空间知识表示方法 5.3 盲目的图搜索策略 5.4 启发式图搜索策略 5.5 与/或图搜索策略 5.2 状态空间知识表示方法 5.2.1 状态空间表示法 5.2.2 状态空间的图描述 5.2.1 状态空间表示法 状态空间表示法:知识表示的一种方法 状态:表示系统状态、事实等叙述型知识的一组变量或数组: qi:状态变量 操作:表示引起状态变化的过程型知识的一组关系或函数: 操作符(算子,操作算子):走步,过程,规则,数学算子,运算符或逻辑符 5.2.1 状态空间表示法 状态空间:利用状态变量和操作符号,表示系统或问题的有关知识的符号体系,状态空间是一个四元组: :状态集合。 :操作算子的集合。 :包含问题的初始状态是S 的非空子集。 :若干具体状态或满足某些性质的路径信息描述。 5.2.1 状态空间表示法 求解路径:从S0结点到G结点的路径。 :状态空间的一个解。 状态空间的一个解:一个有限的操作算子序列。 例如下棋、迷宫及各种游戏。 例1 三数码问题(3 puzzle problem)。 5.2.1 状态空间表示法 状态集 :所有摆法 操作算子: 将空格向上移Up 将空格向左移Left 将空格向下移Down 将空格向右移Right 1 2 3 3 1 2 初始棋局 目标棋局 解法1: 1 2 3 1 2 3 1 2 3 3 1 2 3 1 2 3 1 2 初始棋局 目标棋局 down right up left down 5.2.1 状态空间表示法 5.2.2 状态空间的图描述 (状态) (操作算子) 状态空间的有向图描述 第5章 搜索求解策略 5.1 搜索的概念 5.2 状态空间知识表示方法 5.3 盲目的图搜索策略 5.4 启发式图搜索策略 5.5 与/或图搜索策略 5.3 盲目的图搜索策略 5.3.1 回溯策略 5.3.2 宽度优先搜索策略 5.3.3 深度优先搜索策略 5.3.1 回溯策略 带回溯策略的搜索:(走不通就回头) 从初始状态出发,不停地、试探性地寻找路径,直到它到达目的或“不可解结点”,即“死胡同”为止。 若它遇到不可解结点就回溯到路径中最近的父结点上,查看该结点是否还有其他的子结点未被扩展。 若有,则沿这些子结点继续搜索;如果找到目标,就成功退出搜索,返回解题路径。 5.3.1 回溯策略 回溯搜索示意图 5.3.1 回溯策略 回溯搜索算法的几张表: (1) PS(path states)表:保存当前搜索路径上的状态。如果找到了目的,PS就是解路径上的状态有序集。 (2) NPS(new path states)表:新的路径状态表。它包含了等待搜索的状态,其后裔状态还未被搜索到,即未被生成扩展 。 (3) NSS(no solvable states)表:不可解状态集,列出了找不到解题路径的状态。如果在搜索中扩展出的状态是它的元素,则可立即将之排除,不必沿该状态继续搜索。 回溯搜索示意图的回溯轨迹: 初值:PS=[A]; NPS=[A]; NSS=[ ]; CS=A。 5.3.1 回溯策略 5.3.1 回溯策略 图搜索算法(深度优先、宽度优先、最好优先搜索等)的回溯思想: (1)用未处理状态表(NPS)使算法能返回(回溯)到其 中任一状态。 (2)用一张“死胡同”状态表(NSS)来避免算法重新搜索 无解的路径。 (3)在PS 表中记录当前搜索路径的状态,当满足目的时可 以将它作为结果返回。 (4)为避免陷入死循环必须对新生成的子状态进行检查, 看它是否在该三张表中 。 延边大学计算机科学与技术学科 延边大学计算机科学与技术学科 延边大学计算机科学与技术学科 延边大学计算机科学与技术学科 *

http://parroche-dorioz.com/suijiguiyue/130.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有