cs50ai0-------Search
基础知识
(1) search problem
上图是搜索问题的一般形式
每个名词具体解释如下：
initial state：state是agent与environment的一个配置或者说构造，initial state就是初始的state
actions：在state下可以做出的所有action
transition model：
对在任何state下执行可执行的action所产生的状态的描述
goal test：确认当前state是否是goal state
path cost function：与某一个path相关的cost
(2) dfs与bfs
上图就是dfs与bfs的具体算法流程
首先 从一个包含着initial state的frontier与空的explored set开始，从frontier中安照规则移除一个node(包含parent state，当前state，以及从parent到当前node的action)，拓展该node，将拓展得到的不在frontier中和explored set中的node加入frontier，重复上述操作，直到frontier为空或者到达目标state
区别就是frontier采用的数据结构不同，dfs是stack，bfs是queue
(3) greedy best-first search(gbs)与A*搜索
上面提到的dfs与bfs属于无信息搜索即盲目搜索
而贪心搜索属于有信息搜索也叫启发式搜索
具体定义为：
扩展最接近目标的节点的搜索算法，这个最接近的节点由启发式函数 h(n) 估计
如上图所示 在迷宫问题中的h(n)是到目标的manhattan距离
但是贪心搜索可能导致找到的是局部最优解，不是全局最优路径
而A*搜索则是使用g(n)与h(n)来计算path cost
相当于已经走过的cost和估计的cost之和
A*算法是最优的在如下所示的情况下：
要h(n)要满足不过分估计同时保持一致性
这一点我理解的不是很清楚