Algorithms For Dummies

Knowing the neighborhood

Local search algorithms iteratively improve from a starting solution, moving one 

step at a time through neighboring solutions until they can’t improve the solution 

any further. Because local search algorithms are as simple and intuitive as greedy 

algorithms, designing a local search approach to an algorithmic problem is not 

difficult. The key is defining the correct procedure:

1. 

Start with an existing solution (usually a random solution or a solution from 

another algorithm).

2. 

Search for a set of possible new solutions within the current solution’s 

neighborhood, which constitutes the candidates’ list.

---

CHAPTER 18