Neighborhood

From Glossary

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.


Views
Personal tools