卵石运动问题

卵石运动问题，或图上的卵石运动，是图论中的一组相关问题，涉及多个物体（卵石）在图中从顶点到顶点的运动，对任何时候能占据一个顶点的卵石数量有约束。

卵石运动问题出现在多机器人运动规划（其中卵石是机器人）和网络路由（其中卵石是数据包）等领域。

卵石运动问题最有名的例子是著名的15谜题，其中一组无序的15块瓷砖必须通过每次滑动一块瓷砖在4x4网格内重新排列。

卵石运动问题的一般形式是图上卵石运动，表述如下。{displaystyleP={1,ldots,k}是一个卵石集合，其中有许多卵石。｝是一个卵石集，其中{displaystyleu}转移到相邻的未被占用的顶点到相邻的未被占用的顶点.图上的卵石运动问题是决定，给定两个安排{displaystyleS_{+}}，是否有一连串的举动能将其转换为一个新的模式？

该问题的常见变化限制了图的结构。另一组变体考虑了部分或全部卵石未被标记且可互换的情况。该问题的其他版本不仅要证明可达性，而且要找到一个（潜在的最佳）移动序列（即一个计划），以执行转换。

在图上的卵石运动问题中寻找最短路径（有标记的卵石），已知是NP-hard和APX-hard。当使用上面提到的成本指标（最小化到相邻顶点的移动总数）时，无标签的问题可以在多项式时间内解决，但对于其他自然成本指标来说是NP-hard。