1、问题求解的基本方法启发式搜索 2盲目搜索 3盲目搜索算法的缺点： 盲目应对之道：引入与应用领域相关的启发式知识来指导OPEN表中节点的排序 4 局部排序 -这是对深度优先法的改进，仅对新扩展出来的子节点排序，使这些节点中最有希望者能优先取出考察和扩展 全局排序 -对 OPEN表中的所有节点排序，使最有希望的节点排在表首 5启发式搜索概念：在搜索过程中，引入启发式知识减少搜索的盲目性，提高搜索的效率，称之为启发式搜索启发式知识对搜索的作用： 选择下一个要被扩展的节点，对 OPEN表进行排序 在扩展一个节点时，仅仅有选择性的生成部分有用的节点 修剪掉某些估计不可能导致成功的子节点 6启发式搜索 -
2、算法 A应用评价函数来实现启发式搜索的典型是算法 A ，评价函数 f(n)：f(n)= g(n) + h(n) n-搜索图中的某个当前被扩展的节点； f(n)-从初始状态节点 s, 经由节点 n到达目标状态节点ng，估计的最小路径代价 g(n)-从 s到 n ,估计的最小路径代价； h(n)-从 n到 ng,估计的最小路径代价； 7g(n)是已知的h(n)是未知的，需要采用启发式函数来估算，称为启发式函数 8算法 A搜索算法 A的一般过程：1） G := s； 2） OPEN := (s), CLOSE := ( )； 3） 若 OPEN是空表，则算法以失败结束； 4） n := MOVE-F
3、IRST(OPEN)；5） 若 n是目标状态节点，则搜索成功结束，并给出解答路径；6） 扩展节点 n,将非节点 n祖先的子节点置于子节点集合 SNS中， 并插入搜索图 G中，对于 SNS中每个子节点 ni,计算f(n,ni) = g(n,ni) + h(ni); 97） 标记和修改指针把 SNS中的子节点分为三类（同一般图搜索算法）加第 1类子节点于 OPEN表（同一般图搜索算法）比较第 2类子节点 ni经由新、老父节点的评价函数值 f(n,ni)、 f(ni);若 f(n,ni) f(ni)点 ,则令 f(ni) = f(n,ni),并移动子节点指向老父节点的指针，改为指向新父节点对第 3类子节点作与第 2类同样的处理，并把这些子节点从CLOSE表中移出，重新加入 OPEN表。8）按 f值从小到大排序 OPEN表中的节点 9) 返回语句 3）； 10搜索算法的一般过程：1） G := s； 2） OPEN := (s), CLOSE := ( )； 3） 若 OPEN是空表，则算法以失败结束； 4） n := MOVE-FIRST(OPEN)；5） 若 n是目标状态节点，则搜索成功结束，并给出解答路径；6） 扩展节点 n，将非节点 n祖先的子节点置于子节点集合SNS中，并插入搜索图 G中；
