Cyclic Shift Problems on Graphs
Summary
- 巡回シフトパズルの研究
- 与えられたグラフの各頂点に色のついたトークンが置かれ、グラフ上の区別されたサイクルの集合も与えられる
- 我々は、区別されたサイクルに沿って周期的なシフト操作を行うことにより、与えられた初期配置から最終配置までトークンを再配置することを課される。
- まず、古典的なサイクリックシフトパズルのいくつかを一般化したグラフの大きなクラスを調査
- 与えられた初期配置からどの最終配置に到達できるかの特徴づけを与える。
- 我々の証明は構成的であり、トークンをシフトして目的の配置に到達するための効率的な方法を得ることができる
- 一方、シフト操作の最短シーケンスを求めることを目的とする場合、2色のトークンからなるパズルであっても、この問題はNP困難であることを示す
1. Introduction
- 再構成問題のいくつかは理論計算機科学の重要な基礎問題として研究
- また，15パズルやルービックキューブなど，再構成問題としてモデル化できる実パズルも数多く考案され，パズルコミュニティで提案されている
- その中で、我々は周期的なシフト操作に基づくポピュラーなタイプのパズルに注目する.
- これらのパズルでは、基本操作としてあらかじめ定義されたサイクルに沿っていくつかの要素をシフトさせることができ、目標はピースを所望のパターンに並べ替えることである
モデル化
入力:
- グラフ $G = (V, E)$$
- 色の集合
- トークン交換問題を一般化したものである．
- 実際， の各サイクルの長さを2に制限すると（各サイクルはEの辺に対応する) トークンスワッピング問題と等価である