Algoritmia: Divide y vencerás

Índice

• 1 – Introducción
• 2 – Divide y vencerás
• 3 – Problema de ejemplo
  • 3.1 – El caso base
  • 3.2 – Unir las soluciones
• 4 – Implementación del algoritmo
• 5 – Conclusiones

1 – Introducción

En ocasiones, tenemos que enfrentarnos a problemas muy complicados. Tanto, que es prácticamente imposible imaginar las sentencias que debemos escribir para resolverlos. Necesitamos una estrategia inteligente para enfrentarnos a estos monstruos.

Hay algunos casos en los que sabemos resolver una parte pequeña del problema, pero no el conjunto. En estos casos, podemos utilizar la estrategia divide y vencerás. Se trata de ir partiendo nuestro problema en pedazos tan pequeños como sea necesario, hasta que sepamos resolver esos mini problemitas. Luego, volvemos hacia arriba, resolviendo cada vez problemas más grandes, hasta obtener la solución completa.

Si no has entendido nada, no te preocupes. En este tutorial vamos a aprender esta estrategia y cómo aplicarla a un problema real.

2 – Divide y vencerás

No es un secreto para ningún general que la mejor estrategia es dividir a su enemigo para poder aniquilarlo por separado. Este enfoque es el que debemos adoptar cuando nos enfrentamos a este tipo de problemas: sabemos cómo lidiar con un problema pequeño, pero no sabemos cómo hacerlo con el conjunto.

Con esto, ya deberías tener una pista bastante grande. La recursión juega un papel fundamental en este tipo de algoritmos. Si tenemos nuestro caso base, que sabemos resolver, devuelve la solución; si no, sigue troceando el problema hasta tener el caso base. Por supuesto, tenemos que saber también cómo combinar esas soluciones parciales. Pero eso es un problema mucho más sencillo que abordar todo el conjunto de golpe.

Incluso, puede que sí sepamos cómo abordar el problema desde otro enfoque, pero este sea mucho más ineficiente. Pensemos en cómo buscar una palabra en el diccionario. Por supuesto, podemos empezar desde el principio y pasar páginas hasta encontrarla. Sin embargo, este procedimiento es muy lento. A no ser que tengamos la suerte de que se encuentre entre las primeras, la eficiencia es lineal. De media, tardaremos n/2 iteraciones.

Pero también podemos ser más listos. Las palabras están ordenadas alfabéticamente. Así que, podemos abrir el diccionario por la mitad exacta. Si la palabra está por detrás, descartamos la mitad posterior a esa página; si no, descartamos la mitad anterior. En cualquiera de los casos, volvemos a abrir el subconjunto de páginas por la mitad y repetimos el proceso, hasta que demos con ella.

Este algoritmo se denomina búsqueda binaria y podemos utilizarlo siempre que tengamos un conjunto de elementos ordenados. Como podéis observar, es mucho más eficiente, ya que estamos descartando la mitad de los casos restantes con cada iteración, mientras que con la búsqueda lineal sólo descartábamos uno.

3 – Problema de ejemplo

Queremos dividir una imagen para formar un puzle. Sin embargo, este puzle no será uno cualquiera. Vamos a hacer que cada uno sea único, de forma que las piezas sean totalmente diferentes.

La imagen es cuadrada y sus dimensiones son múltiplos de 4. Lo que queremos es dividirla en piezas con forma de L. Estas L tienen un tamaño de 2×2, dejando, obviamente, un área de 1×1 sin cubrir. Para hacer estos puzles únicos, lo que vamos a hacer es insertar una pieza de 1×1 en una posición cualquiera de la matriz, y calcular la disposición de nuestras L a partir de ella.

Difícil, ¿no? Vamos a empezar por identificar nuestro caso base. Iremos ilustrando mediante tablas, donde utilizaremos el mismo número para las casillas que estén ocupadas por una misma pieza.

3.1 – El caso base

Tenemos una superficie bidimensional con un tamaño desconocido, pero sabemos dos datos claves: es cuadrada y sus dimensiones son múltiplos de 4. Esto ya limita bastante el alcance del algoritmo.

El caso más básico sería una imagen de 4×4. Colocaríamos nuestra pieza de 1×1 en cualquier posición y tendríamos que calcular el resto a partir de ella. Es algo más simple que hacerlo para una matriz de 64×64, pero todavía parece complicado.

Entonces nos damos cuenta de algo: si dividimos la matriz de 4×4 en cuatro cuadrantes de 2×2… ¡tenemos un caso todavía más básico! Y este sí que parece fácil de resolver. Al menos el cuadrante en el que haya caído nuestra pieza de 1×1, porque… ¡sólo tenemos que ajustar la L en las otras tres casillas que quedan sin ocupar.

3.2 – Unir las soluciones

Vale, tenemos la solución para un caso básico de 2×2 donde tenemos una de las casillas ya rellenas. Y tenemos la idea de que, para resolver nuestro problema, tenemos que dividir la matriz de la imagen en cuadrantes una y otra vez hasta obtener nuestro tamaño de caso base de 2×2.

Sin embargo, todavía queda un inconveniente: aunque consigamos fragmentos de 2×2, sólo uno de ellos cumple las condiciones de nuestro caso base. El resto no sabemos cómo resolverlos.

Volvamos a nuestro caso de 4×4. Ya tenemos uno de los cuadrantes resueltos, pero ahora quedan los otros tres. Si tuviéramos una casilla rellena en cada uno… no necesitaríamos nada más para solucionarlo. Pero no la tenemos. ¿Cómo podríamos conseguirlo?

Entonces caemos en la cuenta: si colocamos una L que encaje con la esquina del cuadrante que ya tenemos relleno… ¡los otros tres cuadrantes consiguen una casilla rellena cada uno!

Y, lo que es más, si aplicamos la misma lógica a matrices más grandes, ¡el planteamiento funciona por sí mismo!

4 – Implementación del algoritmo

Aquí os dejo una implementación que he hecho del algoritmo. Podéis encontrar el código completo del ejemplo en el repositorio de GitHub (se abre en una ventana nueva). Aquí sólo expondré las partes más relevantes:

    public void split(int firstPieceRow, int firstPieceColumn) throws InvalidFirstPiece {
        if (!isValidFirstPiece(firstPieceRow, firstPieceColumn))
            throw new InvalidFirstPiece("The piece must be in the matrix.");
        splitFirstPiece(firstPieceRow, firstPieceColumn);
        splitAux(0, 0, dim - 1, dim - 1);
    }

    private void splitAux(int rowStart, int colStart, int rowEnd, int colEnd) {
        if (isBaseCase(rowStart, rowEnd)) {
            splitBaseCase(rowStart, colStart, rowEnd, colEnd);
        } else {
            // First we look for a quadrant which has one position splitted to split the
            // whole quadrant.
            final int splittedQuadrant = getSplittedQuadrant(rowStart, colStart, rowEnd, colEnd);
            SplitQuadrant((splittedQuadrant), rowStart, colStart, rowEnd, colEnd);
            // Now we set a L piece at the corner of this quadrant.
            setCornerPiece(rowStart, colStart, rowEnd, colEnd, splittedQuadrant);
            // Finally, whe split the rest of the quadrants.
            splitRemainingQuadrants(rowStart, colStart, rowEnd, colEnd, splittedQuadrant);
        }
    }

    private void splitRemainingQuadrants(int rowStart, int colStart, int rowEnd, int colEnd, int splittedQuadrant) {
        if (splittedQuadrant != 1)
            SplitQuadrant(1, rowStart, colStart, rowEnd, colEnd);
        if (splittedQuadrant != 2)
            SplitQuadrant(2, rowStart, colStart, rowEnd, colEnd);
        if (splittedQuadrant != 3)
            SplitQuadrant(3, rowStart, colStart, rowEnd, colEnd);
        if (splittedQuadrant != 4)
            SplitQuadrant(4, rowStart, colStart, rowEnd, colEnd);
    }

    private void setCornerPiece(int rowStart, int colStart, int rowEnd, int colEnd, int splittedQuadrant) {
        final int middleRow = rowStart + (rowEnd - rowStart) / 2;
        final int middleCol = colStart + (colEnd - colStart) / 2;

        if (splittedQuadrant != 1)
            splitPosition(middleRow, middleCol);
        if (splittedQuadrant != 2)
            splitPosition(middleRow, middleCol + 1);
        if (splittedQuadrant != 3)
            splitPosition(middleRow + 1, middleCol);
        if (splittedQuadrant != 4)
            splitPosition(middleRow + 1, middleCol + 1);
        pieceNumber++;
    }

    private void splitBaseCase(int rowStart, int colStart, int rowEnd, int colEnd) {
        for (int i = rowStart; i <= rowEnd; i++) {
            for (int j = colStart; j <= colEnd; j++) {
                if (!isSplittedPosition(i, j))
                    splitPosition(i, j);
            }
        }
        pieceNumber++;
    }

5 – Conclusiones

Algunos problemas pueden ser difíciles de solucionar cuando tratamos de abordarlos por completo. Sin embargo, si podemos dividirlos en partes más simples que sí sepamos resolver, estaremos en el buen camino. La estrategia divide y vencerás puede aplicarse a un buen número de ellos. ¡No lo olvides!