K-opt法 (巡回セールスマン問題の)

【けいおぷとほう ($k\,$-opt)】

巡回セールスマン問題に対する近似解法. 適当な巡回路から出発し, $k\,$ 本の枝を, 巡回路が得られるように別の $k\,$ 本に置き換えたとき, 総距離が減少するなら置き換えを行うことによって巡回路を改善していく. $k\,$ を固定する場合には, 計算時間と解の精度から$k=2\,$ もしくは $3\,$ が選択される. $k\,$ を可変にして巡回路の改良が保証されるなら, $k\,$ の値を増やしていく解法(可変 $k\,$-opt, リン・カーニハン (Lin--Kernighan) 法)は, 巡回セールスマン問題に対する代表的な近似解法である.