講演抄録/キーワード |
講演名 |
2009-05-26 16:15
ポリオミノのp4タイリングの列挙 ○堀山貴史・鮫島真人(埼玉大) COMP2009-17 |
抄録 |
(和) |
ポリオミノは、2次元平面上で、n個の単位正方形を辺同士で接続した図形である。
本論文では、p4 対称群すなわち 2つの回転中心の周りでの90度回転により
平面埋め尽くしが可能なポリオミノを列挙するアルゴリズムを提案する。
既存の手法では、試行錯誤によりポリオミノを生成し、
既出の図形かどうかのチェックを通ったものだけを出力している。
一方、本論文の手法は逆探索に基づいており、
ルールに従って次に生成する図形を決定するため、
試行錯誤の排除による計算時間の効率化、
既出の図形を蓄えないことによるメモリ資源の効率化を達成できる。
計算機実験として、n = 18 までのすべての p4 ポリオミノの生成を行う。 |
(英) |
Polyominoes are the two dimensional shapes
made by connecting n unit squares, joined along their edges.
In this paper, we propose algorithms to enumerate polyominoes for p4 tiling,
i.e., those covering the plane by only 90 degrees rotations
around the two rotation centers.
The conventional methods are basically trial and error, i.e.,
they repeat generating polyominoes and checking whether
the shape has been already generated.
Our approach is based on the reverse search,
in which we design rules to generate the next.
This technique has the following two characteristics:
(1) No trial and error, which implies that we can reduce the computation time.
(2) No need to store already enumerated polyominoes.
Thus, we can also reduce the space complexity.
We also implement the algorithm and enumerate
all polyominoes for p4 tiling up to n = 18. |
キーワード |
(和) |
アルゴリズム / 列挙 / タイリング / 回転対称 / / / / |
(英) |
algorithms / enumeration / tiling / rotational symmetry / / / / |
文献情報 |
信学技報, vol. 109, no. 54, COMP2009-17, pp. 51-55, 2009年5月. |
資料番号 |
COMP2009-17 |
発行日 |
2009-05-19 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2009-17 |