「排除連鎖法」の版間の差分
ナビゲーションに移動
検索に移動
細 ("排除連鎖法" を保護しました。 [edit=sysop:move=sysop]) |
|||
| 2行目: | 2行目: | ||
基本的な近傍操作を連鎖的に行うことによって生成され得る解集合を | 基本的な近傍操作を連鎖的に行うことによって生成され得る解集合を | ||
| − | + | 近傍とすることで， | |
| + | 近傍を拡大し， | ||
| + | 局所探索の性能向上を図る手法の総称． | ||
このような解全てを近傍に含めると，連鎖の長さに対して指数的に | このような解全てを近傍に含めると，連鎖の長さに対して指数的に | ||
近傍が大きくなってしまうため， | 近傍が大きくなってしまうため， | ||
改善解を逃さぬように探索の候補を絞るためのルールを， | 改善解を逃さぬように探索の候補を絞るためのルールを， | ||
問題構造を利用してうまく設計する必要がある． | 問題構造を利用してうまく設計する必要がある． | ||
| − | + | 成功例として，[[巡回セールスマン問題]]に対する[[LinとKernighanの方法]]などがある． | |
2007年9月19日 (水) 22:16時点における最新版
【 はいじょれんさほう (ejection chain) 】
基本的な近傍操作を連鎖的に行うことによって生成され得る解集合を 近傍とすることで， 近傍を拡大し， 局所探索の性能向上を図る手法の総称． このような解全てを近傍に含めると，連鎖の長さに対して指数的に 近傍が大きくなってしまうため， 改善解を逃さぬように探索の候補を絞るためのルールを， 問題構造を利用してうまく設計する必要がある． 成功例として，巡回セールスマン問題に対するLinとKernighanの方法などがある．