03-状态空间搜索

状态空间搜索技术

图搜索策略

open表：当前未扩展结点

close表：已扩展结点

盲目搜索

不重排open表

1. 宽度优先：open表是队列
2. 深度优先：open表是栈
3. 等代价优先：根据代价决定加入队列的优先级，所有连接弧代价都相等即为宽度优先

启发式搜索

重排 open 表，即决定先扩展那个结点，或放弃哪一个结点扩展

1. A算法(有序搜索)：根据估计函数来重排open表

2. A*算法：理想的A算法最佳路径

   估价函数：已经付出的代价+估计还要付出的代价

3. 博弈树（己方与max，对方或min的与或树）

   1. 极大极小搜索：用宽度优先算法根据规定深度找出全部博弈树，为了使得自己利益最大化，从最底层结点倒推，就得使得己方max估价函数取值最大的节点，对方min估价函数取最小的节点
   2. $\alpha(max)-\beta(min)$剪枝搜索：深度优先，max确定下界，min确定上界，不同层的$\alpha(max)>=\beta(min)$就剪枝
      1. $\alpha$剪枝：先辈是$\alpha$
      2. $\beta$剪枝：先辈是$\beta$