ダウンロード数: 123
このアイテムのファイル:
| ファイル | 記述 | サイズ | フォーマット | |
|---|---|---|---|---|
| IEICE_tec.rep_COMP97-69.pdf | 2.64 MB | Adobe PDF | 見る/開く |
| タイトル: | 部分最適化問題の完全性 |
| その他のタイトル: | On the Completeness of Partial Optimiziation Problems |
| 著者: | 宮崎, 修一   https://orcid.org/0000-0003-0369-1970 (unconfirmed)岩間, 一雄  |
| 著者名の別形: | Miyazaki, Shuichi Iwama, Kazuo |
| キーワード: | 最適化問題 部分最適化問題 部分MAXSAT 完全性 optimization problems partial optimization problems partial MAXSAT completeness |
| 発行日: | 14-Nov-1997 |
| 出版者: | 電子情報通信学会 |
| 誌名: | 電子情報通信学会技術研究報告 |
| 巻: | 97 |
| 号: | 375 |
| 開始ページ: | 73 |
| 終了ページ: | 79 |
| 論文番号: | COMP97-69 |
| 抄録: | 部分MAXSATは, MAXSATを一般化した組合せ最適化問題であり, スケジュ-ル問題等の現実社会に則した組合せ最適化問題を模倣する能力を持っている.また, 部分MAXSATは, 項の重みづけを施すことにより, 従来のMAXSATアルゴリズムを用いて, 効率良く解けることが実験によって示されている.このように, 部分MAXSATは有用な問題であるが, どのような問題を模倣することができるかを理論的に明らかにする必要がある.本論文では, 部分MAXSATの組合せ最適化問題のクラスでの完全性を示すことにより, 部分MAXSATが幅広い最適化問題を模倣可能であることを示す.また, 他の組合せ最適化問題に対応する部分最適化問題の完全性も示す. Partial NIAXSAT (PMSAT) is a generalization of MAXSAT and has flexibility to simulate general combinatorial optimization problems, such as scheduling problems. However, it is shown empirically that it can be solved efficiently by local search algorithm for MAXSAT using weighting strategy. In this paper, we show the completeness of PMSAT and other partial optimization problems in order to demonstrate their usefulness. |
| 著作権等: | © 1997 電子情報通信学会(IEICE) |
| URI: | http://hdl.handle.net/2433/227136 |
| 関連リンク: | http://db.ieice.org/gakkai/show.php?id=95218 |
| 出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。