| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2014-06-14 13:55 pmg タイリング可能なポリオミノの列挙 ○西岡 潤・堀山貴史（埼玉大）  COMP2014-14 |
|
| 抄録 | （和） | ポリオミノは単位正方形を辺同士が接続するように組み合わせてできる図形である．pmg タイリングは，鏡映とすべり鏡映の繰り返しで，基本図形を平面に隙間なく重なりなく敷き詰めるタイリングである．本稿では，pmgタイリング可能なポリオミノの列挙アルゴリズムを提案する．提案手法は，列挙対象が内包する木構造を利用して列挙を行う逆探索に基づいており，ルールにより次に出力する図形を求める．このため，過去の生成図形との同一性判定を必要とする試行錯誤による従来法に対して，計算時間の効率化と計算領域の削減が図れる．また，本稿では，逆探索に基づく p4 (90 度回転) タイリングでの証明を拡張し，pmg 特有の証明を加えることで，pmg タイリング可能な図形を漏れなく重複なく列挙できることを示す． |
| （英） | Polyominoes are the two dimensional shapes made by connecting n equal-sized squares, joined along their edges. In this paper, we propose algorithms to enumerate all polyominoes for pmg tiling, i.e., those covering the plane by reflection and glide reflection. Our approach is based on the reverse search, in which we design rules to generate the next. By this approach, appart from the conventional method with trial and error, we can reduce the computational time and also the space complexity. The proof of the enumeration in this paper is based on that for p4 tiling (i.e., tiling by 4-fold rotations). Since new situations arise for pmg tiling, the proof is extended to meet with them. (This article is a technical report without peer review.) |
|
| キーワード | （和） | 列挙アルゴリズム / 逆探索 / タイリング / / / / / |
| （英） | Enumeration algorithm / reverse search / tiling / / / / / | |
| 文献情報 | 信学技報, vol. 114, no. 80, COMP2014-14, pp. 107-114, 2014年6月. | |
| 資料番号 | COMP2014-14 | |
| 発行日 | 2014-06-06 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2014-14 |
|
| 研究会情報 | |
| 研究会 | COMP IPSJ-AL |
| 開催期間 | 2014-06-13 - 2014-06-14 |
| 開催地（和） | 道後温泉（愛媛県松山市） |
| 開催地（英） | Matsuyama, Ehime |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2014-06-COMP-AL |
| 本文の言語 | 日本語 |
| タイトル（和） | pmg タイリング可能なポリオミノの列挙 |
| サブタイトル（和） | |
| タイトル（英） | Enumeration of Polyominoes for pmg Tiling |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 列挙アルゴリズム / Enumeration algorithm |
| キーワード(2)（和/英） | 逆探索 / reverse search |
| キーワード(3)（和/英） | タイリング / tiling |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 西岡 潤 / Jun Nishioka / ニシオカ ジュン |
| 第1著者 所属（和/英） | 埼玉大学 (略称： 埼玉大) Saitama University (略称： Saitama Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 堀山 貴史 / Takashi Horiyama / ホリヤマ タカシ |
| 第2著者 所属（和/英） | 埼玉大学 (略称： 埼玉大) Saitama University (略称： Saitama Univ.) |
| 第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著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2014-06-14 13:55:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2014-14 |
| 巻番号（vol） | vol.114 |
| 号番号（no） | no.80 |
| ページ範囲 | pp.107-114 |
| ページ数 | 8 |
| 発行日 | 2014-06-06 (COMP) |
[研究会発表申込システムのトップページに戻る]