BFS versus DFS for random targets in ordered trees
arxiv(2024)
摘要
Consider a search from the root of an ordered tree with n edges to some
target node at a fixed distance ℓ from that root. We compare the average
time complexity of the breadth-first search (BFS) and depth-first search (DFS)
algorithms, when the target node is selected uniformly at random among all
nodes at level ℓ in the ordered trees with n edges. Intuition suggests
that BFS should have better average performance when ℓ is small, while DFS
must have an advantage when ℓ is large. But where exactly is the
threshold, as a function of n, and is it unique? We obtain explicit formulas
for the expected number of steps of both BFS and DFS, by using results on the
occupation measure of Brownian excursions, as well as a combinatorial proof of
an identity related to lattice paths. This allows us to show that there exists
a unique constant λ≈ 0.789004, such that in expectation BFS is
asymptotically faster than DFS if and only if ℓ≤λ√(n).
Furthermore, we find the asymptotic average time complexity of BFS in the given
setting for any class of Galtonx2013Watson trees, including binary
trees and ordered trees. Finally, we introduce the truncated DFS algorithm,
which performs better than both BFS and DFS when ℓ is known in advance,
and we find a formula evaluating the average time complexity of this algorithm.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要