广度优先搜索
lupengheyyds · · 个人记录
一、适用情景
由于是对搜索数的层序遍历，他适合求解层数较浅的搜索。所以他要维护一种解的单调性而不是深搜的连续性
洪泛法
也就是这样：
走地图
也就是在地图上行走的最优问题。
但一般不改变图的样子，这样便只需要存储当前位置答案及相关信息，而不需要存储整个地图。对于地图确实会变化的，可以适用状态压缩，将地图压进队列中的每个状态。
且与状压DP相比，他更适合解决复杂的地图。
这类广搜的精髓在于其状态设计与处理，有以下一个注意点：
- 用统一的不重复的方法进行表示，占据多个位置时应用其中一个位置代表
- 提前处理好移动时的坐标参数变化量，最好相对相邻。
- 判断是否合法一定要单独写成一个函数
- 搜索与数据结构的代码
二、解集排列形式
1.队列
仅仅适用于步数及没走一步答案更新（边权）都相同的情景。
2.双端队列
适用于边权仅为0或1的情况。
3.优先队列
适用于边权全为非负的情况。
4.备注
对于边权有正有负，飘忽不定的情况，广搜的单调性难以维护，此时只能把地图全部遍历一遍，用深搜广搜都一样了。
三、优化
双向搜索
于深搜一样，起点与终点同时进行，每次各扩展一层，当一个状态同时被搜索到，说明相遇了，合并答案就行。
启发式广搜
让优先队列以估价值+当前值进行排序，与其他启发式搜索一样，其估价值必须小于等于实际值。
注意，因为估价函数的影响，最终的答案为第一次出队列而非第一次入队列。
相比于迭代加深启发式搜索的预知不可能，启发式广搜在倾向于选择更可能。