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