这个类似BFS/DFS/IDDFS的算法有名称吗？

Question

从本质上讲,它是一种深度优先搜索,在某个深度或成本停止.例如,它可以DFS来自源的10个边缘内的所有节点,然后是20个,然后是30个.不同之处在于,不是在每次迭代后从头开始DFS,而是存储搜索区域的"周长"(列表节点)当搜索的每次迭代达到其极限时.

在下一次迭代中,我循环遍历周边上的所有节点,从每个节点执行DFS,再次停止到固定深度/成本,再次记录搜索区域的周界以便从下一次迭代开始.

我这样做的原因是因为我的图形(它是一棵树)被分成一组逻辑"块",每个逻辑"块"必须在它的子块开始被探索之前被完全探索.有大量的节点,但只有少量的块; 我本质上是在做一个大块的BFS,每个单独的块(包含大量的单个节点)都由它自己的mini-DFS完全探索.

现在,我只是在现场彻底解决了我的问题,而且确实如此,但文献中有这样的东西吗？我还没有找到任何东西,但我确信其他人之前已经做过这件事,并且正确分析了它的性能,渐近行为,缺点,错误等等.在这种情况下,我想知道它.

Answer 1

我现在不知道这种混合类型的名称。我也用过类似的东西，但我不认为它使用得很频繁并且有名字。通常，其他算法更有意义：

如果你想分块缓慢推进，为什么不使用 BFS？

通常 DFS 是首选，因为在那里您可以获得完整的跟踪。此外，进行迭代加深 DFS 比您的算法更简单，只消耗两倍的时间，并且需要更少的内存。