Pebble motion problems とは

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