LinとKernighanの方法のソースを表示
←
LinとKernighanの方法
ナビゲーションに移動
検索に移動
あなたには「このページの編集」を行う権限がありません。理由は以下の通りです:
この操作は、以下のグループに属する利用者のみが実行できます:
登録利用者
。
このページは編集や他の操作ができないように保護されています。
このページのソースの閲覧やコピーができます。
'''【 りんとかーにはんのほうほう (Lin and Kernighan's algorithm) 】''' [[巡回セールスマン問題]]に対する[[局所探索法]]のひとつ. 巡回路の枝高々<math>k</math>本を別の枝に置き換えることにより 得られる解集合を <math>k</math>-opt近傍と呼ぶ. この近傍において<math>k</math>を可変にし, 連鎖的な枝交換操作によって生成され得る解集合を近傍とする. このような解は指数通りあるため, 改善解を逃さぬように探索の候補を絞るために巧妙なルールが組み込まれている. なお, 上述の局所探索をLinとKernighanの方法と呼ぶことが多いが, 元論文は多スタート局所探索法の枠組みに基づいており, 探索の集中化や効率化に対する種々の工夫も盛り込まれている.
LinとKernighanの方法
に戻る。
案内メニュー
個人用ツール
ログイン
名前空間
ページ
議論
変種
表示
閲覧
ソースを表示
履歴表示
その他
検索
案内
メインページ
コミュニティ・ポータル
最近の出来事
最近の更新
おまかせ表示
ヘルプ
ORWikiへのお問い合わせ
OR学会HP
OR学会アーカイブ集
ツール
リンク元
関連ページの更新状況
特別ページ
ページ情報