Algorithms For Dummies

 

»

Random sampling: Generating solutions to start

 

»

Random walk: Picking a random solution that neighbors the current one. 

(You find more on random walks in the “Solving 2-SAT using randomization” 

section, later in this chapter.)

Randomization isn’t the only heuristic available. A local search can rely on a more 

reasoned exploration of solutions using an objective function to get directions (as 

in hill-climbing optimization) and avoid the trap of so-so solutions (as in simulated 

annealing and Tabu Search). An objective function is a computation that can assess 

the  quality  of  your  solution  by  outputting  a  score  number.  If  you  need  higher 

scores in hill climbing, you have a maximization problem; if you are looking for 

smaller score numbers, you have a problem of minimization.