How do I choose the search algorithm for a particular task? Which criteria should I take into account?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The choice of the most appropriate search algorithm for a particular task is often based (but not exclusively) on its time complexity, space complexity, termination (if the algorithm always halts), optimality guarantees (if the algorithm is guaranteed to find the optimal solution), available implementations (as software libraries) and (if known) the actual performance (for such particular task). There are algorithms that have the same time or space complexities, but that, in practice, have different performance, which also depends on the problem being solved and implementations (which might or not be optimised).
For example, consider a search tree where you have a finite number of nodes and paths. Suppose that solutions lie at the leaves of this tree and that you are interested in one solution, but not necessarily the optimal one. In that case, in practice, DFS might find solutions faster than BFS, because of its nature and the task being solved. However, in the case you have a tree with infinite-length paths, then DFS might not terminate. In that case, proceeding layer by layer (BFS) might be a more appropriate strategy.