What is the difference between local search and global (or complete) search algorithms?


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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.