定义:搜索效率 = 总答案数 / 搜索算法遍历节点的总次数。(0 < 搜索效率 < 1)
搜索效率可以直接反映出 IO 部分 / 算法部分 的时间比例。由于 IO 部分常数较大,需要将搜索效率乘上一个大常数才能得到实际时间比例。
当搜索效率为 x 时, IO 部分 / 算法部分 的时间比例为 20x 。(魔法少女第一定理)
在均匀随机图上面随机走几步,回到原点的概率是 1/n (n 为图的点数)。也就是说,朴素 DFS 算法在均匀随机图上的搜索效率为 1/n。
利用双向搜索(类似密码学上的 meet in the middle 技巧)可以把搜索效率提升到 1/sqrt(n)。
对应到题目场景,如果在图上随机走 7 步回到原点的概率是 x,那么算法的搜索效率往往可以达到 sqrt(x)。(魔法少女第二定理)
在具有特殊特征的图上,搜索效率将非常高。搜索效率越高,高级算法相对于朴素算法的优势就越小(第二定理),算法部分时间在总运行时间内的占比就会越小(第一定理)。
在完全图上,搜索效率可以直接达到 1;在具有局域性的图上(例如社交图),图的维度为 d 且这个值较小时,搜索效率趋近于 (1/d)^(7/2) 。(魔法少女第三定理)
(注:第三定理中图的维度的定义参考了 Wolfram 的理论物理模型:https://writings.stephenwolfram.com/2020/04/finally-we-may-have-a-path-to-the-fundamental-theory-of-physics-and-its-beautiful/ )(章节:The Dimensionality of Space)


搜索过的点都被剪枝了,即使一个完全图搜索到后面也变得稀疏了。所以可以搜索前期先用高级算法,后期用朴素算法?或者说,搜索的图因为剪枝,所以是图动态的,每次搜索前先统计一下要搜索的局部看看是否稀疏。