DFSBFS

DFSBFS is a class of hybrid graph search algorithms that blends depth-first search (DFS) and breadth-first search (BFS) techniques. It aims to combine the memory efficiency of DFS with the systematic, level-by-level expansion that characterizes BFS.

The general approach is to perform DFS-style exploration but to switch to BFS when certain criteria are met, such as the size of the current frontier, a maximum search depth, or a time budget. In doing so, the algorithm expands nodes at the current depth in a breadth-first fashion, rather than continuing deeper along a single path. After finishing the BFS expansion at that level, it may resume DFS to probe other branches, and the process repeats.

Variants of DFSBFS include fixed-switch strategies, where switching points are predetermined, and adaptive or windowed strategies, where switching is guided by the state of the search. The method is designed to provide a middle ground between DFS and BFS, trading some memory usage for improved completeness and, under certain switching rules, closer to optimal solutions than pure DFS.

Properties: Completeness and optimality depend on the switching policy; memory usage typically lies between pure DFS and BFS. The approach is used in AI search, planning, pathfinding, and puzzle solving, especially in domains where the search space is large and memory is at a premium.

See also: Depth-first search, Breadth-first search, Iterative deepening, Depth-first branch and bound, Memory-bounded search.