近傍#

読み: きんぼう
英名: Neighborhood

集合 \(A \subset \mathbb{R}^n\)，点 \(x \in \mathbb{R}^n\) について，ある \(\varepsilon > 0\) が存在して，点 \(x\) を中心とする開球 \(B(x,\varepsilon)=\{y \in \mathbb{R}^n \mid \|y-x\| < \varepsilon \}\) を集合 \(A\) が含んでいるとき，\(A\) を点 \(x\) における近傍という．即ち，点 \(x \in \mathbb{R}^n\) を含む任意の開集合を点 \(x\) における近傍という．

なお，離散最適化問題においても近傍の概念は用いられており，タブーサーチで用いられている近傍の中には，シフト近傍 [1] という近傍が存在する．例えばコストの総和が最小となるように \(n\) 個の仕事を \(m\) 人に割り当てる一般化割当問題の場合，割当 \(\pi\)（仕事集合から人集合への写像）に対するシフト近傍とは，\(\pi\) の一つの仕事の割当先を変更した \(\pi^\prime\) の集合となる．