「K-opt法 (巡回セールスマン問題の)」の版間の差分
ナビゲーションに移動
検索に移動
Albeit-Kun (トーク | 投稿記録) |
|||
| (3人の利用者による、間の3版が非表示) | |||
| 1行目: | 1行目: | ||
'''【けいおぷとほう (<math>k \,</math>-opt)】''' | '''【けいおぷとほう (<math>k \,</math>-opt)】''' | ||
| + | 巡回セールスマン問題に対する近似解法. 適当な巡回路から出発し, <math>k \,</math> 本の枝を, 巡回路が得られるように別の <math>k \,</math> 本に置き換えたとき, 総距離が減少するなら置き換えを行うことによって巡回路を改善していく. <math>k \,</math> を固定する場合には, 計算時間と解の精度から<math>k=2 \,</math> もしくは <math>3 \,</math> が選択される. <math>k \,</math> を可変にして巡回路の改良が保証されるなら, <math>k \,</math> の値を増やしていく解法(可変 <math>k \,</math>-opt, リン・カーニハン (Lin--Kernighan) 法)は, 巡回セールスマン問題に対する代表的な近似解法である. | ||
| − | + | [[Category:グラフ･ネットワーク|けいおぷとほう]] | |
2008年11月5日 (水) 16:40時点における最新版
【けいおぷとほう (-opt)】
巡回セールスマン問題に対する近似解法. 適当な巡回路から出発し, 本の枝を, 巡回路が得られるように別の 本に置き換えたとき, 総距離が減少するなら置き換えを行うことによって巡回路を改善していく. を固定する場合には, 計算時間と解の精度から もしくは が選択される. を可変にして巡回路の改良が保証されるなら, の値を増やしていく解法(可変 -opt, リン・カーニハン (Lin--Kernighan) 法)は, 巡回セールスマン問題に対する代表的な近似解法である.
