| Item type |
SIG Technical Reports(1) |
| 公開日 |
2018-03-01 |
| タイトル |
|
|
タイトル |
Limited Discrepancy Searchによるフィードバック辺集合の探索 |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
神戸大学大学院工学研究科 |
| 著者所属 |
|
|
|
神戸大学大学院工学研究科 |
| 著者所属 |
|
|
|
神戸大学大学院工学研究科 |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Engineering, Kobe University |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Engineering, Kobe University |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Engineering, Kobe University |
| 著者名 |
兼本, 樹
山口, 一章
増田, 澄男
|
| 著者名(英) |
Itsuki, Kanemoto
Kazuaki, Yamaguchi
Sumio, Masuda
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
フィードバック辺集合問題や，その一般化である線形順序付け問題は古くから研究が行われている問題である．本稿では，分枝限定法に基づいて，有望な解を含むと思われる解空間を優先的に探索する Limited Discrepancy Search (LDS) という探索法を用いてフィードバック辺集合問題の解を探索するアルゴリズムを示し，その際のいくつかの工夫について述べる．また，計算機実験により，LDS を用いたときの振る舞いを，整数計画問題として定式化してソルバー （CPLEX） で解いた場合と比較する．頂点数 30，50，100，辺密度 0.1，0.5，1.0 のランダムグラフの入力計 45 通りに対して計算機実験を行い，半数以上の （特に頂点や辺の多い） 入力に対して，LDS が CPLEX より高速に良い解や最適解に到達することを示した． |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2018-AL-167,
号 10,
p. 1-6,
発行日 2018-03-01
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL18167010.pdf (311.4 kB)
