# Neighborhood

Jump to: navigation, search

For a normed space, the neighborhood of a point, $LaTeX: x,$ is the open ball centered at $LaTeX: \textstyle x: \left \{y: ||y-x|| < e \right \},$ where $LaTeX: e > 0.$ The closed ball, with $LaTeX: \textstyle ||y-x|| \le e,$ is also a neighborhood. The usual notation (in this glossary) is $LaTeX: N_e(x),$ and context dictates whether it is open or closed. This extends to the neighborhood of a set $LaTeX: S$ by taking the union; equivalently, $LaTeX: \textstyle N_e[S] = \left \{y: ||y-x|| \le e \mbox{ for some } x \in S \right \}.$

In integer programming, the neighborhood could mean integer-valued neighbors of the form $LaTeX: \textstyle |x-x^*| \le 1.$ In a combinatorial program, where variables are binary, integer-valued neighbors comprise all members of $LaTeX: \textstyle \{0,1\}^n.$ In this case the neighborhood is defined relative to some subset of binary variables reachable by some operation that depends on the problem. This is what is generally meant by a neighborhood in heuristic search in general, and simulated annealing or tabu search in particular, where a move is defined in terms of neighbors. In that context, a neighborhood could be as simple as complementing the value of one variable, as deletions or additions in a knapsack problem, or it could be more complex, like a [1]-Opt neighbor of a TSP tour.