湖南大学人工智能幻灯片3
第三章 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),实例：真空吸尘器世界,状态? 机器人的位置和灰尘位置 初始状态？任何状态都可为初始状态 行动? 向左，向右，吸灰尘 转移模型？状态+行动-新状态 目标测试? 检查所有位置是否干净 路径消耗? 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:对应状态空间中的状态 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, patient's answers),性能评价标准 完备性：如果问题存在解，算法即可找到解 最优性：找到的解是最优解 时间复杂度：花费的时间 空间复杂度：花费的内存 时间空间复杂度的度量： 时间由搜索过程中产生的结点数目来度量 空间由内存中存储的最多结点数量来度量 通常小于状态空间数量|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,问题求解Agent 搜索求解 无信息搜索策略 宽度优先搜索 一致代价搜索 深度优先搜索 迭代加深的深度优先搜索 双向搜索,Qa？,
