逆探索によるpmgタイリング可能なポリアモンドの列挙

• Item type: SIG Technical Reports(1)
• 公開日: 2016-09-16
• タイトル: 逆探索によるpmgタイリング可能なポリアモンドの列挙
• タイトル / 言語: en
• タイトル: Enumeration of Polyiamonds for pmg Tiling by the Reverse Search
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 埼玉大学理工学研究科
• 著者所属: 埼玉大学理工学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Engineering, Saitama University
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Engineering, Saitama University
• 著者名: 宮坂, 正大; 堀山, 貴史
• 著者名(英): Masahiro, Miyasaka; Takashi, Horiyama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ポリアモンドは単位正三角形を辺同士が接続するように組み合わせてできる図形である．pmg タイリングは，鏡映とすべり鏡映の繰り返しで，基本図形を平面に隙間なく，重なりなく敷き詰めるタイリングである．本稿では，逆探索による pmg タイリング可能なポリオミノ ( 単位正方形からなる ) の列挙アルゴリズムを拡張し，pmg タイリング可能なポリアモンドの列挙アルゴリズムを提案する．提案手法は，列挙対象の間に親子関係を定義し，その木構造により列挙を行う逆探索に基づいている．過去の生成図形との同一性判定を必要とする試行錯誤による従来法に対して，逆探索ではルールに従って次の図形を生成することにより，計算時間の効率化と計算容量の削減が図れる．また，逆探索の開始点にあたる家系木の根の図形に 「 関節 」 が存在する場合には，逆探索による pmg タイリング可能なポリオミノの列挙アルゴリズムを単純には適用できないが，新たなアルゴリズムを与え，漏れなく重複なく列挙できることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Polyiamonds are the two dimensional shapes made by connecting n equal-sized equilateral triangles, joined along their edges. Polyiamonds for pmg tiling are defined as the polyiamonds those can cover the plane by reflection and glide reflection. In this paper, we propose algorithms to enumerate all polyiamonds for pmg tiling, based on the one enumerating polyominoes for pmg tilig. Our approach is based on the reverse search, in which we design rules to generate the next. By this approach, apart from the conventional method with trial and error, we can reduce the computational time and also the space complexity. If the root node that is the starting point of the reverse search has a joint, we cannot directly apply the algorithm for polyominoes to our problem. Thus, we propose new algorithms and proove that can enumerate all polyiamonds.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2016-AL-159, 号 1, p. 1-8, 発行日 2016-09-16
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会