Ls in L と Sphinxes in Sphinx に対する敷き詰め方の数の下界の改善フロンティア法による敷き詰め方の列挙

• Item type: SIG Technical Reports(1)
• 公開日: 2016-06-17
• タイトル: Ls in L と Sphinxes in Sphinx に対する敷き詰め方の数の下界の改善フロンティア法による敷き詰め方の列挙
• タイトル / 言語: en
• タイトル: Improving the lower bounds of the number of tilings for Ls in L and Sphinxes in Sphinx Enumerating tilings by frontier-based search
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 神戸大学
• 著者所属: 神戸大学
• 著者所属(英): en
• 著者所属(英): Kobe University
• 著者所属(英): en
• 著者所属(英): Kobe University
• 著者名: 兼本, 樹; 斎藤, 寿樹
• 著者名(英): Itsuki, Kanemoto; Toshiki, Saitoh
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ある図形を拡大した盤面に，元の図形を敷き詰めるパズルを考える．正方形を 3 つ繋げた L 型に対するパズルを Ls in L，正三角形を 6 つ繋げた Sphinx 型に対するパズルを Sphinxes in Sphinx という．近年，Horiyama らによって， これらのパズルに対する解の存在性および敷き詰め方の数え上げの研究が行われた．Horiyama らは数え上げの下界の計算において，拡大倍率の小さい場合における厳密な数え上げを用いている．本研究では， フロンティア法と呼ばれる探索法を用いた敷き詰め方の数え上げアルゴリズムを提案する． フロンティア法とは，幅優先的に探索木を走査する探索手法であり，探索が同一となる複数のノードを共有することで，探索空間を大幅に減らすことができる．提案アルゴリズムにより，既存手法よりも大きな拡大倍率で敷き詰め方の数の厳密な数え上げが行えることを示す． また，L に対する敷き詰め方の数の新たな下界計算法を提案する． これらを用いて，敷き詰め方の数の下界を L では Ω((√2)n2) から Ω((1.944)n2) に， Sphinx では Ω((1.364)n2) から Ω((1.404)n2) にそれぞれ改善する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We treat with puzzles which are filled by copies of a polygon in the polygon enlarged in a certain scale. We call the puzzles Ls in L for a L-shaped polygon consisting of three squares, and Sphinxes in Sphinx for a Sphinx-shaped polygon consisting of six equilateral triangles. Recently, Horiyama et al. have shown the existence of a solution and studied the number of tilings for each scale of the puzzles. For computing the lower bounds of the number of tilings, they employed the exact counting at the small scales. In our research, we give an algorithm for counting the number of tilings of the puzzles by using frontier-based search which is a breadth-first search on a search tree. We achieve that our algorithm in our implementation computes the exact number of tilings for a large scale of the puzzles. Moreover, we present an approach for calculating the lower bounds for Ls in L. Using them, we improve the lower bounds of the number of Tilings for L from Ω((√2)n2) to Ω((1.944)n2), and for Sphinx from Ω((1.364)n2) to Ω((1.404)n2).
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2016-AL-158, 号 7, p. 1-7, 発行日 2016-06-17
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会