人工智能 第三章课件.ppt

《人工智能 第三章课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章PartI通过搜索对问题求解内容提要问题求解Agent搜索求解无信息搜索策略问题求解agent搜索问题求解agent形式化搜索执行实例：Romania已知条件：一个agent在罗马尼亚度假，目前位于Arad城市Agent明天有航班从Bucharest起飞，不能改签退票实例：Romania形式化：形式化目标:赶往Bucharest形式化问题：状态:当前位置行动：城市之间穿梭搜索:城市之间穿梭路线e.g.,Arad，Sibiu,Fagaras,Bucharest实例：Romania状态空间初始状态：I

2、n(Arad)行动：{Go(Sibiu),Go(Timisoara),Go(Zerind)}转移模型:Result(In(Arad),Go(Zerind))=In(Zerind)目标：{In(Bucharest)}路径耗散:c(s,a,s’)实例：真空吸尘器世界状态?机器人的位置和灰尘位置初始状态？任何状态都可为初始状态行动?向左，向右，吸灰尘转移模型？状态+行动->新状态目标测试?检查所有位置是否干净路径消耗?1/行动实例：八数码问题状态?8个棋子以及空格在棋盘9个方格上的分布初始状态？任何状态都可为

3、初始状态行动?向左，向右，向上，向下转移模型？状态+行动->新状态目标测试?检查状态是否匹配目标状态路径消耗?1/行动八皇后问题状态?初始状态？行动?转移模型？目标测试?路径消耗?如何减少它的状态空间？树搜索算法基本思路：从初始状态/已知状态开始，通过行动不断地探索其他状态直到找到目标状态(成功)或者没有行动可执行为止(失败)树表示：根节点：初始状态连线：行动结点：状态空间中的状态树搜索算法树搜索算法实例树搜索算法实例InitializetheexploredsettobeemptyAddthenode

4、totheexploredsetExpandthechosennode,addingtheresultingnodestothefrontieronlyifnotinthefrontierorexploredset树搜索算法实现N.state:对应状态空间中的状态N.parent:结点N的父结点N.action:父结点生成该结点所采取的行动N.path-cost:从初始状态到该结点的路径消耗树搜索算法实现状态对应于问题的物理配置情况结点是一种数据结构包括状态，父结点，行动，代价，结点深度搜索策略搜索策略是

5、指搜索树结点选择的搜索顺序FIFO队列LIFO队列优先级队列哈希表：快速有效检测重复状态算法性能Environment:Patient,hospital,staffActuators:Screendisplay(questions,tests,diagnoses,treatments,referrals)Sensors:Keyboard(entryofsymptoms,findings,patient'sanswers)性能评价标准完备性：如果问题存在解，算法即可找到解最优性：找到的解是最优解时间复

6、杂度：花费的时间空间复杂度：花费的内存时间空间复杂度的度量：时间由搜索过程中产生的结点数目来度量空间由内存中存储的最多结点数量来度量通常小于状态空间数量

7、V

8、+

9、E

10、无信息搜索策略无信息搜索除了问题定义中提供的状态信息外没有任何附加信息算法只能区分状态是不是目标状态无法比较非目标状态的好坏策略：宽度优先搜索一致代价搜索深度优先搜索深度受限搜索迭代加深的深度优先搜索18宽度优先搜索先扩展根结点，再扩展根结点的所有后继，然后再扩展它们的后继实现：FIFO队列19宽度优先搜索宽度优先搜索宽度优先搜索属性：完备性

11、？最优性？时间复杂度O(bd)空间复杂度O(bd)内存需求大时间复杂度高22一致代价搜索扩展未扩展结点中代价最小的实现：队列按照代价从小到大排列23一致代价搜索一致代价搜索完备性？最优性？时间复杂度O(b1+lowbound(C/e))空间复杂度O(b1+lowbound(C/e))深度优先搜索首先扩展最深的为扩展结点实现：用LIFO队列(栈)来存储结点深度优先搜索深度优先搜索深度优先搜索深度受限的搜索假定深度为l的结点没有后继结点深度优先搜索完备性？最优性？时间复杂度O(bm)空间复杂度O(bm)迭代加

12、深的深度优先算法结合了宽度优先和深度优先的优点迭代加深的深度优先算法迭代加深的深度优先算法迭代加深的深度优先算法对于深度为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,111N