第3章-搜索策略ppt课件.ppt

《第3章-搜索策略ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章搜索策略问题求解系统划分为两大类知识贫乏系统依靠搜索技术解决问题知识贫乏、缺乏针对性效率低知识丰富系统依靠推理技术解决问题基于丰富知识的推理技术，直截了当效率高8/10/202113.1引言对于给定的问题，智能系统的行为一般是找到能够达到所希望目标的动作序列，并使其所付出的代价最小、性能最好。基于给定的问题，问题求解的第一步是目标的表示。搜索就是找到智能系统的动作序列的过程。8/10/20212和通常的搜索空间不同，人工智能中大多数问题的状态空间在问题求解之前不是全部知道的。在人工智能中，搜索问题一般包括两个重要的问题：搜索什么搜索什么通常指的就是目标。在哪里搜索在哪里搜索就是“搜

2、索空间”。搜索空间通常是指一系列状态的汇集，因此称为状态空间。8/10/20213所以，人工智能中的搜索可以分成两个阶段：状态空间的生成阶段在该状态空间中对所求问题状态的搜索搜索可以根据是否使用启发式信息分为盲目搜索启发式搜索8/10/20214盲目搜索只是可以区分出哪个是目标状态。一般是按预定的搜索策略进行搜索。没有考虑到问题本身的特性，这种搜索具有很大的盲目性，效率不高，不便于复杂问题的求解。启发式搜索是在搜索过程中加入了与问题有关的启发式信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解并找到最优解。8/10/20215根据问题的表示方式分为状态空间搜索与或树搜索状态空间搜索

3、是用状态空间法来求解问题所进行的搜索与/或树搜索是指用问题规约方法来求解问题时所进行的搜索。8/10/20216考虑一个问题的状态空间为一棵树的形式。宽度优先搜索深度优先搜索如果根节点首先扩展，然后是扩展根节点生成的所有节点，然后是这些节点的后继，如此反复下去。在树的最深一层的节点中扩展一个节点。只有当搜索遇到一个死亡节点（非目标节点并且是无法扩展的节点）的时候，才返回上一层选择其他的节点搜索。8/10/20217无论是宽度优先搜索还是深度优先搜索，遍历节点的顺序一般都是固定的，即一旦搜索空间给定，节点遍历的顺序就固定了。这种类型的遍历称为“确定性”的，也就是盲目搜索。对于启发式搜索，在

4、计算每个节点的参数之前无法确定先选择哪个节点扩展，这种搜索一般也称为非确定的。8/10/20218完备性：如果存在一个解答，该策略是否保证能够找到？时间复杂性：需要多长时间可以找到解答？空间复杂性：执行搜索需要多少存储空间？最优性：如果存在不同的几个解答，该策略是否可以发现最高质量的解答？搜索策略评价标准:8/10/20219有许多智力问题(如梵塔问题、旅行商问题、八皇后问题、农夫过河问题等)和实际问题（如路径规划、机器人行动规划等）都可以归结为状态空间搜索。用状态空间搜索来求解问题的系统均定义一个状态空间，并通过适当的搜索算法在状态空间中搜索解答路径。3.2基于状态空间的搜索技术8/1

5、0/2021103.2.1图搜索的基本概念显式图与隐式图显式图把问题有关的全部状态空间图，即相应的全部有关知识(叙述性知识、过程性知识和控制性知识)，都直接存入知识库隐式图只存储与问题求解有关的部分知识(即部分状态空间)。这种存储方式称为隐式存储。8/10/202111图搜索的基本思想图搜索-一种在图中寻找路径的方法从图中的初始节点开始，至目标节点为止。初始节点和目标节点分别代表产生式系统的初始数据库和满足终止条件的数据库。方法：把问题的初始状态作为当前状态，选择适用的算符对其进行操作，生成一组子状态，检查目标状态是否在其中出现。若出现，则搜索成功，找到了问题的解；若不出现，则按某种搜索

6、策略从已生成的状态中再选一个状态作为当前状态。重复上述过程，直到目标状态出现或者不再有可供操作的状态及算符时为止。8/10/2021123.2.2状态空间搜索——1.什么是状态空间图例：钱币翻转问题设有3个钱币，其初始状态为(反、正、反),欲得的目标状态为(正、正、正)或(反、反、反)。问题是允许每次只能且必须翻转一个钱币，连翻三次。问能否达到目标状态。引入一个三维变量将问题表示出来。设三维变量为：Q=[q1,q2,q3]，式中qi(i=1,2,3)=0表示钱币为正面，qi(i=1,2,3)=1表示钱币为反面。三个钱币可能出现的状态有8种组合：Q0=(0,0,0),Q1=(0,0,1)

7、,Q2=(0,1,0),Q3=(0,1,1),Q4=(1,0,0),Q5=(1,0,1),Q6=(1,1,0),Q7=(1,1,1)。8/10/202113三枚钱币问题的状态空间图8/10/2021143.2.2状态空间搜索——2.问题的状态空间表示法(1)状态空间的表示状态空间记为SP，可表示为二元组：SP=(S,O)S——问题求解（即搜索）过程中所有可能到达的合法状态构成的集合；O——操作算子的集合，操作算子的执行会导致问题状