第三章 一、启发式搜索
1、启发式搜索的基本概念、思想(考)
启发式搜索要用到问题自身的某些特性信息,以指导搜索朝着最有希望的方向前进。在
搜索中,关键的一步就是如何选择下一个要考察的节点。在选择节点时充分利用与问题有关
的特征信息,估计出节点的重要性,在搜索时选择重要性较高的节点,以利于求得最优解。
2、启发信息的强度 强:降低搜索工作量,但可能导致找不到最优解
弱:一般导致工作量加大,极限情况下变为盲目搜索,但可能可以找到最优解
3、启发性信息和估价函数
启发性信息:用于指导搜索过程,且与具体问题有关的控制性信息称为为启发性信息
估价函数:用于评价节点重要性的函数称为估价函数.记为 f(x) = g(x) + h(x)
g(x)为从初始节点 S0 到节点 x 已经实际付出的代价 h(x)是从节点 x 到目标节点 Sg
的最优路径的估计代价,体现了问题的启发性信息,称为启发函数
f(x)表示从初始节点经过节点 x 到达目标节点的最优路径的代价估价值,其作用是用来评
估 OPEN 表中各节点的重要性,决定其次序。
4、局部择优搜索(爬山算法)和全局择优(有序搜索/最好优先)基本思想(考)
启发式搜索爬山算法是一种简单的贪心搜索算法,该算法每次从当前解的临近解空间中
选择一个最优解作为当前解,直到达到一个局部最优解。
局部择优算法,是对深度优先搜索的一种改进。
局部择优搜索(爬山)基本思想:利用评估函数 f(x)来估计目标状态和当前状态的“距离”。
① 当一个节点被扩展后,对子节点 x 进行评估得到 f(x),按 f(x)的升序排列并把这些节点压
人栈。因此,栈顶元素具有最小的 f(x)值。
② 弹出栈顶元素并和目标状态比较。如果栈顶元素不是目标,则扩展栈顶元素,并计算其
所有子状态的 f 值,并按升序把这些子状态压入栈中。
③ 如果栈顶元素是目标,则算法退出。否则该过程循环下去,直至栈为空。
④爬山算法中依然采用深度优先的基本思想,具有局部最优。
全局择优搜索基本思想:从最有希望的节点开始,并生成其所有的子女节点。然后计算所有
节点的性能,基于该性能选择最有希望的节点扩展,而不仅仅是从当前节点所生成的子女节
点中选择。因此,如果在早期选择了一个错误的节点,全局择优提供了一个修改的余地,这
也是其较爬山算法较好之处。
5、局部择优搜索(爬山算法)和全局择优(有序搜索/最好优先)搜索过程(不考)
①局部择优搜索过程:
(1)把初始节点 S0 放入 OPEN 表,计算 f(S0) (2)如果 OPEN 表为空,则问题无解,退出
(3)把 OPEN 表的第一个节点(记为节点 n)取出,放入 CLOSED 表
(4)考查节点 n 是否为目标节点.若是,则求得了问题的解,退出
(5)若节点 n 不可扩展,则转第(2)步
(6)扩展节点 n,用估价函数 f(x)计算每个子节点的估价值,并按估价值从小到大的顺序依
次放入 OPEN 表的首部,并为每一个子节点都配置指向父节点的指针,转第(2)步
②全局择优搜索过程:
(1)把初始节点 S0 放入 OPEN 表,计算 f(S0) (2)如果 OPEN 表为空,则问题无解,退出
(3)把 OPEN 表的第一个节点(记为节点 n)取出,放入 CLOSED 表
(4)考查节点 n 是否为目标节点.若是,则求得了问题的解,退出
(5)若节点 n 不可扩展,则转第(2)步
(6)扩展节点 n,用估价函数 f(x)计算每个子节点的估价值,并为每一个子节点都配置指向
父节点的指针,把这些子节点都送入 OPEN 表,然后对 OPEN 表中的全部节点按估价值从小到