「LinとKernighanの方法」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
細 ("LinとKernighanの方法" を保護しました。 [edit=sysop:move=sysop])
 
1行目: 1行目:
−
'''【 りんかーにはんほう 】'''
+
'''【 りんとかーにはんのほうほう (Lin and Kernighan's algorithm) 】'''
  
−
巡回セールスマン問題に対する局所探索法の一つ．
+
[[巡回セールスマン問題]]に対する[[局所探索法]]のひとつ．
−
巡回路の枝たかだか<math>k </math>本を別の枝に置き換えることにより得られる解集合を
+
巡回路の枝高々<math>k</math>本を別の枝に置き換えることにより
−
<math>k</math>-opt近傍と呼ぶが，この近傍において<math>k </math>を可変にし，
+
得られる解集合を
 +
<math>k</math>-opt近傍と呼ぶ．
 +
この近傍において<math>k</math>を可変にし，
 
連鎖的な枝交換操作によって生成され得る解集合を近傍とする．
 
連鎖的な枝交換操作によって生成され得る解集合を近傍とする．
 
このような解は指数通りあるため，
 
このような解は指数通りあるため，
 
改善解を逃さぬように探索の候補を絞るために巧妙なルールが組み込まれている．
 
改善解を逃さぬように探索の候補を絞るために巧妙なルールが組み込まれている．
−
なお，上述の局所探索をLinとKernighanの方法と呼ぶことが多いが，
+
なお，
 +
上述の局所探索をLinとKernighanの方法と呼ぶことが多いが，
 
元論文は多スタート局所探索法の枠組みに基づいており，
 
元論文は多スタート局所探索法の枠組みに基づいており，
 
探索の集中化や効率化に対する種々の工夫も盛り込まれている．
 
探索の集中化や効率化に対する種々の工夫も盛り込まれている．

2007年9月20日 (木) 15:37時点における最新版

【 りんとかーにはんのほうほう (Lin and Kernighan's algorithm) 】

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

「https://orsj-ml.org/orwiki/wiki/index.php?title=LinとKernighanの方法&oldid=9447」から取得