お知らせ 研究会の開催と会場に参加される皆様へのお願い(2020年7月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2011-04-22 11:25
πDD: 順列集合を演算処理する二分決定グラフ
湊 真一北大/JSTCOMP2011-4
抄録 (和) 「順列」は「組合せ」と並んで離散数学や計算機科学の基礎をなす重要な概念であり、ソーティング、順序付け、マッチング、符号化等、多くの局面に現れる。本稿では、「$\pi$DD」(順列二分決定グラフ)と呼ぶ新しい二分決定グラフを提案する。$\pi$DDは、多数の順列を要素として含む順列集合をコンパクトかつ一意に表現し、演算処理を効率よく行える。中でも、全ての順列の合成を求める直積演算は強力で実用的である。本稿では$\pi$DDの基本的なデータ構造と演算アルゴリズムを示し、さらに簡単な応用例として、あみだくじの解析およびルービックキューブの解析の実験結果を示す。$\pi$DDは数十億もの膨大な個数の順列を現実的な計算時間と記憶量で列挙し、さらに順列集合演算を適用して様々な制約充足問題を解くことができる。 
(英) Permutations and combinations are a couple of basic concepts in elementary combinatorics. Permutations appear in various problems such as sorting, ordering, matching, coding, and many other real-life situations. In this paper, we propose a new decision diagram ``$\pi$DD,'' for compact and canonical representation of a {\em set of permutations}. $\pi$DD has efficient algebraic set operations such as union, intersection, and especially, it has a special Cartesian product operation to generate all possible composite permutations for given two sets of permutations. This is a beautiful and powerful property of $\pi$DDs.
This paper presents the data structures and the basic operation algorithms for $\pi$DDs. We also show two application examples of $\pi$DDs: designing permutation networks and analysis of Rubik's Cube. The experimental results show that $\pi$DD-based method can explore billions of permutations in a feasible time and space, using simple algebraic operations for solving the problems.
キーワード (和) πDD / 順列二分決定グラフ / BDD / ZDD / 順列集合 / 組合せ問題 / /  
(英) $\pi$DD / PiDD / BDD / ZDD / Set of permutations / Combinatorial problems / /  
文献情報 信学技報, vol. 111, no. 20, COMP2011-4, pp. 25-32, 2011年4月.
資料番号 COMP2011-4 
発行日 2011-04-15 (COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード COMP2011-4

研究会情報
研究会 COMP  
開催期間 2011-04-22 - 2011-04-22 
開催地(和) 京都大学 
開催地(英) Kyoto University 
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2011-04-COMP 
本文の言語 日本語 
タイトル(和) πDD: 順列集合を演算処理する二分決定グラフ 
サブタイトル(和)  
タイトル(英) $\pi$DDs(PiDDs): Binary Decision Diagrams for Manipulating Sets of Combinations 
サブタイトル(英)  
キーワード(1)(和/英) πDD / $\pi$DD  
キーワード(2)(和/英) 順列二分決定グラフ / PiDD  
キーワード(3)(和/英) BDD / BDD  
キーワード(4)(和/英) ZDD / ZDD  
キーワード(5)(和/英) 順列集合 / Set of permutations  
キーワード(6)(和/英) 組合せ問題 / Combinatorial problems  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 湊 真一 / Shin-ichi Minato / ミナト シンイチ
第1著者 所属(和/英) 北海道大学 (略称: 北大/JST)
Hokkaido University (略称: Hokkaido Univ.)
第2著者 氏名(和/英/ヨミ) / /
第2著者 所属(和/英) (略称: )
(略称: )
第3著者 氏名(和/英/ヨミ) / /
第3著者 所属(和/英) (略称: )
(略称: )
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2011-04-22 11:25:00 
発表時間 35 
申込先研究会 COMP 
資料番号 IEICE-COMP2011-4 
巻番号(vol) IEICE-111 
号番号(no) no.20 
ページ範囲 pp.25-32 
ページ数 IEICE-8 
発行日 IEICE-COMP-2011-04-15 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会