Algorithms For Dummies

Presenting local search tricks

Local search tracks the current solution and moves to neighboring solutions one 

at a time until it finds a solution (or can’t improve on the present solution). It 

presents some key advantages when working on NP-hard problems because it

 

»

Is simple to devise and execute

 

»

Uses little memory and computer resources (but searches require running 

time)

 

»

Finds acceptable or even good problem solutions when starting from a 

less-than-perfect solution (neighboring solutions should create a path to the 

final solution)

---

CHAPTER 18

  Performing Local Search 

     343

You can see the problems that a local search can solve as a graph of interconnected 

solutions. The algorithm traverses the graph, moving from node to node looking 

for the node that satisfies the task requirements. Using this perspective, a local 

search takes advantage of graph exploration algorithms such as depth-first search 

(DFS) or breadth-first search (BFS), both discussed in Chapter 9.

Local search provides a viable way to find acceptable solutions to NP-hard prob-

lems. However, it can’t work properly without the right heuristic. Randomization 

can provide a good match with local search, and it helps by using