algorithmgraph-theorydepth-first-search

Depth First Search v.s. Greedy Best First Search

I am wondering under what settings can Depth First Search (DFS) equal to Greedy Best First Search? Is it possible?

Solution

  • A Greedy Best First Search algorithm chooses one node among the immediate children of the current node which is optimal based on some criteria.

    Let's say that criteria is max(node.val). In that case, at each node you do:

    next_node = curr_node.children[0]
for node in curr_node.children:
  if node.val > next_node.val:
    next_node = node
# add next_node to path and continue searching

    Now, you could implement this recursively or iteratively.

    A classic DFS, whether implemented recursively or iteratively, tries every path and that's different than the Greedy Best First Search, which only explores the path following the immediate best child.

    If you changed the DFS to look at every immediate child first and only go down the best found, it would produce the same results as the Greedy Best First Search. But if you think about it, this isn't DFS anymore. It's just a recursive Greedy Best First Search as we defined it at the beginning.