近傍

近傍#

  • 読み: きんぼう

  • 英名: 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\) の集合となる.

関連

参考文献

[1]

柳浦睦憲 and 茨木俊秀. 組合せ最適化 ―メタ戦略を中心として― (経営科学のニューフロンティア 2). 朝倉書店, 2001.