设为首页 - 加入收藏
广告 1000x90
您的当前位置:二四六天天好彩308K文字资料 > 博弈树搜索 > 正文

人工智能ch5

来源:未知 编辑:admin 时间:2019-07-19

  教学计划 ? ? ? ? ? ? ? 人工智能及其发展 知识表示 确定性推理 不确定推理 搜索策略 机器学习—知识获取 专家系统 第五章 搜索策略 ? ? ? ? 基本概念 状态空间搜索策略 与/或树搜索策略 搜索的完备性与效率 §1、 基本概念 ? 搜索 – 根据问题的实际情况,不断寻找可利用的知识,从 而构造一条代价较小的推理线路,使问题得到圆满 解决的过程称搜索 – 人工智能问题的特点 ? 结构不良 ? 非结构化 – 解的特点 ? 一般不存在通用、有效的解析形式——数学形式化 ? 利用已有的知识进行搜索求解 ? 分类 – 盲目搜索 ? 按预定的策略进行搜索,搜索过程中获得的中间信息不用 于改进控制策略 – 启发式搜索 ? 搜索过程中加入了与问题有关的信息(称启发信息),用 于指导搜索朝着最有希望的方向前进,加速问题求解的过 程并最终找到最优解 ? 启发信息 – 与问题相关 – 与求解过程的中间结果相关 – 比较 ? 盲目搜索与具体问题无关,易于形成统一算法 ? 启发式搜索与具体问题有关,效率高、速度快,启发信息 难于获得 ? 控制策略 – 确定选择算法的依据,见ch3。 ? 问题表示方法 – 状态空间表示法 ? 状态 – 描述问题求解过程中任一时刻状况的数据结构——状态 – 形式:Sk=(Sk0,Sk1,……,Skn,……) – 其中: Ski是第i个分量 给定每个分量一个值后,就称为一个具体的状态 – 状态可以是有限的或无限的 ? 算符 – 引起状态转变的操作 – 状态转变指状态中某些分量(一个或多个)的值发生变化 – 例:知识的应用使新的结论被推出,从而改变了问题的状态 ? 状态空间 – 问题的全部状态和一切可用算符所构成的集合称状态空间 – 形式:(S,F,G) ? S——初始状态集合 ? F——算符集合 ? G——目标状态集合 ? 状态空间表示法指将问题通过抽象表示为状态空间 ? 状态空间的图示形式称为状态空间图——有向图 – 节点(顶点)表示状态 – 有向边(弧)表示算符 ? 例: – 书p.258 – 推理中,由初始证据、中间证据、使用的知识一起构成状态 空间;综合数据库的变化反应状态转变 – 与/或树表示法 ? 问题分解 – 复杂问题分解为若干个较为简单的子问题,每个子问题继续 分解成更简单的子问题,重复此过程,直到不能再分解或不 需要再分解为止 – 分别求解各子问题 – 各子问题的解复合起来得到原问题的解 – 问题的分解形成与树,被分解的节点称与节点 ? 等价变换 – 将复杂问题用同构或同态的等价变换将它变换成若干个较易 求解的新问题 – 若新问题中有一个可求解,该解可变换为原问题的解 – 问题等价变换后形成或树,被变换的节点称或节点 ? 由问题的分解与等价变换形成问题求解过程的树形表示称 为问题求解的与/或树表示法 ? 相关概念 – 本原问题:不能再分解或变换,而且直接可解的子问题 – 端节点与终止节点 ? 与/或树中,没有子节点的节点称端节点 ? 本原问题对应的节点称终止节点 ? 终止节点一定是端节点,端节点不一定是终止节点 – 可解节点 ? 与/或树中,满足下列条件之一的节点就是可解节点 1)终止节点 2)子节点中至少有一个是可解节点的或节点 3)子节点全部是可解节点的与节点 – 不可解节点 ? 不是可解的节点称不可解节点 – 解树 ? 如果树的所有节点都是可解节点,树被称为解树 §2、状态空间搜索策略 ? 问题形式化 – 将状态空间(S,F,G)中的每一个状态看作一个顶点,F操 作将使(顶点)状态发生变化而形成新的状态(顶点),新 旧状态之间通过F连接(边)。由此,整个状态空间可以用一 个有向图G=(V,E)表示 ? V——状态(顶点)集合 ? E——操作(边)集合 – 状态空间搜索问题可以转化为在图G中搜索从初始状态顶点S0 到目标状态顶点Sg的路径问题 ? 主要数据结构 – 图搜索中用到的主要数据结构包括 ? 图G ? OPEN表 – (顶点状态,父顶点) – OPEN表用于存放待处理的顶点 ? CLOSED表 – (编号,顶点状态,父顶点) – CLOSED表用于存放将要处理的顶点或已处理的顶点 ? A算法——盲目搜索算法 – 算法 ? 输入:(G,F),初始顶点S0 ? 步骤 – – – – – 输出:Sg,解树G‘ 1)S0放入OPEN,建立仅含一个顶点S0的图G‘ 2)检查OPEN,若为空则问题无解,结束 3)取出OPEN的第一个顶点并放入CLOSED中,记为Sn 4)检查Sn,若为Sg则求得了问题的解,结束搜索,结束 5)展开Sn :对Sn应用F中的操作,生成一组新顶点{Sn1,Sn2,……, Snk}。 若nk=0转2),否则,记M为新顶点中不是Sn先辈的顶点集合,并 将它们放入G‘中,连接由Sn指向它们的弧。弧上标记使用的操作。 – 6)M的处理 ? 对M中未在G’中出现过的顶点,生成其父顶点并放入OPEN中 ? 对于哪些在G‘中出现过的顶点,确定是否修改其父顶点并实施 ? 对于哪些已在G’中出现且已扩展了的成员,确定是否修改其后 继顶点的父顶点并实施 – 7)按某种策略对OPEN中的顶点排序 – 8)转2) – 应用 ? 广度优先搜索算法 – 算法:将A算法中需放入OPEN中的顶点依次放入OPEN的尾部, 并为每一个顶点配置指向父顶点的指针 – 特点:盲目性大,可能产生许多无用的中间顶点,效率低,能 找到最优解 ? 深度优先搜索算法 – 算法:将A算法中需放入OPEN中的顶点依次放入OPEN的头部, 并为每一个顶点配置指向父顶点的指针 – 特点:不一定能找到解,且解一般不是最优解。效率较高 ? 有界深度搜索算法 – 算法:将A算法中需放入OPEN中的顶点若其深度不超过规定的 上界SUP,则放入OPEN的头部,并为每一个顶点配置指向父顶 点的指针 – 特点:不一定能找到解,且解一般不是最优解。效率较高 – 关键:SUP的选择 ? 代价树广度优先搜索算法 – 代价函数 ? g(x2)=g(x1)+c(x1,x2) ? g(x)——从S0到x的代价,c(x1,x2)——从x1到x2的代价 ? ?当x2是由x1展开生成时,x2不同什么原因造成g(x2)不 同 – 算法:对需放入OPEN中的顶点计算代价g(x),并为每一个 顶点配置指向父顶点的指针后将它们放到OPEN的尾部,重 新对OPEN进行排序 – 特点:能找到最优解 ? 代价树深度优先搜索算法 – 代价函数: ? g(x2)=g(x1)+c(x1,x2) ? g(x)——从S0到x的代价,c(x1,x2)——从x1到x2的代价 – 算法:将需放入OPEN中的顶点按g(x)的值排序后放到OPEN 的头部,并为每一个顶点配置指向父顶点的指针 – 特点:不一定能找到解,且解一般不是最优解。效率较高 ? ?g(x)是否为启发信息 ? A*算法——启发式搜索算法 – 估价函数 ? 最小代价函数 – f*(x)=g* (x)+h* (x) ? f*(x)——从S0经x到Sg的最小代价 ? g*(x)——从S0到x的最小代价 ? h*(x)——从x到Sg的最小代价 ? 估价函数 – f(x)=g(x)+h(x) 称为f*(x)的估价函数,如果满足: ? g(x)是g*(x)的估计,且g(x)0 ? h(x)是h*(x)的估计,且有:h(x)≤h*(x) ,对任意的x – 算法 ? 在A算法中用f(x)对OPEN表进行排序得到的算法称A*算法 – A*算法的性质 ? 对有解的状态空间,A*算法能在有限步内终止并找到最优 解 ? h(x)的值越大越好,其值越大表明携带的信息量越大,搜 索效率越高 ? h(x)的单调性 – h(Sg)=0 – 若xj是xi的子顶点,有:h(xi)-h(xj)≤c(xi,xj) – A*算法的特点 ? 一定能找到最优解 ? 效率高 ? 合适的f(x)构造困难 – 应用:f(x)的不同选择形成不同的算法 ? 局部择优搜索 – 算法:需放入OPEN中的顶点按f(x)从小到大排序后放入OPEN 的头部 – 特例 ? f(x)=g(x)——A*成为代价深度优先 ? f(x)=h(x)=d(x)——A*成为深度优先搜索,d(x):x的深度 ? 全局择优搜索 – 算法:将OPEN中的顶点按f(x)从小到大排序 – 特例 ? f(x)=g(x)——A*成为代价广度优先 ? f(x)=h(x)=d(x)——A*成为广度优先搜索,d(x):x的深度 ? 例:书p.275 §3、与/或树搜索策略 ? 相关概念 – 解标示 ? 可解标示过程——由可解子节点来确定父节点、祖先节点等为 可解节点的过程 ? 不可解标示过程——由不可解子节点来确定父节点、祖先节点 等为不可解节点的过程 – 与/或树的一般搜索过程 ? ? ? ? 1)把原始问题作为初始节点,并把它视为当前节点 2)应用分解或等价变换算符对当前节点进行扩展 3)为每个子节点设置指向父节点的指针 4)选择适合的子节点作为当前节点,反复执行2)和3),并 调用可解标示过程或不可解标示过程,直到初始节点被标示为 可解或不可解为止。 – 搜索树:由搜索过程形成的节点和指针结构 – 可解性与剪枝 ? 如果已确定某个节点为可解节点,则其不可解的后裔节点不在有 用,可从搜索树中删除 ? 如果已确定某个节点为不可解节点,则其全部后裔节点不在有用, 可从搜索树中删除 ? 与/或树的盲目搜索 – 广度优先搜索 ? 算法: – 1)把初始节点S0放如OPEN – 2)把OPEN表的第一个节点n取出放入CLOSED表 – 3)如果n可扩展,则做下列工作 ? 扩展节点n,将其子节点放入OPEN的尾部,并为每个节点配置 指向父节点的指针,以备标示过程使用 ? 考察这些子节点中是否有终止节点。若有,则标示这些终止节 点为可解节点,并调用可解标示过程进行标示。如果S0也被标 示为可解节点,就得到了解树,搜索过程结束。如果不能确定 S0为可解节点,则从OPEN中删去具有可解先辈的节点 ? 转2) – 4 )如果n不可扩展,则做下列工作 ? 标示n为不可解节点 ? 调用不可解标示过程进行标示。如果S0也被标示为不可解 节点,搜索过程失败,表明原问题无解,结束搜索。如果 不能确定S0为不可解节点,则从OPEN中删去具有不可解先 辈的节点 ? 转2) ? 流程:书p.281 – 深度优先搜索 ? 算法 – 修改广度优先搜索中节点放入OPEN的顺序为:将节点放入 OPEN表的头部 – 有界深度优先搜索 ? 算法 – 修改广度优先搜索中节点放入OPEN的顺序为:将节点放入 OPEN表的头部 – 增加限制:只能扩展深度不超过SUP的节点 ? 流程:书p.283 ? 与/或树的启发式搜索 – 有序搜索 ? 在搜索中,根据代价确定扩展的节点以确定搜索路线的搜索方 法称为与/或树的有序搜索方法 ? 解树的代价 – 节点代价计算 设:h(x)表示节点x的代价,c(x,y)表示x到其子节点y的代价 1)如果x是终止节点,定义:h(x)=0 2)如果x是或节点,y1,y2,……,yn是其子节点,定义 h(x)=min{c(x,yi)+h(yi)} 3)如果x是与节点,y1,y2,……,yn是其子节点,定义 和代价计算:h(x)=?(c(x,yi)+h(yi)) 最大代价计算: h(x)=max{c(x,yi)+h(yi)} 4)如果x不可扩展,且又不是终止节点,定义:h(x)=? – 解树代价计算 ? 解树的代价是初始节点S0的代价 ? 如果有多棵解树,一般它们的代价是不相同的。代价最小的解 树称为最优解树 ? 希望树 – 最优解树难于求得,目标是:较优解树 – 希望树T是满足下列条件的树 ? 初始节点S0在T中 ? 如果节点x在T中,则一定有: 1)如果x是具有子节点y1,y2,……,yn的或节点,则具有值 min{c(x,yi)+h(yi)} 的节点在T中 2)如果x是与节点,则它的全部子节点都在T中 – ?希望树是最优解树吗?为什么? ? 有序搜索过程 – – – – 1)把初始节点S0放入OPEN中 2)求出希望树T 3)依次把OPEN表中T的端节点N选出并放入CLOSED中 4)如果节点N是终止节点,则 ? 标示N为可解节点 ? 对T应用可解标示过程 ? 若S0被标示为可解节点,则T就是最优解树,退出搜索 ? 否则,从OPEN中删去具有可解先辈的所有节点 – 5)如果节点N不是终止节点且不可扩展,则 ? 标示N为不可解节点 ? 对T应用不可解标示过程 ? 若S0被标示为不可解节点,则搜索失败,退出搜索 ? 否则,从OPEN中删去具有不可解先辈的所有节点 – 6)如果节点N不是终止节点但可扩展,则 ? 扩展N,产生其所有子节点 ? 把这些子节点放入OPEN中,并为每个子节点配置指向 父节点的指针 ? 计算这些子节点及其先辈节点的h估值 – 7)转2) ? 流程:书p.286 ? 例:书p.286 – 博弈树搜索 ? 书p.288 – ?-?剪枝技术 ? 书p.290 搜索的完备性与效率 ? 完备性 – 对于一类可解的问题和一个搜索过程,如果 运用该搜索过程一定能求得该类问题的解, 称该搜索过程是完备的,否则为不完备的。 – 完备的搜索过程称搜索算法或算法 – 不完备的搜索过程称过程 ? 广度优先搜索、代价树的广度优先搜索、 改进后的有界深度优先搜索、A*——都 是完备的,其它搜索过程不是完备的。 ? 搜索效率 – 外显率 P ? L T – L为从初始节点到目标节点的路径长度,T为整 个搜索过程中所生成的节点总数 ? 有效分枝因素——B – B+B2+B3+……+BL=T ? 显然: L ? ( B ? 1) P? B ? ( B L ? 1) B ? ( B L ? 1) T? B ?1 粒子群优化算法(PSO) ? PSO(Particle Swarm Optimization)是一种进 化计算技术(evolutionary computation),源 于对鸟群捕食的行为研究。 ? 在这个区域里只有一块食物。所有的鸟都 不知道食物在那里。但是他们知道当前的 位置离食物还有多远。那么找到食物的最 优策略是什么呢? ? 最简单有效的就是搜寻目前离食物最近的 鸟的周围区域。 ? v[] = v[]+c1× rand()×(pbest[]- present[]) + c2×rand()×(gbest[] - present[]) ? present[] = persent[] + v[] – – – – – – v[] 是粒子的速度, persent[] 是当前粒子的位置, pbest[] 是粒子本身所找到的最优解, gbest[]整个种群目前找到的最优解, rand () 是介于(0, 1)之间的随机数。 c1, c2 是学习因子。 通常 c1 = c2 = 2。 蚁群优化(ACO) ? ACO——Ant Colony Optimization 求解最优化问题 B D A 蚁 穴 求最短路径 C 食 物 聚类 DNA计算 ? 1994年11月Adleman的在Science上发表的 论文,第一次实现了人类用生物材料作 计算物质而解决了人类的数学问题:七 节点Hamilton路径问题。 ? Adleman的求解基于下面的求解HPP的非确 定算法 – 输入: n顶点有向图G, 输入顶点为vin, 输出顶点 为vout. – 步骤1: 生成图中的充分大量的随机路径. – 步骤2: 仅保留那些从vin开始,从vout结束的路径. – 步骤3: 仅保留那些恰好经过n个顶点的路径. – 步骤4: 仅保留那些经过图中n个顶点至少一次 的路径. – 输出: 如果还有路径留下, 回答”是”, 否则, 回 答”否”. ? 这个算法进行的是耗尽式搜索 ? 每个顶点I用20个碱基的随机DNA串si编 码, 0≤i≤6. 如, 对i=2,3,4: s2=TATCGGATCGGTATATCCGA, s3=GCTATTCGAGCTTAAAGCTA, s4=GGCTAGGTACCAGCATGCTT. ? 因方向性,这些低核苷酸都从5’写到3’ ? 图G中存在一条从顶点i到顶点j的边, 这可 通过对编码边的两个顶点的低核苷酸的 后半部分和前半部分求Watson-Crick补. 三条特定的边表示如下: e2→3 = CATATAGGCTCGATAAGCTC, e3→2 = GAATTTCGATATAGCCTAGC, e3→4 = GAATTTCGATCCGATCCATG. ? 重要的一点是该构造保持边的方向性, e2→3和e3→2完全不同. ? 互补黏结生成连接的路径 – 顶点s3到s2: s2=TATCGGATCGGTATATCCGA s3=GCTATTCGAGCTTAAAGCTA e3→e2 = GAATTTCGATATAGCCTAGC – 顶点s3到s4: s3=GCTATTCGAGCTTAAAGCTA s4=GGCTAGGTACCAGCATGCTT e3→e4 = GAATTTCGATCCGATCCATG 精品课件! 精品课件! ? 步骤二: 要将第一步的结果中那些从vin 出发而到 vout 结束的DNA分子串用磁珠提出并通过PCR技术 放大,从而把那些从vin 出发而到vout 结束的DNA分 子串大量增加。 度一样)的DNA串取出。 ? 步骤三: 只要用凝胶电泳把只有n个顶点(当然长 ? 步骤四: 使用“亲合纯化”方法完成。既把含有给 定序列v(表示图中一个顶点)的单链从反映器中滤 出来,这只要将h(v)附着在磁珠上,于是把含v的 DNA串因互补结合而固定在磁珠上,然后把磁珠滤 出反映器。对n个顶点依次过滤,最终完成第四步。 如果还有DNA序列则得到一条Hamilton路径,否则 就不存在。

本文链接:http://mzi-ads.com/boyishusousuo/697.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top