横断を用いたZDD上のBlockingの探索

• Item type: SIG Technical Reports(1)
• 公開日: 2024-05-01
• タイトル: 横断を用いたZDD上のBlockingの探索
• タイトル / 言語: en
• タイトル: Finding Blocking on ZDD with Hitting Set
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 高知工科大学情報学群
• 著者所属: 高知工科大学情報学群
• 著者所属(英): en
• 著者所属(英): School of Information, Kochi University of Technology
• 著者所属(英): en
• 著者所属(英): School of Information, Kochi University of Technology
• 著者名: 原田, 崇司; 竹内, 聖悟
• 著者名(英): Takashi, Harada; Shogo, Takeuchi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 集合 S と集合 S の部分集合からなる集合 F が与えられとき，F の部分集合で S の分割となるものがあるかを判定する問題を厳密被覆問題という．厳密被覆問題は，割当問題やパズルを解くことに用いることができる問題で，高速な解法が提案されている．現実の問題を厳密被覆問題として定式化すると，F のサイズが膨大になってしまうことがあるので，F を zero-suppressed binary decision diagram (ZDD) として圧縮して受け取り，ZDD として圧縮したまま解くアルゴリズムが提案されている．F の要素 o を選ぶと，S の要素 x を被覆できなくなるとき，o は x をブロックするという．本稿では，厳密被覆問題の問題例を表す ZDD が与えられたとき，Blocking を引き起こす F の要素を横断を利用して発見する方法を示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Exact Cover (XC) is the following problem; given a set S and a family F of subsets of S, deciding whether there is a subset of F that is a partition of S. XC can be used to solve assignment problems and puzzles, and a fast algorithm is known. Because formulating a practical problem can make a size of F huge, an algorithm that takes an input as compressed data structure, zero-suppressed binary decision diagram (ZDD) and solves it without decompressing ZDD is proposed. If selecting an element o of F causes that an element x of S can not be covered, we say that x is blocked by o. In this paper, we propose an algorithm that takes a ZDD representing an instance of XC and outputs subsets of F causing blocking.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2024-AL-198, 号 12, p. 1-5, 発行日 2024-05-01
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会