文献

J-GLOBAL ID：201802243665983802   整理番号：18A1776928

SeqBDDを用いた集合分割の族の表現法と実験的評価

著者 (3件)： 高橋翔哉 (北大 大学院情報科学研究科) ,  湊真一 (京大 大学院情報学研究科) ,  瀧川一学 (北大 大学院情報科学研究科)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2018  号： AL-169  ページ： Vol.2018-AL-169,No.6,1-7 (WEB ONLY)  発行年： 2018年08月27日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： ある集合を重なりのない部分集合に分けたものを集合分割と呼ぶ。集合分割は選挙区割り問題やスケジューリング問題などの応用先を持ち,これらは集合分割の集合(集合分割の族)に対する最適化問題として表現することが可能である。このように集合分割の族を考えることは重要であるが,集合分割の総数は集合の要素数に対して爆発的に増加するために扱うのが難しく,集合分割の族を扱う試みはあまりなされてこなかった。本研究では集合分割をある文字列で表現される操作(操作列)で表し,その操作列の集合をSequence Binary Decision Diagram(SeqBDD)と呼ばれる文字列集合を扱うデータ構造を用いて表現することで集合分割の族を扱う手法を提案する。本稿では様々な集合分割の族をSeqBDDで表現する手法とその計算機実験結果を示す。(著者抄録)

シソーラス用語： 集合 ,  *分割法 ,  表現 ,  性能評価 ,  計算機シミュレーション ,  データ解析 ,  二分決定グラフ ,  *集合論 ,  文字列 ,  制約条件 ,  *最適化問題 ,  数列 ,  定式化
準シソーラス用語： 二分決定図

分類 (1件)： 集合論  (AB10000I)

引用文献 (9件)：

• 根本俊男, 堀田敬介. 公平な小選挙区制のための数理モデル.システム/制御/情報 : システム制御情報学会誌, Vol. 49, No. 3, pp. 78-84, 2005.
• 茨木俊秀. 組合せ最適化とスケジューリング問題: 新解法とその動向. 計測と制御, Vol. 34, No. 5, pp. 340-346, 1995.
• Burcin Bozkaya, Erhan Erkut, and Gilbert Laporte. A tabu search heuristic and adaptive memory procedure for political districting. European Journal of Operational Research, Vol. 144, No. 1, pp. 12-26, 2003.
• Randal E. Bryant. Graph-based algorithms for boolean function manipulation. IEEE Trans. Computers, Vol. 35, No. 8, pp. 677-691, 1986.
• Jun Kawahara, Takeru Inoue, Hiroaki Iwashita, and Shin ichi Minato. Frontier-based search for enumerating all constrained subgraphs with compressed representation. IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E100-A, No. 9, pp. 1773-1784, 2017.

タイトルに関連する用語 (4件)： 集合 ,  表現 ,  実験 ,  評価