湖南大学人工智能课件3

第三章PartI通过搜索对问题求解内容提要问题求解Agent搜索求解无信息搜索策略搜索问题求解agent形式化搜索执行已知条件：一个agent在罗马尼亚度假，目前位于Arad城市Agent明天有航班从Bucharest起飞，不能改签退票形式化：形式化目标:赶往Bucharest形式化问题：状态:当前位置行动：城市之间穿梭搜索:城市之间穿梭路线e.g.,Arad，Sibiu,Fagaras,Bucharest状态空间初始状态：In(Arad)行动：{Go(Sibiu),Go(Timisoara),Go(Zerind)}转移模型:Result(In(Arad),Go(Zerind))=In(Zerind)目标：{In(Bucharest)}路径耗散:c(s,a,s’)状态?机器人的位置和灰尘位置初始状态？任何状态都可为初始状态行动?向左，向右，吸灰尘转移模型？状态+行动-新状态目标测试?检查所有位置是否干净路径消耗?1/行动状态?8个棋子以及空格在棋盘9个方格上的分布初始状态？任何状态都可为初始状态行动?向左，向右，向上，向下转移模型？状态+行动-新状态目标测试?检查状态是否匹配目标状态路径消耗?1/行动状态?初始状态？行动?转移模型？目标测试?路径消耗?如何减少它的状态空间？基本思路：从初始状态/已知状态开始，通过行动不断地探索其他状态直到找到目标状态(成功)或者没有行动可执行为止(失败)树表示：根节点：初始状态连线：行动结点：状态空间中的状态InitializetheexploredsettobeemptyAddthenodetotheexploredsetExpandthechosennode,addingtheresultingnodestothefrontieronlyifnotinthefrontierorexploredsetN.state:对应状态空间中的状态N.parent:结点N的父结点N.action:父结点生成该结点所采取的行动N.path-cost:从初始状态到该结点的路径消耗状态对应于问题的物理配置情况结点是一种数据结构包括状态，父结点，行动，代价，结点深度搜索策略是指搜索树结点选择的搜索顺序FIFO队列LIFO队列优先级队列哈希表：快速有效检测重复状态Environment:Patient,hospital,staffActuators:Screendisplay(questions,tests,diagnoses,treatments,referrals)Sensors:Keyboard(entryofsymptoms,findings,patient'sanswers)性能评价标准完备性：如果问题存在解，算法即可找到解最优性：找到的解是最优解时间复杂度：花费的时间空间复杂度：花费的内存时间空间复杂度的度量：时间由搜索过程中产生的结点数目来度量空间由内存中存储的最多结点数量来度量通常小于状态空间数量|V|+|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搜索求解无信息搜索策略宽度优先搜索一致代价搜索深度优先搜索迭代加深的深度优先搜索双向搜索QA？