算法
(BFS,双向BFS) $O((LN)^5)$
假设每次决策数量是 $K$,那么如果直接BFS,最坏情况下的搜索空间是 $K^{10}$,非常大,所以会TLE或者MLE。
如果采用双向BFS,则可以把搜索空间降到 $2K^5$。在实际测试中只需 20ms 左右,剪枝效果很好。
BFS的扩展方式是:分别枚举在原字符串中使用替换规则的起点,和所使用的的替换规则。
时间复杂度
假设字符串长度是 $L$,替换规则一共有 $N$ 个,则:
在最坏情况下每次会从字符串的每个位置开始,使用全部的 $N$ 种替换规则,因此总共会有 $LN$ 种扩展方式,从起点和终点最多会分别扩展5步,因此总搜索空间是 $2(LN)^5$。
在BFS过程中,空间中的每个状态只会被遍历一次,因此时间复杂度是 $O((LN)^5)$。
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
const int N = 6;
int n;
string A, B;
string a[N], b[N];
int extend(queue<string>& q, unordered_map<string, int>&da, unordered_map<string, int>& db,
string a[N], string b[N])
{
int d = da[q.front()];
while (q.size() && da[q.front()] == d)
{
auto t = q.front();
q.pop();
for (int i = 0; i < n; i ++ )
for (int j = 0; j < t.size(); j ++ )
if (t.substr(j, a[i].size()) == a[i])
{
string r = t.substr(0, j) + b[i] + t.substr(j + a[i].size());
if (db.count(r)) return da[t] + db[r] + 1;
if (da.count(r)) continue;
da[r] = da[t] + 1;
q.push(r);
}
}
return 11;
}
int bfs()
{
if (A == B) return 0;
queue<string> qa, qb;
unordered_map<string, int> da, db;
qa.push(A), qb.push(B);
da[A] = db[B] = 0;
int step = 0;
while (qa.size() && qb.size())
{
int t;
if (qa.size() < qb.size()) t = extend(qa, da, db, a, b);
else t = extend(qb, db, da, b, a);
if (t <= 10) return t;
if ( ++ step == 10) return -1;
}
return -1;
}
int main()
{
cin >> A >> B;
while (cin >> a[n] >> b[n]) n ++ ;
int t = bfs();
if (t == -1) puts("NO ANSWER!");
else cout << t << endl;
return 0;
}
为什么每次要扩展一层
bfs一次扩展一层
不是很理解,如果不是每次扩展一层,并不是答案不对,而是会TLE,超时的数据在本地IDE跑出来是对的....到底是为啥呢?是因为有些状态重复扩展了吗?
不是扩展一层跟普通BFS有啥区别
因为有一次可能找不到最优解,一层一定能保证有最优解,视频里提到了
你好,我想问一个问题,假设从起点开始搜索时,A,B为两个状态,A->B通过的操作是C,那么从终点反向搜索B->A时的操作不应该是C的逆操作C’吗?为什么双向广搜从终点开始搜索用的操作还是C,不应该是C’吗?
两个搜索方向传的参数不一样
extend 函数中 判断为什么要判断 da[q.front()] == d
只拓展一层,同一层的节点的da相同(到起点距离相同)
代码里bfs部分的 if ( ++ step == 10) return -1;感觉没用到呀
也许这是样例的功劳
说明已经走了十步,但是还没找到可行解
没加可能会炸:
a b
a aa
bb b
当step大于10就说明已经至少扩展了10层,如果此时还没找到解,那么就输出NO Solution
所以这题的引出是为了强调双向BFS的用法把,毕竟真卡时间复杂度2 * 120 ^ 5也是爆掉了
赞同,可能数据本身也没有那么恶心hhh
同样听了y总的代码,然后自己从头开始打了一遍,并且从头到尾都注释了一下,感觉还比较清楚把
https://www.acwing.com/solution/content/61327/
希望大家批评指正
extend 那块,可以不用引用吗? 既然queue[HTML_REMOVED]传的都是指针
这里如果不引用的话,就会把要传递的queue或者unordered-map复制一份再传入,当规模较大就会导致效率低下,而且在函数中的改变不会在队列和map本身上生效
yxc老师,
for (int i = 0; i < t.size(); i ++ )
这行代码是不是容易出错?(
t.size()
好像不是int类型的)t.size()返回是size_t类型,也就是unsigned int类型, 最常见的错误是写成for(unsigned int i = n - 1; i >= 0; i–) 这样的话就死循环了。原因时unsigend 的0减1就变为正的最大了。https://stackoverflow.com/questions/2084949/comparison-operation-on-unsigned-and-signed-integers
推荐的写法应该是不要做 int 和 unsigned int的比较。int 和int比较。unsigned 和 unsigned比较。但是一般也正确。
对滴,在特别情况下
.size()
和int
整型变量比较时会出错,所以尽量保证式子的运算结果是正数,因为如果是负数,unsigned int
类型的变量会变成超大的正数。y总使用Java语言写这个代码逻辑相同,时间有一千多毫秒,超过了一秒还可以吗
$(LN)^5$时间复杂度不会炸吗?
双向BFS不能每次只扩展一个点:假如从一边A扩展到了某一中间点o,此时,若没有继续扩展这一层的点,而是从另一边B扩展的话,B也可能扩展到了这个点。;但是可能存在同层的点可以直接到B的同层的一个点,这样最短距离是要小1的
还是不理解为什么双向广搜出来的答案一定是最优解
已阅
yxcnb!!!
为什么在bfs的时候 终止条件是2个队列都不为空呢 为什么不是只要有一个队列不为空就继续搜下去呢
有一个为空说明从那个状态开始已经搜完所有状态却没有和第一个队列交集,说明无解,只有两个都不为空才继续搜
因为如果其中一个队列空了,说明已经变不成该队列中没出现过的字符串了。这时如果两个队列仍没出现交集,另一个队列继续搜完全没有意义。
我用string r = t.replace(j, a[i].size(), b[i]);替换y总那种拼接方法结果不行,为啥呢。。。
因为这样t也被修改了,应该写成r = t, r = r.replace(…)
我把y总的代码进行了详细地注释,可能更好理解一些
https://www.acwing.com/solution/content/41647/
如果有错误,请大家指正。
如果 if (db.count(state)) return da[t] + 1 + db[state]; 这里return 的值大于 10 了, 可以直接得到 “NO answer”的答案吧?
我也是这样想的
y总,如果A字符串和B字符串相等就会TLE啦,建议在拓展之前加上if(db.count(t)) return da[t] + db[t];,就可以
这道题目的数据不能太强,否则即使是双向BFS也一定会超时的。
好滴~
当时回复的时候卡了,就会提交很多次qaq,y总我不是故意的
没关系,删除评论之后对应的消息通知也会删掉,我这里不会收到重复通知的。
老师,时间复杂度第三行末尾那里写错了吧,应该是$2(LN)^5$ 吧
时间复杂度一般不考虑常数,$O(N)$ 和 $O(2N)$ 是相等的。
不是不是,老师我那个强调的是指数, 不是系数。
好滴,已更正。