Límite superior en el número mínimo de movimientos para resolver el $m\times n$ rompecabezas deslizante

Question

Definir un $m\times n$ rompecabezas deslizante para tener un $m\times n$ cuadrícula de numerado plazas, y el único movimiento válido es cambiar el especial cuadrados numerados de 0 con un ortogonalmente adyacentes (arriba/abajo/izquierda/derecha) de la plaza, y el rompecabezas se resuelve si las plazas están ordenados por válida se mueve en una configuración en particular, donde la plaza se encuentra en la esquina superior izquierda (por ejemplo, en orden ascendente, cuando se toma fila por fila, columna por columna). Si debido a un arbitrario solución de rompecabezas, puede el mínimo número de movimientos en la solución se calcula? Si no exactamente, es de esperar una ajustada asintótica bound? Si no se puede calcular fácilmente para juegos individuales, lo que sobre un global de límite superior?

No puedo conseguir nada mejor que $\lfloor{\frac{m^2}{2}}\rfloor n + \lfloor{\frac{n^2}{2}}\rfloor m - m - n + 2$, que se obtiene de considerar el total vertical y horizontal de la distancia en todas las plazas excluyendo el especial de la plaza, de la que cada movimiento puede disminuir en la mayoría de los 1. El peor de configuración parece ser que cuando la red se gira 180 grados sobre el centro. Este bound es claramente apretado para $(m,n)=(2,2)$ pero nada más. Por otra parte no puedo encontrar una solución general para una solución de rompecabezas que tiene el mismo asintótica número de movimientos como los que se une, que bien puede ser más interesante que la exacta obligado a sí mismo!

Answer 1

Como se señaló en los comentarios, el asintótica obligado es, precisamente, $\Theta(n^3)$ (Para el caso general, con $m\geq n$, es en realidad $\Theta(m^2n)$; en aras de la claridad sólo estoy considerando la posibilidad de $m=n$, pero es muy fácil adaptarse a la mayoría de estos argumentos para el caso general). El '180 flip' posición establece el límite inferior, ya que hay $n^2-(\frac{n}{3})^2 = \frac{8}{9}n^2$ azulejos en el tercio exterior de filas y columnas (es decir, con $x$ o $y$ coordinar bien $\lt n/3$ o $\gt 2n/3$) y cada uno de los azulejos debe moverse al menos $n/3$ lugares para llegar a su posición final. Un movimiento sólo puede cambiar la distancia desde el objetivo de una baldosa por una unidad, por lo que establece el $O(n^3)$ límite inferior.

El límite superior viene de la norma de 'rellenar las celdas una por una". Desde cada una de las baldosas no es más que $2n$ a las células de su posición final y en movimiento de una sola plaza toma $O(1)$ mueve (por ejemplo, para mover una celda en una plaza vacía la parte de arriba y dejar la plaza vacía por encima de ella, se mueven en el vacío de la plaza D,R,U,U,L) podemos llenar todos, pero uno de los cuadros en una fila en $O(n^2)$ tiempo sin tener que desplazar a cualquier ya-conjunto de azulejos. El final de la plaza en una fila lleva más de atención, pero que uno puede ser llenado por el desplazamiento de la baldosa de la izquierda en una fila hacia abajo, cambiando el resto de la fila de la derecha, la configuración de la final de la baldosa en cualquiera de los dos de la derecha plazas (sin molestar a ninguna de las otras celdas de la fila) y, a continuación, cambiar el resto de la fila de atrás; este es un proceso complicado, pero sólo añade $O(n)$ se mueve por fila. Un enfoque similar se establece la fila inferior una vez que el resto del rompecabezas está completo: $O(n)$ mueve suficiente para mover cualquiera de las tres fichas de la fila inferior en un 'canónica' en la esquina inferior derecha, realice una norma 3-ciclo sobre ellos, y luego deshacer los movimientos para traer de vuelta a sus ubicaciones originales. Desde cualquier permutación de los azulejos en la fila inferior se puede expresar como un producto de $O(n)$ 3-ciclos, esto añade $O(n^2)$ tiempo total de esfuerzo. En el $m\geq n$ de los casos, el procedimiento anterior se debe rendir $O(m^2n)$, la misma que en su estimación.

'Todo' lo que queda en este punto es la parte más difícil del problema: el establecimiento de la constante en el $n^3$ plazo...

Answer 2

El 2x3 rompecabezas fue llamado el Día de la Mudanza rompecabezas de Sam Loyd. Como un gráfico, hay una alta cantidad de simetría, como se muestra a continuación. Estás buscando el grosor de estos gráficos. Es mejor reducir las esquinas, ya que aumentan el tamaño de la gráfica.

A continuación, sólo tienes que encontrar el Diámetro. No va a ser alta, debido a la simetría.