Número mínimo de pasos necesarios para visitar cada esquina de una cuadrícula rectangular

Question

Estoy atascado en este problema:

---

Supongamos que tenemos la siguiente configuración de red (o matriz) $G\in \Bbb{M}^{\{0,x,y\}}_{m\times n}$

(Es decir $G$ es una matriz que tiene $m$ filas y $n$ Columna sobre el alfabeto $\{0,x,y\}$ ) $$G= \begin{bmatrix} x & 0 & 0 & \cdots & x \\ 0 & 0 & 0 & \cdots & 0 \\ 0 & y & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ x & 0& 0& \cdots & x \end{bmatrix} $$

¿Qué es la mínimo número de pasos necesarios para $y$ para visitar cada una de las esquinas de la cuadrícula (es decir, cada una de las $x$ en la matriz) donde $y$ puede moverse a la izquierda , a la derecha , arriba y abajo un célula a la vez?

(El $y$ en la red $G$ fue colocado arbitrariamente, $y$ puede estar en cualquier parte de la matriz, incluso en las esquinas).

---

Mi intento :

El número mínimo de pasos necesarios para $y$ para visitar cada una de las esquinas de la cuadrícula es al menos la suma de las distancias manhattan de $y$ a cada una de las esquinas de la cuadrícula, ya que el número mínimo de pasos necesarios para llegar a cada esquina de la cuadrícula es igual a la distancia manhattan a esa esquina, obtenemos que la suma de estas distancias será el número mínimo de pasos necesarios para llegar a cada una de las esquinas.

Desgraciadamente, mi respuesta es errónea.

Si tomo por ejemplo la red: $$G= \begin{bmatrix} x & 0 & 0 & 0 & 0 & x \\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & y & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ x & 0 & 0 & 0 & 0 & x \end{bmatrix} $$

Podemos ver que el número mínimo de pasos requeridos es realmente 19 y no la suma de las distancias manhattan que es 20.

---

Gracias por cualquier pista o ayuda.

(Nota: Me he encontrado con este problema al tratar de averiguar una heurística para $A^*$ búsqueda en cuadrícula que calcula una ruta para $y$ que debe visitar cada una de las esquinas de una cuadrícula al menos una vez)

Answer 1

La solución es utilizar un enfoque codicioso. Siempre se visita la esquina cuya distancia Manhattan es la menor y luego se visitan las otras 3 esquinas mientras se rozan los bordes de la matriz.

La intuición es que debemos minimizar el número de pasos que repetimos en una dirección determinada.

Que la distancia (Manhattan) que recorre para desplazarse a una esquina sea $\Delta x + \Delta y$ . Una vez que estás en la esquina, la forma óptima es moverse a través de los bordes de la matriz ya que (por la desigualdad del triángulo) cualquier otra secuencia será subóptima. Al pasar por los bordes la distancia que repetirás es $s = \Delta x + \Delta y$ por lo que nuestro objetivo es minimizar $s$

Answer 2

En realidad creo que hay una fórmula relativamente sencilla para esto (cabe en una línea) si no te importan unas cuantas aplicaciones del $\min(\cdot,\cdot)$ función.

Que las filas de la cuadrícula estén numeradas $1$ a través de $m$ las columnas numeradas $1$ a través de $n$ . Que la posición inicial $y$ estar en la fila $j$ y la columna $k$ , y denotar esta posición por las coordenadas $(j,k)$ .

La respuesta de Banach Tarski le da la estrategia correcta para minimizar el número total de pasos. Empezamos por encontrar las distancias a todas las las esquinas y luego elegir la esquina más cercana.

Para llegar a una esquina, podemos subir $j - 1$ filas o hacia abajo $m - j$ filas; e independientemente de la elección de arriba o abajo, podemos ir izquierda $k - 1$ columnas o derecha $n - k$ columnas. Sea cual sea la esquina que elijamos, el número de pasos es simplemente la suma del número de filas que hay que recorrer y el número de columnas que hay que recorrer. Por tanto, la distancia de Manhattan a la esquina más cercana es $$ \min(j - 1, m - j) + \min(k - 1, n - k). \tag1 $$

Después de llegar a la esquina, visitamos las tres siguientes esquinas atravesando los bordes de la cuadrícula. Una vez elegida la siguiente esquina, se determina el resto del recorrido. determinado. Haremos una de las siguientes cosas:

• arriba (o abajo) $m-1$ filas, luego a la izquierda (o a la derecha) $n-1$ columnas, luego hacia abajo (o hacia arriba) $m-1$ filas hasta la última esquina, un total de $2m + n - 3$ pasos.
• izquierda (o derecha) $n-1$ columnas, luego hacia arriba (o hacia abajo) $m-1$ filas, luego a la derecha (o a la izquierda) $n-1$ columnas hasta la última esquina, un total de $m + 2n - 3$ pasos.

Claramente, $2m + n - 3 < m + 2n - 3$ si y sólo si $m < n$ de hecho, $2m + n - 3 = (m + n - 3) + m$ y $m + 2n - 3 = (m + n - 3) + n$ . Por lo tanto, el número restante de pasos, que es la menor de estas dos cantidades, es $$ (m + n - 3) + \min(m,n). \tag 2 $$

Para encontrar el número total de pasos, sumamos las expresiones $(1)$ y $(2)$ juntos: $$ (m + n - 3) + \min(m,n) + \min(j - 1, m - j) + \min(k - 1, n - k). $$

Si prefiere utilizar valores absolutos en lugar de $\min(\cdot,\cdot)$ , se puede utilizar la siguiente ecuación de identidad: $$ \min(a,b) = \tfrac12(x + y - \lvert x - y \rvert). $$

La distancia total es entonces de $$ (m + n - 3) + \tfrac12(m + n - \lvert m - n \rvert) + \tfrac12(m - 1 - \lvert m - 2j + 1 \rvert) + \tfrac12(n - 1 - \lvert n - 2k + 1 \rvert) $$ que se simplifica a $$ 2m + 2n - 4 - \tfrac12(\lvert m - n \rvert + \lvert m - 2j + 1 \rvert + \lvert n - 2k + 1 \rvert). $$

Answer 3

He aquí una solución algorítmica para encontrar el número de pasos mínimos necesarios para recorrer cada una de las esquinas de la matriz al menos una vez:

(Para una forma eficaz de calcular el valor, véase la respuesta de David K)

El algoritmo se llama FindMinimalNumberOfStepsToVisitAllCorners donde esquinas es un conjunto de vectores de componentes enteros no negativos en 2D y posición es un vector de componentes enteros no negativos en 2D que indica la posición inicial en la cuadrícula:

// Returns the closest corner in the set 'corners' to 'position'.
FindMinimalCorner(position, corners)
    minimalCorner = null
    minimalDistance = 0

    for each corner in corners
        if minimalCorner = null
            minimalCorner = corner
            minimalDistance = manhattanDistnace(position, corner)
        else
            if  minimalDistance > manhattanDistnace(position, corner)
                minimalCorner = corner
                minimalDistance = manhattanDistnace(position, corner)

    return (minimalCorner, minimalDistance)

// Returns the minimal number of steps required to visit all 'corners' from 'firstPosition'.
FindMinimalNumberOfStepsToVisitAllCorners(firstPosition, corners)
    sumOfDistances = 0
    position = firstPosition

    while corners != EMPTY_SET
        (minimalCorner, minimalDistance) = FindMinimalCorner(position, corners)

        sumOfDistances = sumOfDistances  + minimalDistance

        position = minimalCorner
        corners = corners - {minimalCorner}

    return sumOfDistances