| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2016-06-24 16:10 Ls in LとSphinxes in Sphinxに対する敷き詰め方の数の下界の改善 ～ フロンティア法による敷き詰め方の列挙 ～ ○兼本 樹・斎藤寿樹（神戸大）  COMP2016-9 |
|
| 抄録 | （和） | ある図形を拡大した盤面に，元の図形を敷き詰めるパズルを考える．正方形を３つ繋げた 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)にそれぞれ改善する． |
| （英） | 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). | |
| キーワード | （和） | 敷き詰めパズル / 数え上げ / フロンティア法 / / / / / |
| （英） | Tiling puzzles / Enumeration / Frontire-based search / / / / / | |
| 文献情報 | 信学技報, vol. 116, no. 116, COMP2016-9, pp. 41-47, 2016年6月. | |
| 資料番号 | COMP2016-9 | |
| 発行日 | 2016-06-17 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2016-9 |
|
| 研究会情報 | |
| 研究会 | COMP IPSJ-AL |
| 開催期間 | 2016-06-24 - 2016-06-25 |
| 開催地（和） | 石川県教育会館 |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2016-06-COMP-AL |
| 本文の言語 | 日本語 |
| タイトル（和） | Ls in LとSphinxes in Sphinxに対する敷き詰め方の数の下界の改善 |
| サブタイトル（和） | フロンティア法による敷き詰め方の列挙 |
| タイトル（英） | Improving the lower bounds of the number of tilings for Ls in L and Sphinxes in Sphinx |
| サブタイトル（英） | Enumerating tilings by frontier-based search |
| キーワード(1)（和/英） | 敷き詰めパズル / Tiling puzzles |
| キーワード(2)（和/英） | 数え上げ / Enumeration |
| キーワード(3)（和/英） | フロンティア法 / Frontire-based search |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 兼本 樹 / Itsuki Kanemoto / カネモト イツキ |
| 第1著者 所属（和/英） | 神戸大学 (略称： 神戸大) Kobe University (略称： Kobe Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 斎藤 寿樹 / Toshiki Saitoh / |
| 第2著者 所属（和/英） | 神戸大学 (略称： 神戸大) Kobe University (略称： Kobe Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2016-06-24 16:10:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2016-9 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | no.116 |
| ページ範囲 | pp.41-47 |
| ページ数 | 7 |
| 発行日 | 2016-06-17 (COMP) |
[研究会発表申込システムのトップページに戻る]