| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 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 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2009-05-26 - 2009-05-26 |
| 開催地（和） | 埼玉大学 |
| 開催地（英） | Saitama Univ. |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2009-05-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | ポリオミノのp4タイリングの列挙 |
| サブタイトル（和） | |
| タイトル（英） | Enumeration of Polyominoes for p4 Tiling |
| サブタイトル（英） | |
| キーワード(1)（和/英） | アルゴリズム / algorithms |
| キーワード(2)（和/英） | 列挙 / enumeration |
| キーワード(3)（和/英） | タイリング / tiling |
| キーワード(4)（和/英） | 回転対称 / rotational symmetry |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 堀山 貴史 / Takashi Horiyama / ホリヤマ タカシ |
| 第1著者 所属（和/英） | 埼玉大学 (略称： 埼玉大) Saitama University (略称： Saitama Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 鮫島 真人 / Masato Samejima / サメジマ マサト |
| 第2著者 所属（和/英） | 埼玉大学 (略称： 埼玉大) Saitama University (略称： Saitama Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2009-05-26 16:15:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2009-17 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | no.54 |
| ページ範囲 | pp.51-55 |
| ページ数 | 5 |
| 発行日 | 2009-05-19 (COMP) |
[研究会発表申込システムのトップページに戻る]