文献

J-GLOBAL ID：202102252900810213   整理番号：21A3304732

王将グラフ上での順次交換による色付きドロップ整列の計算量

Sequentially Swapping Colored Tokens on King’s Graphs

著者 (4件)： 岡田優斗 (名古屋大 情報) ,  木谷裕紀 (九大 大学院経済学研究院) ,  大舘陽太 (名古屋大 大学院情報学研究院) ,  小野廣隆 (名古屋大 大学院情報学研究院)
資料名： 電子情報通信学会技術研究報告(Web)  (IEICE Technical Report (Web))
巻： 121  号： 218(COMP2021 13-20)  ページ： 36-38 (WEB ONLY)  発行年： 2021年10月16日 
JST資料番号： U2030A  ISSN： 2432-6380  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 王将グラフとは王将の動きをもとに定義されたグラフであり,いわゆるグリッドに斜辺を足した形をとる.本研究では王将グラフの各頂点に置かれた色付きドロップを初期配置から最終配置に整列させる問題を考える.ただし,ドロップの移動はグラフの適当な歩(walk)上でドロップを順次交換する形をとる.2×2以上の王将グラフ上では十分長い歩に沿って順次交換を行えば,任意の初期配置からドロップ各色の色数が等しい任意の最終配置へ整列させることができることが知られている.本研究では,そのような歩長のオーダー的にタイトな上界を与える.またドロップが2色の場合,入力kに対して歩長k以下の順次交換で目的を達成可能かの判定がNP完全であることなどを示す.なおこの問題は,モバイル端末ゲーム,パズル&ドラゴンズでのドロップ移動をモデル化したものである.(著者抄録)

シソーラス用語： *グラフ ,  交換 ,  シーケンシャル処理 ,  アラインメント ,  *娯楽 ,  *計算量
準シソーラス用語： パズル ,  計算の複雑さ ,  順次処理 ,  整列

分類 (1件)： 計算理論  (JB02000A)

引用文献 (6件)：

• “パズル&ドラゴンズ”.
• K. Yamanaka, E. D. Demaine, T. Horiyama, A. Kawamura, S. Nakano, Y. Okamoto, T. Saitoh, A. Suzuki, R. Uehara and T. Uno: “Sequentially swapping colored tokens on graphs”, Journal of Graph Algorithms and Applications, 23, 1, pp. 3-27 (2019).
• W. W. Johnson and W. E. Story: “Notes on the “15” puzzle”, American Journal of Mathematics, 2, 4, pp. 397-404 (1879).
• D. Ratner and M. Warmuth: “Finding a shortest solution for the n x n extension of the 15-puzzle is intractable”, AAAI’86, AAAI Press, pp. 168-172 (1986).
• D. Ratner and M. Warmuth: “The (n²-1)-puzzle and related relocation problems”, Journal of Symbolic Computation, 10, 2, pp. 111-137(1990).

タイトルに関連する用語 (4件)： グラフ ,  ドロップ ,  整列 ,  計算量