湖南大学人工智能课件3.pptx

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

2、ult(In(Arad),Go(Zerind)=In(Zerind)目标：In(Bucharest)路径耗散:c(s,a,s) 状态? 机器人的位置和灰尘位置 初始状态？任何状态都可为初始状态 行动? 向左，向右，吸灰尘 转移模型？状态+行动-新状态 目标测试? 检查所有位置是否干净 路径消耗? 1 /行动 状态? 8个棋子以及空格在棋盘9个方格上的分布 初始状态？任何状态都可为初始状态 行动? 向左，向右，向上，向下 转移模型？状态+行动-新状态 目标测试? 检查状态是否匹配目标状态 路径消耗? 1 /行动状态? 初始状态？行动? 转移模型？目标测试? 路径消耗? 如何减少它的状态空间？如何

3、减少它的状态空间？基本思路：从初始状态/已知状态开始，通过行动不断地探索其他状态直到找到目标状态(成功)或者没有行动可执行为止(失败)树表示：根节点：初始状态连线：行动结点：状态空间中的状态Initialize the explored set to be emptyAdd the node to the explored setExpand the chosen node, adding the resulting nodes to the frontier only if not in the frontier or explored setN.state:对应状态空间中的状态N.pare

4、nt:结点N的父结点N.action:父结点生成该结点所采取的行动N.path-cost:从初始状态到该结点的路径消耗状态对应于问题的物理配置情况结点是一种数据结构包括状态，父结点，行动，代价，结点深度搜索策略是指搜索树结点选择的搜索顺序FIFO队列LIFO队列优先级队列哈希表：快速有效检测重复状态性能评价标准完备性：如果问题存在解，算法即可找到解最优性：找到的解是最优解时间复杂度：花费的时间空间复杂度：花费的内存时间空间复杂度的度量：时间由搜索过程中产生的结点数目来度量空间由内存中存储的最多结点数量来度量通常小于状态空间数量|V|+|E|无信息搜索除了问题定义中提供的状态信息外没有任何附加信

5、息算法只能区分状态是不是目标状态无法比较非目标状态的好坏策略：宽度优先搜索一致代价搜索深度优先搜索深度受限搜索迭代加深的深度优先搜索先扩展根结点，再扩展根结点的所有后继，然后再扩展它们的后继实现：FIFO队列属性：完备性？最优性？时间复杂度O(bd)空间复杂度O(bd)内存需求大时间复杂度高扩展未扩展结点中代价最小的实现：队列按照代价从小到大排列完备性？最优性？时间复杂度O(b1+lowbound(C/e)空间复杂度O(b1+lowbound(C/e)首先扩展最深的为扩展结点实现：用LIFO队列(栈)来存储结点假定深度为l的结点没有后继结点完备性？最优性？时间复杂度O(bm)空间复杂度O(bm

6、)结合了宽度优先和深度优先的优点对于深度为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？