首页 > 代码库 > 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、通过搜索进行问题求解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。