您所在位置：网站首页 > 办公文档 > PPT模板库 > PPT素材/模板湖南大学人工智能幻灯片3

湖南大学人工智能幻灯片3

40页

卖家[上传人]：F****n

文档编号：88162505

上传时间：2019-04-20

文档格式：PPTX

文档大小：1.96MB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

25 金贝

/ 40 举报版权申诉马上下载

文本预览

下载提示

常见问题

1、第三章 PartI 通过搜索对问题求解,内容提要,问题求解Agent 搜索求解无信息搜索策略,问题求解agent,搜索问题求解agent 形式化搜索执行,实例： Romania,已知条件：一个agent在罗马尼亚度假，目前位于Arad城市 Agent明天有航班从Bucharest起飞，不能改签退票,实例： Romania,形式化：形式化目标: 赶往Bucharest 形式化问题：状态: 当前位置行动：城市之间穿梭搜索: 城市之间穿梭路线e.g., Arad， Sibiu, Fagaras, Bucharest,实例： Romania,状态空间初始状态：In(Arad) 行动：Go(Sibiu),Go(Timisoara),Go(Zerind) 转移模型: Result(In(Arad),Go(Zerind)=In(Zerind) 目标：In(Bucharest) 路径耗散:c(s,a,s),实例：真空吸尘器世界,状态? 机器人的位置和灰尘位置初始状态？任何状态都可为初始状态行动? 向左，向右，吸灰尘转移模型？状态+行动-新状态目标测试? 检查所有位置是否干净

2、路径消耗? 1 /行动,实例：八数码问题,状态? 8个棋子以及空格在棋盘9个方格上的分布初始状态？任何状态都可为初始状态行动? 向左，向右，向上，向下转移模型？状态+行动-新状态目标测试? 检查状态是否匹配目标状态路径消耗? 1 /行动,八皇后问题,状态? 初始状态？行动? 转移模型？目标测试? 路径消耗?,如何减少它的状态空间？,树搜索算法,基本思路：从初始状态/已知状态开始，通过行动不断地探索其他状态直到找到目标状态(成功)或者没有行动可执行为止(失败) 树表示：根节点：初始状态连线：行动结点：状态空间中的状态,树搜索算法,树搜索算法实例,树搜索算法实例,Initialize the explored set to be empty,Add the node to the explored set Expand the chosen node, adding the resulting nodes to the frontier only if not in the frontier or explored set,树搜索算法实现,N.state:对应状态空间中

3、的状态 N.parent:结点N的父结点 N.action:父结点生成该结点所采取的行动 N.path-cost:从初始状态到该结点的路径消耗,树搜索算法实现,状态对应于问题的物理配置情况结点是一种数据结构包括状态，父结点，行动，代价，结点深度,搜索策略,搜索策略是指搜索树结点选择的搜索顺序 FIFO队列 LIFO队列优先级队列哈希表：快速有效检测重复状态,算法性能, Environment: Patient, hospital, staff Actuators: Screen display (questions, tests, diagnoses, treatments, referrals) Sensors: Keyboard (entry of symptoms, findings, patients answers),性能评价标准完备性：如果问题存在解，算法即可找到解最优性：找到的解是最优解时间复杂度：花费的时间空间复杂度：花费的内存时间空间复杂度的度量：时间由搜索过程中产生的结点数目来度量空间由内存中存储的最多结点数量来度量通常小于状态空间数量|V|+

4、|E|,无信息搜索策略,18,无信息搜索除了问题定义中提供的状态信息外没有任何附加信息算法只能区分状态是不是目标状态无法比较非目标状态的好坏策略：宽度优先搜索一致代价搜索深度优先搜索深度受限搜索迭代加深的深度优先搜索,宽度优先搜索,19,先扩展根结点，再扩展根结点的所有后继，然后再扩展它们的后继实现： FIFO队列,宽度优先搜索,宽度优先搜索,宽度优先搜索,22,属性：完备性？最优性？时间复杂度O(bd) 空间复杂度O(bd) 内存需求大时间复杂度高,一致代价搜索,23,扩展未扩展结点中代价最小的实现：队列按照代价从小到大排列,一致代价搜索,一致代价搜索,完备性？最优性？时间复杂度O(b1+lowbound(C/e) 空间复杂度O(b1+lowbound(C/e),深度优先搜索,首先扩展最深的为扩展结点实现：用LIFO队列(栈)来存储结点,深度优先搜索,深度优先搜索,深度优先搜索,深度受限的搜索,假定深度为l的结点没有后继结点,深度优先搜索,完备性？最优性？时间复杂度O(bm) 空间复杂度O(bm),迭代加深的深度优先算法,结合了宽度优先和深度优先的优点,迭代加深的深度优先算法,迭代加深的深度优先算法,迭代加深的深度优先算法,对于深度为d，分支数为b的情况，深度受限的搜索算法产生的结点数为： N(DLS)= b0 + b1+ bd 迭代加深的深度优先算法产生的结点数为： N(IDS)=(d+1)+(d)b+(d-1)*b2+.+(1)bd 当 b = 10, d = 5, N(DLS)= 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111 N(IDS)= 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456,迭代加深的深度优先算法,最优性? 完整性? 时间复杂度O(bd) 空间复杂度O(bd),双向搜索,同时向前搜索和向后搜索当两种搜索模式相遇时算法停止直观上2 * O(bd/2) 远小于O(bd),搜索算法对比,问题求解agent,问题求解Agent 搜索求解无信息搜索策略宽度优先搜索一致代价搜索深度优先搜索迭代加深的深度优先搜索双向搜索,Qa？,

《湖南大学人工智能幻灯片3》由会员F****n分享，可在线阅读，更多相关《湖南大学人工智能幻灯片3》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源