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

提供: ORWiki
2007年7月12日 (木) 00:39時点における122.17.2.240 (トーク)による版 (新しいページ: ''''【けいおぷとほう ($k$-opt)】''' 巡回セールスマン問題に対する近似解法. 適当な巡回路から出発し, $k$ 本の枝を, 巡回路が得られ...')
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

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

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