講演抄録/キーワード |
講演名 |
2013-12-21 11:25
$k$集合整列問題に対する効率のよいアルゴリズム 脊戸和寿(成蹊大)・○照山順一(NII)・長尾篤樹(京大) COMP2013-52 |
抄録 |
(和) |
本稿では$k$集合整列問題に対して効率のよいアルゴリズムを与える.
$k$集合整列問題とは以下のような問題である:
$n$個のビンに$k$個のボールが入っており,$i$番目のビンにあるボールすべてに番号$n-i+1$がついている.
隣り合うビンに存在する任意の2つのボールの交換のみを許した時,
すべてのボールとビンの番号を一致させるためには何回の交換が必要だろうか.
我々はこの問題に対して,高々$frac{k+1}{4}n^2 + O(n)$回の交換で本問題を解く貪欲アルゴリズムを与える.
この値は$n, k$が大きくなるにつれて下界値と近くなる.
また,$k=3$の場合に対してさらに効率のよいアルゴリズムを与える.
このアルゴリズムは再帰的アルゴリズムであり,
高々$frac{15}{16}n^2 + O(n)$回の交換で本問題を解くことができる. |
(英) |
We give efficient algorithms for Sorting $k$-Sets in Bins.
The Sorting $k$-Sets in Bins problem can be described as follows:
We are given numbered $n$ bins with $k$ balls in each bin.
Balls in the $i$-th bin are numbered $n-i+1$.
We can only swap balls between adjacent bins.
How many swaps are needed to move all balls to the same numbered bins.
For this problem, we design an efficient greedy algorithm with $frac{k+1}{4}n^2+O(kn)$ swaps.
As $k$ and $n$ increase, this approaches the lower bound of $lceil binom{kn}{2}/(2k-1) rceil$.
In addition, we design a more efficient recursive algorithm using $frac{15}{16}n^2+O(n)$ swaps
for the $k=3$ case. |
キーワード |
(和) |
貪欲アルゴリズム / 再帰アルゴリズム / 数理パズル / ソート / スワップ / / / |
(英) |
Greedy / Recursion / Mathematical puzzle / Sorting / Swap / / / |
文献情報 |
信学技報, vol. 113, no. 371, COMP2013-52, pp. 81-85, 2013年12月. |
資料番号 |
COMP2013-52 |
発行日 |
2013-12-13 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2013-52 |