WEKO3
アイテム
15パズルの変形とその最短手数の最大値に関する研究
https://ipsj.ixsq.nii.ac.jp/records/210291
https://ipsj.ixsq.nii.ac.jp/records/2102913b14ab38-fe3f-4fd1-b3df-38c8be17e4c6
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL21182010.pdf (750.4 kB)
|
Copyright (c) 2021 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2021-03-10 | |||||||||
| タイトル | ||||||||||
| タイトル | 15パズルの変形とその最短手数の最大値に関する研究 | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | Research on transformation of 15-puzzle and its maximum shortest moves | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||
| 資源タイプ | technical report | |||||||||
| 著者所属 | ||||||||||
| 北陸先端科学技術大学院大学先端科学技術研究科 | ||||||||||
| 著者所属 | ||||||||||
| 北陸先端科学技術大学院大学先端科学技術研究科 | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| School of Information Science, Japan Advanced Institute of Science and Technology | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| School of Information Science, Japan Advanced Institute of Science and Technology | ||||||||||
| 著者名 |
佐藤, 隆太郎
× 佐藤, 隆太郎
× 上原, 隆平
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | スライディングブロックパズルの 1 つに，15 パズルと呼ばれるパズルがある．15 パズルは，4 × 4 のグリッドに，1 から 15 までの番号が書かれた 15 枚のタイルと 1 つの空きマスで構成される．このパズルの目的は，空きマスに隣接したタイルをスライドさせる操作を繰り返し行い，特定のタイルの配置に変化させることである．15 パズルのサイズは，4 × 4 から m × n に一般化することができる．n × n パズルの最短手数を求める問題は NP 困難であることが知られており，n についての最大の最短手数は分かっていない．本研究では，パズルの一方の長さを小さい値（m＝2）に制限した．そのような 2×n のサイズに対して，計算機を用いて特定の配置における手数や手順を計算し，n についての最大の最短手数の下界値と上界値について示した． | |||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | The 15-puzzle is one of the sliding block puzzles. It consists of a grid of 4 × 4 with 15 tiles numbered from 1 to 15 and one blank space. The goal of this puzzle is to change arrangement of the tiles by repeatedly sliding a tile adjacent to the blank space. The 15-puzzle can be generalized from 4 × 4 to m× n. The problem of finding the shortest moves for an n2 - 1 puzzle is known to NP-hard, and the maximum shortest moves for n is not known. In this study, we limit the width of one side of the puzzle to a small value (m = 2). As a result, we show the lower and upper bounds of the maximum shortest moves for 2 × n. | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AN1009593X | |||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2021-AL-182, 号 10, p. 1-6, 発行日 2021-03-10 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 2188-8566 | |||||||||
| Notice | ||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
