「K-opt法 (巡回セールスマン問題の)」の版間の差分
| 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) 法)は, 巡回セールスマン問題に対する代表的な近似解法である. | 巡回セールスマン問題に対する近似解法. 適当な巡回路から出発し, <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) 法)は, 巡回セールスマン問題に対する代表的な近似解法である. | ||
2007年7月16日 (月) 15:31時点における版
【けいおぷとほう (-opt)】
巡回セールスマン問題に対する近似解法. 適当な巡回路から出発し, 本の枝を, 巡回路が得られるように別の 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k \,} 本に置き換えたとき, 総距離が減少するなら置き換えを行うことによって巡回路を改善していく. を固定する場合には, 計算時間と解の精度から もしくは 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 3 \,} が選択される. を可変にして巡回路の改良が保証されるなら, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k \,} の値を増やしていく解法(可変 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k \,} -opt, リン・カーニハン (Lin--Kernighan) 法)は, 巡回セールスマン問題に対する代表的な近似解法である.
