湖南大学人工智能课件3

第三章

PartI

通过搜索对问题求解

第三章

PartI

通过搜索对问题求解

2015年1月湖南大学信息科学与工程学院内容提要问题求解Agent搜索求解无信息搜索策略内容提要问题求解Agent2问题求解agent搜索问题求解agent形式化搜索执行问题求解agent搜索问题求解agent3实例：Romania已知条件：一个agent在罗马尼亚度假，目前位于Arad城市Agent明天有航班从Bucharest起飞，不能改签退票实例：Romania已知条件：4实例：Romania形式化：形式化目标:赶往Bucharest形式化问题：状态:当前位置行动：城市之间穿梭搜索:城市之间穿梭路线e.g.,Arad，Sibiu,Fagaras,Bucharest实例：Romania形式化：5实例：Romania状态空间初始状态：In(Arad)行动：{Go(Sibiu),Go(Timisoara),Go(Zerind)}转移模型:Result(In(Arad),Go(Zerind))=In(Zerind)目标：{In(Bucharest)}路径耗散:c(s,a,s’)实例：Romania状态空间6实例：真空吸尘器世界状态?机器人的位置和灰尘位置初始状态？任何状态都可为初始状态行动?向左，向右，吸灰尘转移模型？状态+行动->新状态目标测试?检查所有位置是否干净路径消耗?1/行动实例：真空吸尘器世界状态?机器人的位置和灰尘位置7实例：八数码问题状态?8个棋子以及空格在棋盘9个方格上的分布初始状态？任何状态都可为初始状态行动?向左，向右，向上，向下转移模型？状态+行动->新状态目标测试?检查状态是否匹配目标状态路径消耗?1/行动实例：八数码问题状态?8个棋子以及空格在棋盘9个方格上的8八皇后问题状态?初始状态？行动?转移模型？目标测试?路径消耗?如何减少它的状态空间？八皇后问题状态?如何减少它的状态空间？9树搜索算法基本思路：从初始状态/已知状态开始，通过行动不断地探索其他状态直到找到目标状态(成功)或者没有行动可执行为止(失败)树表示：根节点：初始状态连线：行动结点：状态空间中的状态树搜索算法基本思路：从初始状态/已知状态开始，通过行动不断地10树搜索算法树搜索算法11树搜索算法实例树搜索算法实例12树搜索算法实例InitializetheexploredsettobeemptyAddthenodetotheexploredsetExpandthechosennode,addingtheresultingnodestothefrontieronlyifnotinthefrontierorexploredset树搜索算法实例Initializetheexplored13树搜索算法实现N.state:对应状态空间中的状态N.parent:结点N的父结点N.action:父结点生成该结点所采取的行动N.path-cost:从初始状态到该结点的路径消耗树搜索算法实现N.state:对应状态空间中的状态14树搜索算法实现状态对应于问题的物理配置情况结点是一种数据结构包括状态，父结点，行动，代价，结点深度树搜索算法实现状态对应于问题的物理配置情况15搜索策略搜索策略是指搜索树结点选择的搜索顺序FIFO队列LIFO队列优先级队列哈希表：快速有效检测重复状态搜索策略搜索策略是指搜索树结点选择的搜索顺序16算法性能Environment:Patient,hospital,staffActuators:Screendisplay(questions,tests,diagnoses,treatments,referrals)Sensors:Keyboard(entryofsymptoms,findings,patient'sanswers)性能评价标准完备性：如果问题存在解，算法即可找到解最优性：找到的解是最优解时间复杂度：花费的时间空间复杂度：花费的内存时间空间复杂度的度量：时间由搜索过程中产生的结点数目来度量空间由内存中存储的最多结点数量来度量通常小于状态空间数量|V|+|E|算法性能Environment:Patient,ho17无信息搜索策略18无信息搜索除了问题定义中提供的状态信息外没有任何附加信息算法只能区分状态是不是目标状态无法比较非目标状态的好坏策略：宽度优先搜索一致代价搜索深度优先搜索深度受限搜索迭代加深的深度优先搜索无信息搜索策略18无信息搜索宽度优先搜索19先扩展根结点，再扩展根结点的所有后继，然后再扩展它们的后继实现：FIFO队列宽度优先搜索19先扩展根结点，再扩展根结点的所有后继，然后再宽度优先搜索宽度优先搜索20宽度优先搜索宽度优先搜索21宽度优先搜索22属性：完备性？最优性？时间复杂度O(bd)空间复杂度O(bd)内存需求大时间复杂度高宽度优先搜索22属性：一致代价搜索23扩展未扩展结点中代价最小的实现：队列按照代价从小到大排列一致代价搜索23扩展未扩展结点中代价最小的一致代价搜索一致代价搜索24一致代价搜索完备性？最优性？时间复杂度O(b1+lowbound(C/e))空间复杂度O(b1+lowbound(C/e))一致代价搜索完备性？25深度优先搜索首先扩展最深的为扩展结点实现：用LIFO队列(栈)来存储结点深度优先搜索首先扩展最深的为扩展结点26深度优先搜索深度优先搜索27深度优先搜索深度优先搜索28深度优先搜索深度优先搜索29深度受限的搜索假定深度为l的结点没有后继结点深度受限的搜索假定深度为l的结点没有后继结点30深度优先搜索完备性？最优性？时间复杂度O(bm)空间复杂度O(bm)深度优先搜索完备性？31迭代加深的深度优先算法结合了宽度优先和深度优先的优点迭代加深的深度优先算法结合了宽度优先和深度优先的优点32迭代加深的深度优先算法迭代加深的深度优先算法33迭代加深的深度优先算法迭代加深的深度优先算法34迭代加深的深度优先算法对于深度为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迭代加深的深度优先算法对于深度为d，分支数为b的情况，35迭代加深的深度优先算法最优性?完整性?时间复杂度O(bd)空间复杂度O(bd)迭代加深的深度优先算法最优性?36双向搜索同时向前搜索和向后搜索当两种搜索模式相遇时算法停止直观上2*O(bd/2)远小于O(bd)双向搜索同时向前搜索和向后搜索37搜索算法对比搜索算法对比38问题求解agent问题求解Agent搜索求解无信息搜索策略宽度优先搜索一致代价搜索深度优先搜索迭代加深的深度优先搜索双向搜索问题求解agent问题求解Agent39Qa？

Qa？

第三章

PartI

通过搜索对问题求解

第三章

PartI

通过搜索对问题求解

2015年1月湖南大学信息科学与工程学院内容提要问题求解Agent搜索求解无信息搜索策略内容提要问题求解Agent42问题求解agent搜索问题求解agent形式化搜索执行问题求解agent搜索问题求解agent43实例：Romania已知条件：一个agent在罗马尼亚度假，目前位于Arad城市Agent明天有航班从Bucharest起飞，不能改签退票实例：Romania已知条件：44实例：Romania形式化：形式化目标:赶往Bucharest形式化问题：状态:当前位置行动：城市之间穿梭搜索:城市之间穿梭路线e.g.,Arad，Sibiu,Fagaras,Bucharest实例：Romania形式化：45实例：Romania状态空间初始状态：In(Arad)行动：{Go(Sibiu),Go(Timisoara),Go(Zerind)}转移模型:Result(In(Arad),Go(Zerind))=In(Zerind)目标：{In(Bucharest)}路径耗散:c(s,a,s’)实例：Romania状态空间46实例：真空吸尘器世界状态?机器人的位置和灰尘位置初始状态？任何状态都可为初始状态行动?向左，向右，吸灰尘转移模型？状态+行动->新状态目标测试?检查所有位置是否干净路径消耗?1/行动实例：真空吸尘器世界状态?机器人的位置和灰尘位置47实例：八数码问题状态?8个棋子以及空格在棋盘9个方格上的分布初始状态？任何状态都可为初始状态行动?向左，向右，向上，向下转移模型？状态+行动->新状态目标测试?检查状态是否匹配目标状态路径消耗?1/行动实例：八数码问题状态?8个棋子以及空格在棋盘9个方格上的48八皇后问题状态?初始状态？行动?转移模型？目标测试?路径消耗?如何减少它的状态空间？八皇后问题状态?如何减少它的状态空间？49树搜索算法基本思路：从初始状态/已知状态开始，通过行动不断地探索其他状态直到找到目标状态(成功)或者没有行动可执行为止(失败)树表示：根节点：初始状态连线：行动结点：状态空间中的状态树搜索算法基本思路：从初始状态/已知状态开始，通过行动不断地50树搜索算法树搜索算法51树搜索算法实例树搜索算法实例52树搜索算法实例InitializetheexploredsettobeemptyAddthenodetotheexploredsetExpandthechosennode,addingtheresultingnodestothefrontieronlyifnotinthefrontierorexploredset树搜索算法实例Initializetheexplored53树搜索算法实现N.state:对应状态空间中的状态N.parent:结点N的父结点N.action:父结点生成该结点所采取的行动N.path-cost:从初始状态到该结点的路径消耗树搜索算法实现N.state:对应状态空间中的状态54树搜索算法实现状态对应于问题的物理配置情况结点是一种数据结构包括状态，父结点，行动，代价，结点深度树搜索算法实现状态对应于问题的物理配置情况55搜索策略搜索策略是指搜索树结点选择的搜索顺序FIFO队列LIFO队列优先级队列哈希表：快速有效检测重复状态搜索策略搜索策略是指搜索树结点选择的搜索顺序56算法性能Environment:Patient,hospital,staffActuators:Screendisplay(questions,tests,diagnoses,treatments,referrals)Sensors:Keyboard(entryofsymptoms,findings,patient'sanswers)性能评价标准完备性：如果问题存在解，算法即可找到解最优性：找到的解是最优解时间复杂度：花费的时间空间复杂度：花费的内存时间空间复杂度的度量：时间由搜索过程中产生的结点数目来度量空间由内存中存储的最多结点数量来度量通常小于状态空间数量|V|+|E|算法性能Environment:Patient,ho57无信息搜索策略58无信息搜索除了问题定义中提供的状态信息外没有任何附加信息算法只能区分状态是不是目标状态无法比较非目标状态的好坏策略：宽度优先搜索一致代价搜索深度优先搜索深度受限搜索迭代加深的深度优先搜索无信息搜索策略18无信息搜索宽度优先搜索59先扩展根结点，再扩展根结点的所有后继，然后再扩展它们的后继实现：FIFO队列宽度优先搜索19先扩展根结点，再扩展根结点的所有后继，然后再宽度优先搜索宽度优先搜索60宽度优先搜索宽度优先搜索61宽度优先搜索62属性：完备性？最优性？时间复杂度O(bd)空间复杂度O(bd)内存需求大时间复杂度高宽度优先搜索22属性：一致代价搜索63扩展未扩展结点中代价最小的实现：队列按照代价从小到大排列一致代价搜索23扩展未扩展结点中代价最小的一致代价搜索一致代价搜索64一致代价搜索完备性？最优性？时间复杂度O(b1+lowbound(C/e))空间复杂度O(b1+lowbound(C/e))一致代价搜索完备性？65深度优先搜索首先扩展最深的为扩展结点实现：用LIFO队列(栈)来存储结点深度优先搜索首先扩展最深的为扩展结点66深度优先搜索深度优先搜索67深度优先搜索深度优先搜索68深度优先搜索深度优先搜索69深度受限的搜索假定深度为l的结点没有后继结点深度受限的搜索假定深度为l的结点没有后继结点70深度优先搜索完备性？最优性？时间复杂度O(bm)空间复杂度O(bm)深度优先搜索完