启发式搜索

• 启发式算法
  • 正向推理
    • 初始状态向目标状态方向执行
    • 一般用于状态空间的搜索
  • 反向推理
    • 目标状态出发向初始状态方向执行
    • 一般用于问题规约
  • A算法
    • f(x)计算代价最小的节点先出表
  • A*算法
    • 可采纳性(Admissibility)
      • 搜索法总能找到最短(代价最小)的解答路径，则算法具有可采纳性
      • 宽度优先搜索就是可采纳的，只是效率不高
      • h(n) ⇐ h’(n)
        • 估计代价 ⇐ 实际代价
        • h(x)接近h*(x)的程度衡量启发式函数的强弱
          • 接近程度是A*算法的关键
          • h(x)包含的启发式信息越多越好
          • 多个h(x)设计方案，效果最好的那个就是A*算法，其他的都是A算法
    • 迭代加深A*算法
      • 为了优化空间
      • 设置限制值c
        • 只有当前节点n的子节点n’的f(n’) < c时，才扩展n’放到栈中，并更新c的值为min(c, f(n’))
        • 算法终止条件
          • 找到目标节点
          • 栈为空且c’=无穷大
  • 爬山法
    • 贪心法选h(x)最小的节点扩展
    • 回溯策略
      • 爬山法加搜索失败时回溯
      • 影响效率的关键因素是回溯次数，所以好的启发式函数h(x)剪枝重要
• 概念
  • 启发式搜索
    • 选择节点时能充分利用与问题有关的特征信息，估计与节点的重要性，搜索时选择重要性高的节点，以求得最优解
  • 启发信息
    • 与被解问题的某些特征值有关的控制信息
      • 解的出现规律
      • 解的结构特征
  • 评估函数
    • 评估待扩展各节点的重要性
    • f(x) = g(x) + h(x)
      • g(x)表示从初始节点到节点x的实际代价
      • h(x)节点x到目标节点的最优路径的估计代价
        • 体现了问题的启发式信息
        • h(x)称为启发式函数
      • h(x)的设计
        • g(x)=0，接近于深度优先搜索
        • h(x)=0，接近于宽度优先搜索
        • 加入权值w，使f(x) = g(x) + wh(x)
          • 浅层时，w取大值，使g(x)占比小，突出启发函数，加速深度搜索
          • 深层时，w取小值，使g(x)占比大，加速广度搜索