第二章一般图搜索

这是一篇有关第二章一般图搜索的思维导图，从搜索定义、一般图搜索的基本概念、一般图搜索算法等方面进行了概述。

第二章 一般图搜索

• 搜索
  • 搜索定义
    • 搜索算法是指利用计算机的高性能来有目的的穷举一个问题解空间的部分或全部的可能情况，从而求出问题的解的一种计算机算法。
  • 搜索算法
    • 基于方法
      • 一般图搜索
      • 启发式搜索
      • 不确定搜索
    • 基于问题
      • 博弈搜素
      • 约束满足
• 一般图搜索的基本概念
  • 图搜索
    • 搜索过程利用图的形式呈现出来
    • 计算机的图是由一系列顶点组成的，顶点之间通过边连接
  • 节点深度
  • 路径
  • 路径的耗散值
  • 扩展一个节点
    • 扩展当前节点的所有后继节点
    • 并计算出当前节点到其后继节点的耗散值
  • 问题状态、初始状态、目标状态、状态空间
• 一般图搜索算法
  • 基本思想
    • 从给定的初始状态出发
    • 一步一步的选取一个节点进行扩展，并更新状态
    • 重复上述步骤，直到扩展目标节点T(T到S的路径就是所求的解)，或者没有节点可以扩展
  • 算法框架
    • 节点类型
      • mj：新扩展出来的节点
      • mk：节点在open表中，由其他父节点已经扩展过该节点
      • ml：节点在closed表中，该节点已经被扩展过
  • 搜索问题求解
    • 初始状态
    • 目标状态
    • 扩展规则及排序规则
    • 耗散值函数