小石の動きの問題

小石運動問題、またはグラフ上の小石運動は、グラフ理論における一連の関連問題であり、グラフ内の頂点から頂点への複数のオブジェクト (「小石」) の移動を扱います。この移動には、頂点を一度に占めることができる小石の数の制約があります。小石運動問題は、複数ロボットの 動作計画(小石はロボット) やネットワーク ルーティング(小石はデータパケット) などの領域で発生します。小石運動問題の最もよく知られている例は、有名な15 パズルです。このパズルでは、15 個のタイルの無秩序なグループを、一度に 1 個のタイルをスライドさせて 4x4 グリッド内で再配置する必要があります。

小石運動問題の一般的な形式はグラフ上の小石運動^[1]であり、以下のように定式化される。

を頂点を持つグラフとします。をを持つ小石の集合とします。小石の配置とは、に対してとなる写像です。移動とは、小石を頂点から隣接する空いている頂点へ移動させることです。グラフ上の小石の移動問題とは、2 つの配置と が与えられた場合に、を に変換する移動のシーケンスが存在するかどうかを判断することです。 ${\displaystyle G=(V,E)}$${\displaystyle n}$${\displaystyle P=\{1,\ldots ,k\}}$${\displaystyle k<n}$${\displaystyle S:P\rightarrow V}$${\displaystyle S(i)\neq S(j)}$${\displaystyle i\neq j}$${\displaystyle m=(p,u,v)}$${\displaystyle p}$${\displaystyle u}$${\displaystyle v}$${\displaystyle S_{0}}$${\displaystyle S_{+}}$${\displaystyle S_{0}}$${\displaystyle S_{+}}$

この問題の一般的なバリエーションでは、グラフの構造が次のように制限されます。

• 木^[2 ]
• 正方形のグリッド、[ ^3]
• 2連結グラフ。^[4]

別のバリエーションでは、小石の 一部^[5]またはすべて^[3]にラベルが付いておらず、交換可能である場合を考えています。

この問題の他のバージョンでは、到達可能性を証明するだけでなく、変換を実行する（潜在的に最適な）一連の動作（つまり、計画）を見つけることも求められます。

グラフ上の小石の移動問題（ラベル付き小石を使用）における最短解シーケンスを見つけることは、NP困難^[6]かつAPX困難^[3]であることが知られています。 ラベルなし問題は、上記のコストメトリック（隣接頂点への移動の総数を最小化する）を使用すると多項式時間で解決できますが、他の自然なコストメトリックではNP困難です。 ^[3]