| Item type |
SIG Technical Reports(1) |
| 公開日 |
2024-01-13 |
| タイトル |
|
|
タイトル |
ZDDを用いた分割統治法によるパス数え上げアルゴリズム |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
九州工業大学 |
| 著者所属 |
|
|
|
九州工業大学 |
| 著者所属 |
|
|
|
九州工業大学 |
| 著者所属 |
|
|
|
九州工業大学 |
| 著者所属 |
|
|
|
九州工業大学 |
| 著者所属(英) |
|
|
|
en |
|
|
Kyushu Institute of Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Kyushu Institute of Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Kyushu Institute of Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Kyushu Institute of Technology |
| 著者所属(英) |
|
|
|
en |
|
|
Kyushu Institute of Technology |
| 著者名 |
前田, 惠太
岩崎, 巧実
藤岡, 祐太
塩田, 拓海
斎藤, 寿樹
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
本研究では，無向グラフ G 上の始点 s から終点 t までの長さ l の s-t パスを数え上げる問題に対する分割統治法によるアルゴリズムの効率的な実装について議論する．この分割統治法に基づくアルゴリズムでは，s，t とは異なる頂点 v を経由する s-t パスの数を頂点 s から v へのパスの数と v から t までのパスの数をかけ合わせることで計算する．ただし，ここで s-v パスと v-t パスに共通の頂点を持たせてはいけない．一方，ゼロサプレス型二分決定グラフ (ZDD) は組合せ集合をコンパクトに表現することができるデータ構造で，組合せ集合における効率的な演算体型が数多く提供されている．また，ZDD を用いることで，各組合せに重みをもたせた組合せ多重集合を表現できることが知られている．本研究では，ZDD における組合せ多重集合の新たな演算である素集合結合演算を提案し，それを用いることで，分割統治法によるパスの数え上げアルゴリズムを提案する．分割統治法における 2 種類の分割方法によるアルゴリズムの実装方法について示し，それらの実装における効率性を計算機実験により示す． |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2024-AL-196,
号 2,
p. 1-8,
発行日 2024-01-13
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL24196002.pdf (2.6 MB)
