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. 923
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 242