Algorithms For Dummies

 Challenging Difficult Problems

 

»

Choose a heuristic or a meta-heuristic (a heuristic that helps you determine 

which heuristic to use) that works well for your problem in practice. However, 

it has no theoretical guarantee and tends to be empiric.

Understanding Local Search

Local search is a general approach to solving problems that comprises a large range 

of algorithms, which will help you escape the exponential complexities of many 

NP problems. A local search starts from an imperfect problem solution and moves 

away  from  it,  a  step  at  a  time.  It  determines  the  viability  of  nearby  solutions, 

potentially leading to a perfect solution, based on random choice or an astute 

heuristic (no exact method is involved).

A  heuristic is an educated guess about a solution, such as a rule of thumb that 

points to the direction of a desired outcome but can’t tell exactly how to reach it. 

It’s like being lost in an unknown city and having people tell you to go a certain 

way to reach your hotel (but without precise instructions) or just how far you are 

from  it.  Some  local  search  solutions  use  heuristics,  so  you  find  them  in  this 

 chapter. Chapter 20 delves into the full details of using heuristics to perform prac-

tical tasks.

You have no guarantee that a local search will arrive at a problem solution, but 

your chances do improve from the starting point when you provide enough time 

for the search to run its computations. It stops only after it can’t find any further 

way to improve the solution it has reached.