排除連鎖法

【 はいじょれんさほう (ejection chain) 】

基本的な近傍操作を連鎖的に行うことによって生成され得る解集合を 近傍とすることで， 近傍を拡大し， 局所探索の性能向上を図る手法の総称． このような解全てを近傍に含めると，連鎖の長さに対して指数的に 近傍が大きくなってしまうため， 改善解を逃さぬように探索の候補を絞るためのルールを， 問題構造を利用してうまく設計する必要がある． 成功例として，巡回セールスマン問題に対するLinとKernighanの方法などがある．