首页 > 代码库 > 1、通过搜索进行问题求解

1、通过搜索进行问题求解

  • 一个问题由5部分组成:初始状态行动集合,转移模型目标测试函数,路径代价函数。问题的环境用状态空间表示。状态空间中从初始状态到达目标状态的路径是一个解。
  • 可以从完备性最优性时间复杂度空间复杂度等方面来评价一个搜索算法。
  • 主要分为:无信息搜索策略(盲搜)、有信息搜索策略(启发式搜索)
  • 无信息搜索策略(盲搜):
    •   宽度优先
    •   一致代价搜素(借助一个最小堆,每次选择代价最小的状态前进),类似dijkstra
    •       深度优先搜索
    •      迭代加深搜索(加一个深度限制)
    •       双向搜索(在起点和终点分别进行宽度优先或者迭代加深的深度优先,直到两个圆相交)
  •   有信息的搜索(一般的最佳优先搜索,需要访问启发式函数 h(n) 来估算从n到目标的解代价)。
    •   贪婪最佳优先搜索选择扩展 h(n)最小的结点(比如旅行问题中,每一步选择各个临结点中距离目标结点最近的结点),可能不是最优解。
    •       A*搜索扩展 f(n) = g(n) + h(n)最小的结点。
      •   h(n)的选择,保证是最优解:1)可采纳性  2)一致性(单调性)。 
      •       例如:旅行问题中: f(n) = g(n)  + h(n)
      •       f(n) = 经过结点 n 的最小代价解的估计代价;g(n)  = 从开始结点到结点n的路径代价,而h(n) = 从结点n到目标结点的最新代价路径的估计值(在这里采用直线距离) 

1、通过搜索进行问题求解