研究・知財戦略機構 学内フォーマット集
組み合わせ最適化における指数サイズ・多項式時間近傍の設計
| 研究課題名 | 組み合わせ最適化における指数サイズ・多項式時間近傍の設計 | ||
| 研究種目等 | 特定領域研究 （計画研究） | ||
| 研究概要 | （研究実施計画） 近傍内の最適化の技法： 引き続き，グラフ及びハイパーグラフの分割アルゴリズムについて，理論，実装の両面から研究を進めていく。分割概念としては，木分割と分枝分割の両方を対象とする。理論面では，グラフの種々のクラスについての研究を進める。グラフのクラスによって木分割の方が容易であったり，またその逆であったりするので，一方についての効率的アルゴリズムが知られており，他方については未解決であるようなグラフクラスを中心に研究を進める。実装面からは，平面グラフに対する理論的に良いアルゴリズムが得られているので，これに実装上の工夫を加えて，大規模問題での使用に耐えるようにする。 動的計画法の実装法については，巨大な表を扱う際の表と計算の分割法について，引き続き研究を進める。これは，逐次的なアルゴリズムにおいても必要な要素であるが，FPGAを用いた実装においてはさらに重要である。 具体的な問題への巨大近傍アプローチの適用： 巡回セールスマン問題：ベンチマークライブラリであるTSPLIB唯一の未解決インスタンスPLA85900への挑戦を継続して進める。これまでのアプローチでは，初期解（複数）の生成のために，Lin-Kerningham手法に基づいたHelsgaunのTSPソルバーに大きく依存していたが，Lin-Kerningham手法に替わる新たに設計した巨大近傍手法によってこれを置き換えていく。 集合被覆問題：まず基本的な巨大近傍アルゴリズムの実装が完成し，大規模な問題に対して既存手法との比較実験を行う。そのなかで，さらなる改良を目指していく。 クリーク被覆問題：まず基本的な巨大近傍アルゴリズムを実装し，回路テストパターン圧縮問題から派生するインスタンスについての実験が完了して，それ以外の応用について開拓する。必要に応じて，応用分野に特化した理論と技法の構築を行う。 近傍内最適化アルゴリズムのFPGA化： 巡回セールスマン問題を対象とした動的計画法のFPGA化をおこなう。まず，素朴な実装から始め，上で述べた表の効率的構成法などを組み込んでいく。 |
||
| 研究者 | 所属 | 職 | 氏名 |
| 理工学部 | 教授 | 玉木久夫 | |
| 補助金額（千円） ※直接経費のみ |
3,100 | ||
| 研究期間 | 2004.4～2008.3 | ||
| リンク | |||