What is the difference between local search and global (or complete) search algorithms?
$\begingroup$
$\endgroup$
0
asked Sep 23, 2017 at 9:19
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
The difference between a local search algorithm (like beam search) and a complete search algorithm (like A*) is, for the most part, small.
Local search algorithms will not always find the correct or optimal solution, if one exists. For example, with beam search (excluding an infinite beam width), it sacrifices completeness for greater efficiency by ordering partial solutions by some heuristic predicting how close a partial solution is to a complete one. Beam search is a greedy algorithm.
Complete search algorithms will always find the correct or optimal solution if there is one, given enough time. An algorithm like A* uses heuristics to prune the tree as it goes along, but it will not converge to a sub-optimal solution. In a lot of practical cases, this is inefficient, but how much so is problem dependent.
