预告：我用两年写的新书《算法竞赛》，已于2022年2月交给清华大学出版社，预计于2022年7月出版。《算法竞赛》是一本“大全”，内容覆盖“基础-中级-高级”，篇幅700页左右。部分知识点的草稿已经在本博客发表。本篇博客节选自新书《算法竞赛》的“3.2.1 BFS判重”。
文章目录
- 1. map判重
- 2. set判重
?? 判重，即判断当前状态是否以前已经处理过。如果已经处理过，就不用再处理了，从这个角度看，判重是一种 剪枝技术。
?? 判重常常应用在BFS中，BFS剪枝的题目很多需要判重。
?? BFS的原理是逐步扩展下一层，把扩展出的下一层点放进队列中处理。在处理上一层的同时，把下一层的点放到队列的尾部。在任意时刻，队列中只包含相邻两层的点。如果这些点都不同，只能把所有点放进队列。如果这些点有相同的，那么相同的点只处理一次就够了，其他相同的点不用重复处理，此时需要判重。
?? 下面的真题是BFS判重。
2017年蓝桥杯省赛真题
跳蚱蜢 https://www.lanqiao.cn/problems/642/learning/
题目描述：有9只盘子，排成1个圆圈。其中8只盘子内装着8只蚱蜢，有一个是空盘。
把这些蚱蜢顺时针编号为 1~8。每只蚱蜢都可以跳到相邻的空盘中，也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。
请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列，并且保持空盘的位置不变（也就是1-8换位，2-7换位,…），至少要经过多少次跳跃？
?? 这是一道八数码问题，八数码是经典的BFS问题。
?? 本题首先用了“化圆为线”的技巧。直接让蚱蜢跳到空盘有点麻烦，因为有很多蚱蜢在跳。如果反过来看，让空盘跳，跳到蚱蜢的位置，就简单多了，只有一个空盘在跳。题目给的是一个圆圈，不好处理，可以“化圆为线”。把空盘看成0，那么有9个数字{0,1,2,3,4,5,6,7,8}，一个圆圈上的9个数字，拉直成了一条线上的9个数字。这就是八数码问题，八数码有9个数字{0,1,2,3,4,5,6,7,8}，它有9！=362880种排列，不算多。
?? 本题的初始状态是“012345678”，终止状态是“087654321”。从初始状态跳一次，下一状态有4种情况，如图所示。
【搜索专题|搜索中的判重（以BFS为例）】
文章图片
?? 用BFS扩展每一层。每一层就是蚱蜢跳了一次，扩展到某一层时发现终点“087654321”，这一层的深度就是蚱蜢跳跃的次数。
?? 所以，八数码问题实际是一个最短路径问题，用BFS最合适。
?? 这题如果写个裸的BFS，能运行出来吗？第1步到第2步，有4种跳法；第2步到第3步，有 4 2 4^2 42种；…；第20步，有 4 20 4^{20} 420 = 1万亿种。
?? 必须判重，判断有没有重复跳，如果跳到一个曾经出现过的情况，就不用往下跳了。一共只有9！= 362880种情况。代码的复杂度是多少？在每一层，能扩展出最少4种、最多362880种情况，最后算出的答案是20层，那么最多算20*362880 = 7,257,600次。在下面的C++代码中统计实际的计算次数，是1451452次。
?? 如何判重？用STL的map、set判重，效率都很好。
?? 另外有一种数学方法叫康托判重（康托判重的详细讲解，参考《算法竞赛入门到进阶》，清华大学出版社，罗勇军，郭卫斌著，“4.3.2 八数码问题”。），竞赛时一般不用。
?? 下面是“跳蚱蜢”的代码，有map和set两种判重方法。请自己了解STL map和set的概念。
1. map判重
#include
using namespace std;
struct node{
node(){}
node(string ss, int tt){s = ss, t = tt;
}
string s;
int t;
};
//(1) map
map, bool> mp;
queue q;
void solve(){
while(!q.empty()){
node now = q.front();
q.pop();
string s = now.s;
int step = now.t;
if(s == "087654321"){ cout<< 2. set判重
#include
using namespace std;
struct node{
node(){}
node(string ss, int tt){s = ss, t = tt;
}
string s;
int t;
};
//(2) set
set> visited;
//记录已经搜索过的状态
queue q;
void solve(){
while(!q.empty()){
node now = q.front();
q.pop();
string s = now.s;
int step = now.t;
if(s == "087654321"){ cout<< 推荐阅读
- 蓝桥杯往届真题详解|题目 2599: 蓝桥杯2020年第十一届国赛真题-天干地支
- 洛谷|P1923 【深基9.例4】求第 k 小的数
- Leetcode|Leetcode70-爬楼梯(C语言)
- 剑指offer进阶|剑指offer103（最少的硬币数目）
- 剑指offer进阶|剑指offer85（生成匹配的括号）
- 蓝桥杯|蓝桥杯——乳草的入侵
- #|算法Day6（广度优先搜索——最短路径问题）
- 论文解读|Query-Efficient Hard-label Black-box Attack: An Optimization-based Approach论文解读
- leetcode|《九日集训》(第九讲) 简单递归