LinとKernighanの方法

【 りんとかーにはんのほうほう (Lin and Kernighan's algorithm) 】

巡回セールスマン問題に対する局所探索法のひとつ． 巡回路の枝高々$k$本を別の枝に置き換えることにより 得られる解集合を $k$-opt近傍と呼ぶ． この近傍において$k$を可変にし， 連鎖的な枝交換操作によって生成され得る解集合を近傍とする． このような解は指数通りあるため， 改善解を逃さぬように探索の候補を絞るために巧妙なルールが組み込まれている． なお， 上述の局所探索をLinとKernighanの方法と呼ぶことが多いが， 元論文は多スタート局所探索法の枠組みに基づいており， 探索の集中化や効率化に対する種々の工夫も盛り込まれている．