文档介绍：人工智能的搜索算法?在智能过程中,搜索是不可避免的———— Nilsson ?一个物理符号系统解决任何智能问题的充分和必要条件———— Newell 搜索法简介?搜索法是人工智能中问题求解的基本方法?可大致分为有信息搜索和无信息搜索?约束满足问题和博弈问题的求解均可表述为搜索过程? Agent 的学****过程亦可表述为搜索过程?搜索法的本质是在状态空间中从问题的初始状态搜索到通向目标状态的路径搜索法简介?当前的智能计算方法本质上也是搜索方法,如神经网络、遗传算法、蚁群算法等?搜索法的设计主要考虑解路径的耗散值以及搜索过程中的耗散值——耗费最低化算法性能的评价?评价算法性能的四个方面: ?完备性:有解时能保证找到解(可判定问题) ?最优性:能否找到最优解?时间复杂度?空间复杂度搜索算法的评价?搜索法要处理的是状态空间图?在人工智能领域,状态空间图是由初始状态和后继函数隐含表示的(与通常的计算机图搜索算法不同) ?搜索算法可从以下三个方面评价: ? b: 分支因子? d: 最浅目标节点的深度? m: 状态空间中最大路径长度(考虑耗散) 问题的形式化?搜索法首先要对问题进行形式化描述?问题通常可形式化定义为下述四个部分? Agent 所处的初始状态? Agent 可采纳的行动:后继函数?目标测试:确定当前状态是否是目标状态?路径耗散函数:为每条路径分配量化的耗散值举例:八数码问题盲目搜索?广度优先搜索: ?在下一层节点被扩展之前保证本层节点都被扩展?通常用 FIFO 队列实现?能保证找到最浅的目标节点(不一定是最优的) ?在单步耗散相同时是最优算法?空间复杂度大, ?目标节点较深时,时间复杂度亦很大)( 1?dbO盲目搜索?代价一致搜索: ?与广度优先搜索类似,但首先扩展耗费最低的节点?须保证算法的完备性(为每一步设定最小耗散) ?最坏时间复杂度为)( *? cbO