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
