第五章 状态空间的搜索策略ppt课件.ppt

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

1、状态空间的搜索策略北京师范大学信息科学与技术学院王醒策概述教学内容搜索的概念及种类盲目搜索策略启发式搜索策略教学重点宽度优先搜索、深度优先搜索及代价树的搜索算法，A*搜索算法教学难点利用各种搜索算法解决实际问题，尤其是估价函数的选取概述有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。概述搜索是人工智能中的基本问题搜索中的知识表示状态空间表示法与/或树表示法很多问题可以转化为搜索问题搜索的概念以及分类搜索的概念根据问题的实际情况，按照一定的策略或者规划，从知识库中寻找可以利用的知识，从而构造出一条使得问题获得解决的推理路线的过程搜索的

2、两层含义要找到从初始事实到问题最终答案的一条推理路线找到的这条路线是时间和空间复杂度最小的求解路线搜索的种类搜索可以分为盲目搜索和启发式搜索两种盲目搜索又称为无信息搜索。也就是在搜索的过程中只按预先的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略启发式搜索称为有信息搜索。它是指在问题搜索过程中，根据问题本身的特征或者搜索过程中产生出来的一些信息来不断地改变或者调整搜索方向，使搜索朝着最有希望的方向前进，加速问题的求解，并找到最优解。人工智能领域中已有搜索方法（1）求任一解路的搜索策略回溯法（Backtracking）爬山法（HillClimbing）宽度优先法（Breadth-

3、first）深度优先法（Depth-first）限定范围搜索法（BeamSearch）好的优先法（Best-first）人工智能领域中已有搜索方法（2）求最佳解路的搜索策略大英博物馆法（BritishMuseum）分枝界限法（BranchandBound）动态规划法（DynamicProgramming）最佳图搜索法（A﹡）人工智能领域中已有搜索方法（3）求与或关系解图的搜索法一般与或图搜索法（AO﹡）极小极大法（Minimax）α－β剪枝法（Alpha-betaPruning）启发式剪枝法（HeuristicPruning）回溯搜索（Backtrackingstrategies）回溯搜索

4、策略是盲目搜索中的一种。思想为：首先将规则给出一个固定的排序；在搜索时，对当前状态（搜索开始时，当前状态是初始状态）依次检测每一条规则；在当前状态未使用过的规则中找到第一条可触发规则，被应用于当前状态；得到的新状态重新设置为当前状态，并重复以上搜索；如果当前状态无规则可用，或者所有规则已经被试探过仍未找到问题的解，则将当前状态的前一个状态（即直接生成该状态的状态）设置为当前状态。重复以上搜索，直到找到问题的解，或者试探了所有可能后仍找不到问题的解为止。回溯搜索举例说明：四皇后问题在一个4×4的国际象棋棋盘上，一次一个地摆布四枚皇后棋子，摆好后要满足每行、每列和对角线上只允许出现一枚棋子，即

5、棋子间不许相互俘获。回溯搜索给出棋盘的几个势态，其中a，b满足目标条件，c，d，e为不合法状态，即不可能构成满足目标条件的中间态势回溯搜索搜索方法的实现——递归实现递归方法的特点递归必须要有出口递归公式中，每一次调用必须距出口更近一些回溯搜索回溯搜索算法步骤Backtrack(DATA)①如果当前状态DATA为目标状态，则找到目标。②该状态不合法，则过程返回失败信息，必须回溯。③计算DATA（当前状态）的可应用规则集，依某种原则（任意排列或按启发式准则）排列后赋给RULES。④如果规则用完未找到目标，过程返回FAIL，必须回溯。回溯搜索⑤取头条可应用规则。⑥删去头条规则，减少可应用规则表的

6、长度。⑦调用规则R作用于当前状态，生成新状态（RDATA）。⑧对新状态递归调用本过程。⑨当PATH＝FAIL时，递归调用失败，则转移回第四步，调用另一规则进行测试。⑩过程返回解路径规则表（或局部解路径子表）。回溯搜索回溯搜索会出现的问题深度问题死循环问题回溯搜索回溯中失败原因的分析——多步回溯问题回溯搜索中知识的应用盲目搜索策略状态空间图的搜索策略宽度优先搜索策略深度优先搜索策略代价树的宽度优先搜索代价树的深度优先搜索盲目搜索的性质总结状态空间图的搜索策略算法思想：首先将问题的初始状态（即状态空间中的初始节点）当作是当前状态。选择一个合适的算符作用于当前状态，生成一组后继状态（或称为）后继

7、节点，然后检查这组后继状态中有没有目标状态。如果有，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解；若没有，则按照某种控制策略从已生成的状态中再选一个状态作为当前状态，重复上述的过程直到目标状态不在出现或者不再有可供操作的状态及算符为止。状态空间图的搜索策略图论中的几个术语节点深度：初始节点（根节点）的深度为0任何其它节点的深度等于父节点的深度加1路径：设一节点的序列为（n0,n1…,ni,…,nk）i=1