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