# Comparing classical tree-search algorithms (BFS,DFS,A*,IDS) - when to use one or the other?

I have a question about classical tree-search algorithms as I will have an exam soon and this is the type of questions they might be asking. Although I know how to compare the complexities, optimality, and completeness, I would like to go a bit further than that and compare the sparseness of the tree, the branching factor, solution depth, etc. I would like to compare the algorithms (A*, BFS, DFS, IDS tree-search algorithms (i.e. without keeping a list of visited nodes)) pairwise and ask the question what would be the situation where one or the other would be preferred.

So far I have written down everything I can think of and I would like to know:

• Is what I have written down correct?
• Is there something I have missed for specific comparisons?
• Is there something I missed for all of them? I.e. some specific quality I did not think of?
• Something I struggled with was which algorithm to prefer if the tree is sparse/dense - I took an educated guess for most of them but I am uncertain of my answers. If anyone has any guidance in that part, it would be terrific.

I have also added some questions here and there. I realise this is a lot but I greatly appreciate any help - any hints are welcome as well.

# 1 DFS vs IDS

When to prefer DFS?

• If the solutions are frequent deeper in the tree

When to prefer IDS?

• If you need at least one of them: optimality, completeness
• If the tree is infinite (as DFS might get stuck)
• If the solution is located in the upper part of the tree
• If the solution is located deep in the tree and they are infrequent

Is there anything that can be said about sparseness/denseness for IDS here?

# 2 DFS vs BFS

When to prefer DFS?

• If the tree has a large branching factor (BFS gets slow with wide trees)
• If solutions and frequent and located deep in the tree
• If there is a limit to how much memory can be used

When to prefer BFS?

• If at least one of the two is required: optimality, completeness
• If the tree is infinite
• If the maximum depth is much larger than the branching factor
• If you know that the solution is now far from the root of the tree
• If solutions are rare and located deep in the tree
• When the tree is sparse (unsure why)

# 3 DFS vs A*

When to prefer DFS?

• If the heuristic of A* is poor
• If the goal is optimality and the A* heuristic is not admissible
• If solutions are frequent and located deep in the tree

When to prefer A*?

• If the tree is infinite
• If the tree is dense (unsure why)
• In general blind search is slower than heuristic search, therefore for a good enough heuristic, A* should be prefered

Is there anything that can be said about the branching factor here?

# 4 BFS vs A*

When to prefer A*?

• If memory space is limited
• If the tree has a high branching factor
• If the tree is dense
• Although the complexity of queue is slightly better than that of priority queue, A*'s time complexity is usually better than BFS's time complexity with a good enough heuristic

When to prefer BFS?

• If the tree has a low branching factor
• If the tree is dense
• If the heuristic is poor
• If the heuristic is not admissible and optimality is required

Is there anything that can be said about frequent/infrequent solutions here?

# 5 BFS vs IDS

When to prefer IDS?

• When a lower space complexity is required and somewhat lower time complexity is acceptable

When to prefer BFS?

• If the solution is in the upper part of the tree as it is less costly to generate the nodes once

I am a bit lost here - is there anything else that can be said about finiteness, denseness, frequency of solutions of the graph?

# 6 A* vs IDS

When to prefer IDS?

• When the A* algorithm has a poor heuristic
• When optimality is required and the A* heuristic is not admissible
• If there are limitations to the amount of memory available

When to prefer A*?

• In general blind search is slower than heuristic search, therefore for a good enough heuristic, A* should be prefered