I find a definition of "exact neighborhood" (the book is online (\*1) Definition 1.5 on p.10) confusing.


Do I understand it right that neighborhood that contains the global optimum and no other local optimums/ma is what they call "exact neighborhood" in this book ?


Is this terminology accepted anywhere, or just in this book ?


(\*1)
<http://books.google.com/books?id=u1RmDoJqkF4C&pg=PA10&lr=&hl=iw&source=gbs_toc_r&cad=4#v=onepage&q&f=false>
Papadimitriou Steiglitz‏ Combinatorial optimization 


search in the book: definition 1.5 exact



definition of "exact neighborhood" [optimization]
It's important that you understand the definition of a neighborhood used in this book. This is definition 1.3 on page 7. $N$ is not a set but rather a function that maps a solution to the problem to a subset of the entire set of solutions. You can also speak of the neighborhood of a particular solution, s, with respect to $N$, which would be denoted $N(s)$. $N(s)$ is a subset of the set of all solutions. 


Your question makes it clear that you don't understand this definition, since you imply that $N$ is a set of solutions. 


An example might help. If you're familiar with the 2-opt heuristic for the traveling salesman problem, then "the 2-opt neighborhood" is an example of N, while "the set of tours that can be obtained from the tour T by two-opt moves" is N(T) with respect to the two-opt neighborhood. 


This definition makes sense in the context of a local search algorithm. Given a neighborhood N, and an initial solution $s^{0}$, the local search algorithm constructs a sequence of solutions $s^{1}$, $s^{2}$, $\ldots$, by iterating


$s^{n+1}=\arg \min N(s^{n})$


If the neighborhood $N$ is exact, and if the iteration eventually converges to a solution where $s^{n+1}=s^{n}$, then that solution will be globally optimal. 


