文献

J-GLOBAL ID：201502202353887272   整理番号：15A1163762

”Sorting k-Sets in Bins”のための効率的なアルゴリズム

Efficient Algorithms for Sorting k-Sets in Bins

著者 (5件)： NAGAO Atsuki (Kyoto Univ.) ,  NAGAO Atsuki (Japan Soc. for the Promotion of Sci.) ,  SETO Kazuhisa (Seikei Univ.) ,  TERUYAMA Junichi (National Inst. of Informatics) ,  TERUYAMA Junichi (JST, ERATO, Kawarabayashi Large Graph Project)
資料名： IEICE Transactions on Information and Systems (Web)  (IEICE Transactions on Information and Systems (Web))
巻： E98.D  号： 10  ページ： 1736-1743 (J-STAGE)  発行年： 2015年 
JST資料番号： U0469A  ISSN： 1745-1361  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： ”Sorting k-Sets in Bins”問題向けの効率的なアルゴリズムを提案した。この問題は,次のように述べることができる。各ビンの中にk個のボールを持つ番号付けられたn本のビンを考える。i番目のビンの中のボールは,n-i+1と番号付ける。そして,隣接したビン内のボールのみを交換できる。筆者等のタスクは,すべてのボールを同様に番号付けられたビンに移動することである。この問題に関して,(k+1/4)n²+O(k+n)交換の効率的な欲張りアルゴリズムを与えた。また,k=3に関する詳細な分析を実施し,さらに効率的な再帰的アルゴリズムを与えた。このアルゴリズムは,k=3に関して15/16n²+O(n)交換である。(翻訳著者抄録)

シソーラス用語： *ソーティング ,  アルゴリズム ,  *計算機アルゴリズム ,  娯楽 ,  効率
準シソーラス用語： ソート処理 ,  パズル ,  計算効率 ,  再帰アルゴリズム ,  欲張りアルゴリズム

分類 (1件)： その他の計算機利用技術  (JE14000C)

タイトルに関連する用語 (1件)： アルゴリズム