Tabu Searchによる半順序の系列分割問題

スポンサーリンク

概要

論文の詳細を見る
グラフ分割問題の特別なケースとして、グラフの頂点番号を1からnまで連続的な数とする一列化グラフに対して、各ブロックの頂点番号の連続性を保持するKernighanの系列分割問題がある。しかし、多くのシステムの構造はより一般的な無閉路有向グラフで構成されており、その上での系列分割について検討する必要がある。前回の発表等ので、この無閉路有向グラフの系列分割問題に問題を拡張し、その厳密解法を与えた。本稿では巨大な問題をより高速に解くために、無閉路有向グラフの最適系列分割問題に対して、Tabu Searchによる近似解法の適用を試みる。TabuSearchはFred Gloverによって提案された局所探索法の変形である。その大まかな戦略は探索過程で以前に探索した解に再び戻る解のサイクリングをタブーリストを設けることによって禁止する処置をとることである。
一般社団法人情報処理学会の論文
1994-09-20

著者

関連論文

もっと見る

スポンサーリンク