第三章启发式搜索

第三章启发式搜索的思维导图导图，A算法、A*算法，启发式搜索算法、基本思想、算法框架、常见的算法等内容。

第三章 启发式搜索

• A算法
  • 启发式搜索算法
    • 启发式信息
      • 人类有关求解问题的直观感觉或经验，通常是无法证明的
    • 利用启发式信息引导搜索算法，从而达到减少搜索范围或降低问题复杂度的目的，将人类求解问题的经验固化到求解算法中。
    • 启发式信息的使用
      • 使用强
        • 降低搜索规模，但可能找不到最优解
      • 使用弱
        • 搜索工作量大，极端情况下变成盲目搜索，但可能找到最优解
      • 关键
        • 如何利用启发式信息，尽可能有效地找到问题的近似最优解
  • 基本思想
    • 基于一般图搜素算法
    • 定义一个评估函数f，对当前的搜索状态进行评估，从open表找出最有希望的节点进行扩展。（排序规则）
    • 评估函数
      • f(n) = g(n) + h(n)
      • g*(n)：从起始点S到n的最短路径的耗散值
      • h*(n)：从n到目标节点T的最短路径的耗散值
      • f*(n)：从起始节点S经过n到达目标节点T的最短路径的耗散值，f*(n)=g*(n)+h*(n)
      • g(n)、h(n)、f(n)分别是对g*(n)、h*(n)、f*(n)的估计
  • 算法框架
  • 常见的算法
    • 爬山法
      • 总是考虑与目标之间的差距，g(n)=0，仅考虑h(n)
    • 分支界限法
      • 总是扩展具有最小耗散值的节点，使用g(n)，h(n)=0
    • 动态规划法
      • 总是扩展具有最小耗散值的节点，并且删除明显不可能的路径，使用g(n)，h(n)=0
• A*算法
  • 定义
    • 在A算法中，如果满足条件：h(n)<=h*(n)，则A算法称为A*算法
  • A*算法的性质
    • A*算法的假设
      • 任意两个节点之间的耗散值大于0
    • A*算法的重要等式
      • f*(S)=f*(T)=g*(T)=h*(S)=f*(n)，n在S到T的最佳路径上
  • A*算法的改进
    • 存在的问题
      • 问题的提出
        • 因A算法第6步对ml类节点可能要重新放回到open表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降
      • 原因
        • 在前面的扩展中，没有找到从S到n的最短路径，即，g*(n)与g(n)不相等
    • 问题的解决
      • 改进的条件
        • 可采纳性不变(能找到最优解)
        • 不多扩展节点
        • 不增加算法的复杂性
      • 对h加以限制
        • h单调性的定义
        • h单调的性质
        • h的单调化方法
      • 对算法加以改进
        • 改进的出发点
          • fm是指当前已扩展节点的最大f值，利用fm代替f*(S)
        • 算法框架
• 最佳图搜索算法
• 启发式搜索算法