Problemas de movimiento de guijarros

Los problemas de movimiento de guijarros , o movimiento de guijarros en grafos , son un conjunto de problemas relacionados en la teoría de grafos que tratan sobre el movimiento de múltiples objetos ("guijarros") de vértice a vértice en un grafo con una restricción en el número de guijarros que pueden ocupar un vértice en un momento dado. Los problemas de movimiento de guijarros aparecen en dominios como la planificación de movimiento de múltiples robots (en la que los guijarros son robots) y el enrutamiento de redes (en la que los guijarros son paquetes de datos). El ejemplo más conocido de un problema de movimiento de guijarros es el famoso rompecabezas de las 15 piezas , donde un grupo desordenado de quince fichas debe reorganizarse dentro de una cuadrícula de 4x4 deslizando una ficha a la vez.

La forma general del problema del movimiento de guijarros es Movimiento de guijarros en grafos ^{[ 1 ]} formulado de la siguiente manera:

Dejar${\displaystyle G=(V,E)}$ser un gráfico con${\displaystyle n}$vértices. Deje${\displaystyle P=\{1,\ldots ,k\}}$ser un conjunto de guijarros con${\displaystyle k<n}$Una disposición de guijarros es un mapa.${\displaystyle S:P\rightarrow V}$de tal manera que${\displaystyle S(i)\neq S(j)}$para${\displaystyle i\neq j}$Un movimiento${\displaystyle m=(p,u,v)}$consiste en transferir guijarros${\displaystyle p}$desde el vértice${\displaystyle u}$al vértice adyacente desocupado${\displaystyle v}$El problema del movimiento de guijarros en gráficos consiste en decidir, dadas dos disposiciones${\displaystyle S_{0}}$y${\displaystyle S_{+}}$, si existe una secuencia de movimientos que transforma${\displaystyle S_{0}}$en${\displaystyle S_{+}}$.

Encontrar la secuencia de soluciones más corta en el problema del movimiento de guijarros en grafos (con guijarros etiquetados) es conocido por ser NP-difícil ^{[ 6 ]} y APX-difícil ^{[ 3 ]} . El problema sin etiquetar se puede resolver en tiempo polinomial cuando se utiliza la métrica de costo mencionada anteriormente (minimizando el número total de movimientos a vértices adyacentes), pero es NP-difícil para otras métricas de costo naturales ^{[ 3 ] .}