chapter05.tex

\chapter{Búsqueda completa}

\key{Búsqueda completa}
es un método general que se puede utilizar
para resolver casi cualquier problema de algoritmo.
La idea es generar todas las posibles
soluciones al problema utilizando la fuerza bruta,
y luego seleccionar la mejor solución o contar la
cantidad de soluciones, dependiendo del problema.

La búsqueda completa es una buena técnica
si hay tiempo suficiente para recorrer todas las soluciones,
porque la búsqueda suele ser fácil de implementar
y siempre da la respuesta correcta.
Si la búsqueda completa es demasiado lenta,
es posible que se necesiten otras técnicas, como los algoritmos voraces o
la programación dinámica.

\section{Generación de subconjuntos}

\index{subconjunto}

Primero consideramos el problema de generar
todos los subconjuntos de un conjunto de $n$ elementos.
Por ejemplo, los subconjuntos de $\{0,1,2\}$ son
$\emptyset$, $\{0\}$, $\{1\}$, $\{2\}$, $\{0,1\}$,
$\{0,2\}$, $\{1,2\}$ y $\{0,1,2\}$.
Hay dos métodos comunes para generar subconjuntos:
podemos realizar una búsqueda recursiva
o explotar la representación en bits de los enteros.

\subsubsection{Método 1}

Una forma elegante de recorrer todos los subconjuntos
de un conjunto es usar la recursión.
La siguiente función \texttt{search}
genera los subconjuntos del conjunto
$\{0,1,\ldots,n-1\}$.
La función mantiene un vector \texttt{subset}
que contendrá los elementos de cada subconjunto.
La búsqueda comienza cuando la función se llama
con el parámetro 0.

\begin{lstlisting}
void search(int k) {
    if (k == n) {
        // process subset
    } else {
        search(k+1);
        subset.push_back(k);
        search(k+1);
        subset.pop_back();
    }
}
\end{lstlisting}

Cuando la función \texttt{search}
se llama con el parámetro $k$,
decide si incluir el
elemento $k$ en el subconjunto o no,
y en ambos casos,
luego se llama a sí misma con el parámetro $k+1$
Sin embargo, si $k=n$, la función nota que
todos los elementos se han procesado
y se ha generado un subconjunto.

El siguiente árbol ilustra las llamadas a funciones cuando $n=3$.
Siempre podemos elegir la rama izquierda
($k$ no está incluido en el subconjunto) o la rama derecha
($k$ está incluido en el subconjunto).

\begin{center}
\begin{tikzpicture}[scale=.45]
  \begin{scope}
    \small
    \node at (0,0) {$\texttt{search}(0)$};

    \node at (-8,-4) {$\texttt{search}(1)$};
    \node at (8,-4) {$\texttt{search}(1)$};

    \path[draw,thick,->] (0,0-0.5) -- (-8,-4+0.5);
    \path[draw,thick,->] (0,0-0.5) -- (8,-4+0.5);

    \node at (-12,-8) {$\texttt{search}(2)$};
    \node at (-4,-8) {$\texttt{search}(2)$};
    \node at (4,-8) {$\texttt{search}(2)$};
    \node at (12,-8) {$\texttt{search}(2)$};

    \path[draw,thick,->] (-8,-4-0.5) -- (-12,-8+0.5);
    \path[draw,thick,->] (-8,-4-0.5) -- (-4,-8+0.5);
    \path[draw,thick,->] (8,-4-0.5) -- (4,-8+0.5);
    \path[draw,thick,->] (8,-4-0.5) -- (12,-8+0.5);

    \node at (-14,-12) {$\texttt{search}(3)$};
    \node at (-10,-12) {$\texttt{search}(3)$};
    \node at (-6,-12) {$\texttt{search}(3)$};
    \node at (-2,-12) {$\texttt{search}(3)$};
    \node at (2,-12) {$\texttt{search}(3)$};
    \node at (6,-12) {$\texttt{search}(3)$};
    \node at (10,-12) {$\texttt{search}(3)$};
    \node at (14,-12) {$\texttt{search}(3)$};

    \node at (-14,-13.5) {$\emptyset$};
    \node at (-10,-13.5) {$\{2\}$};
    \node at (-6,-13.5) {$\{1\}$};
    \node at (-2,-13.5) {$\{1,2\}$};
    \node at (2,-13.5) {$\{0\}$};
    \node at (6,-13.5) {$\{0,2\}$};
    \node at (10,-13.5) {$\{0,1\}$};
    \node at (14,-13.5) {$\{0,1,2\}$};


    \path[draw,thick,->] (-12,-8-0.5) -- (-14,-12+0.5);
    \path[draw,thick,->] (-12,-8-0.5) -- (-10,-12+0.5);
    \path[draw,thick,->] (-4,-8-0.5) -- (-6,-12+0.5);
    \path[draw,thick,->] (-4,-8-0.5) -- (-2,-12+0.5);
    \path[draw,thick,->] (4,-8-0.5) -- (2,-12+0.5);
    \path[draw,thick,->] (4,-8-0.5) -- (6,-12+0.5);
    \path[draw,thick,->] (12,-8-0.5) -- (10,-12+0.5);
    \path[draw,thick,->] (12,-8-0.5) -- (14,-12+0.5);
\end{scope}
\end{tikzpicture}
\end{center}

\subsubsection{Método 2}

Otra forma de generar subconjuntos se basa en
la representación en bits de los enteros.
Cada subconjunto de un conjunto de $n$ elementos
se puede representar como una secuencia de $n$ bits,
que corresponde a un entero entre $0 \ldots 2^n-1$.
Los unos en la secuencia de bits indican
qué elementos están incluidos en el subconjunto.

La convención habitual es que
el último bit corresponde al elemento 0,
el penúltimo bit corresponde al elemento 1,
y así sucesivamente.
Por ejemplo, la representación en bits de 25
es 11001, que corresponde al subconjunto $\{0,3,4\}$.

El siguiente código recorre los subconjuntos
de un conjunto de $n$ elementos

\begin{lstlisting}
for (int b = 0; b < (1<<n); b++) {
    // process subset
}
\end{lstlisting}

El siguiente código muestra cómo podemos encontrar
los elementos de un subconjunto que corresponde a una secuencia de bits.
Al procesar cada subconjunto,
el código construye un vector que contiene los
elementos en el subconjunto.
\begin{lstlisting}
for (int b = 0; b < (1<<n); b++) {
    vector<int> subset;
    for (int i = 0; i < n; i++) {
        if (b&(1<<i)) subset.push_back(i);
    }
}
\end{lstlisting}

\section{Generación de permutaciones}

\index{permutación}

A continuación, consideramos el problema de generar
todas las permutaciones de un conjunto de $n$ elementos.
Por ejemplo, las permutaciones de $\{0,1,2\}$ son
$(0,1,2)$, $(0,2,1)$, $(1,0,2)$, $(1,2,0)$,
$(2,0,1)$ y $(2,1,0)$.
De nuevo, hay dos enfoques:
podemos usar recursión o recorrer las
permutaciones iterativamente.

\subsubsection{Método 1}

Al igual que los subconjuntos, las permutaciones se pueden generar
usando recursión.
La siguiente función \texttt{search}
recorre las permutaciones del conjunto $\{0,1,\ldots,n-1\}$.
La función construye un vector \texttt{permutation}
que contiene la permutación,
y la búsqueda comienza cuando la función se
llama sin parámetros.

\begin{lstlisting}
void search() {
    if (permutation.size() == n) {
        // process permutation
    } else {
        for (int i = 0; i < n; i++) {
            if (chosen[i]) continue;
            chosen[i] = true;
            permutation.push_back(i);
            search();
            chosen[i] = false;
            permutation.pop_back();
        }
    }
}
\end{lstlisting}

Cada llamada a la función agrega un nuevo elemento a
\texttt{permutation}.
La matriz \texttt{chosen} indica qué
elementos ya están incluidos en la permutación.
Si el tamaño de \texttt{permutation} es igual al tamaño del conjunto,
se ha generado una permutación.

\subsubsection{Método 2}

\index{next\_permutation@\texttt{next\_permutation}}

Otro método para generar permutaciones
es comenzar con la permutación
$\{0,1,\ldots,n-1\}$ y repetir
el uso de una función que construye la siguiente permutación
en orden creciente.
La biblioteca estándar de C++ contiene la función
\texttt{next\_permutation} que se puede usar para esto:

\begin{lstlisting}
vector<int> permutation;
for (int i = 0; i < n; i++) {
    permutation.push_back(i);
}
do {
    // process permutation
} while (next_permutation(permutation.begin(),permutation.end()));
\end{lstlisting}

\section{Backtracking}

\index{backtracking}

Un algoritmo de \key{backtracking}
comienza con una solución vacía
y extiende la solución paso a paso.
La búsqueda recursivamente
recorre todas las formas diferentes de cómo
se puede construir una solución.

\index{problema de la reina}

Como ejemplo, considere el problema de
calcular el número
de formas en que se pueden colocar $n$ reinas en
un tablero de ajedrez de $n \times n$ de modo que
ninguna de las dos reinas se ataque entre sí.
Por ejemplo, cuando $n=4$,
hay dos soluciones posibles:

\begin{center}
\begin{tikzpicture}[scale=.65]
  \begin{scope}
    \draw (0, 0) grid (4, 4);
    \node at (1.5,3.5) {\symqueen};
    \node at (3.5,2.5) {\symqueen};
    \node at (0.5,1.5) {\symqueen};
    \node at (2.5,0.5) {\symqueen};

    \draw (6, 0) grid (10, 4);
    \node at (6+2.5,3.5) {\symqueen};
    \node at (6+0.5,2.5) {\symqueen};
    \node at (6+3.5,1.5) {\symqueen};
    \node at (6+1.5,0.5) {\symqueen};

  \end{scope}
\end{tikzpicture}
\end{center}

El problema se puede resolver usando backtracking
colocando reinas en el tablero fila por fila.
Más precisamente, exactamente una reina
se colocará en cada fila de modo que ninguna reina ataque
a ninguna de las reinas colocadas antes.
Se ha encontrado una solución cuando todas
las $n$ reinas se han colocado en el tablero.

Por ejemplo, cuando $n=4$,
algunas soluciones parciales generadas por
el algoritmo de backtracking son las siguientes:

\begin{center}
\begin{tikzpicture}[scale=.55]
  \begin{scope}
    \draw (0, 0) grid (4, 4);

    \draw (-9, -6) grid (-5, -2);
    \draw (-3, -6) grid (1, -2);
    \draw (3, -6) grid (7, -2);
    \draw (9, -6) grid (13, -2);

    \node at (-9+0.5,-3+0.5) {\symqueen};
    \node at (-3+1+0.5,-3+0.5) {\symqueen};
    \node at (3+2+0.5,-3+0.5) {\symqueen};
    \node at (9+3+0.5,-3+0.5) {\symqueen};

    \draw (2,0) -- (-7,-2);
    \draw (2,0) -- (-1,-2);
    \draw (2,0) -- (5,-2);
    \draw (2,0) -- (11,-2);

    \draw (-11, -12) grid (-7, -8);
    \draw (-6, -12) grid (-2, -8);
    \draw (-1, -12) grid (3, -8);
    \draw (4, -12) grid (8, -8);
    \draw[white] (11, -12) grid (15, -8);
    \node at (-11+1+0.5,-9+0.5) {\symqueen};
    \node at (-6+1+0.5,-9+0.5) {\symqueen};
    \node at (-1+1+0.5,-9+0.5) {\symqueen};
    \node at (4+1+0.5,-9+0.5) {\symqueen};
    \node at (-11+0+0.5,-10+0.5) {\symqueen};
    \node at (-6+1+0.5,-10+0.5) {\symqueen};
    \node at (-1+2+0.5,-10+0.5) {\symqueen};
    \node at (4+3+0.5,-10+0.5) {\symqueen};

    \draw (-1,-6) -- (-9,-8);
    \draw (-1,-6) -- (-4,-8);
    \draw (-1,-6) -- (1,-8);
    \draw (-1,-6) -- (6,-8);

    \node at (-9,-13) {inválida};
    \node at (-4,-13) {inválida};
    \node at (1,-13) {inválida};
    \node at (6,-13) {válida};

  \end{scope}
\end{tikzpicture}
\end{center}
En el nivel inferior, las tres primeras configuraciones
son ilegales, porque las reinas se atacan entre sí.
Sin embargo, la cuarta configuración es válida
y puede extenderse a una solución completa colocando
dos reinas más en el tablero.
Solo hay una forma de colocar las dos reinas restantes.

\begin{samepage}
El algoritmo se puede implementar de la siguiente manera:
\begin{lstlisting}
void search(int y) {
    if (y == n) {
        count++;
        return;
    }
    for (int x = 0; x < n; x++) {
        if (column[x] || diag1[x+y] || diag2[x-y+n-1]) continue;
        column[x] = diag1[x+y] = diag2[x-y+n-1] = 1;
        search(y+1);
        column[x] = diag1[x+y] = diag2[x-y+n-1] = 0;
    }
}
\end{lstlisting}
\end{samepage}
La búsqueda comienza llamando a \texttt{search(0)}.
El tamaño del tablero es $n \times n$,
y el código calcula el número de soluciones
a \texttt{count}.

El código asume que las filas y columnas
del tablero están numeradas de 0 a $n-1$.
Cuando se llama a la función \texttt{search} con
el parámetro $y$,
coloca una reina en la fila $y$
y luego se llama a sí misma con el parámetro $y+1$.
Luego, si $y=n$, se ha encontrado una solución
y la variable \texttt{count} se incrementa en uno.

El arreglo \texttt{column} lleva un registro de las columnas
que contienen una reina,
y los arreglos \texttt{diag1} y \texttt{diag2}
llevan un registro de las diagonales.
No está permitido agregar otra reina a una
columna o diagonal que ya contiene una reina.
Por ejemplo, las columnas y diagonales de
el tablero de $4 \times 4$ se numeran de la siguiente manera:

\begin{center}
\begin{tikzpicture}[scale=.65]
  \begin{scope}
    \draw (0-6, 0) grid (4-6, 4);
    \node at (-6+0.5,3.5) {$0$};
    \node at (-6+1.5,3.5) {$1$};
    \node at (-6+2.5,3.5) {$2$};
    \node at (-6+3.5,3.5) {$3$};
    \node at (-6+0.5,2.5) {$0$};
    \node at (-6+1.5,2.5) {$1$};
    \node at (-6+2.5,2.5) {$2$};
    \node at (-6+3.5,2.5) {$3$};
    \node at (-6+0.5,1.5) {$0$};
    \node at (-6+1.5,1.5) {$1$};
    \node at (-6+2.5,1.5) {$2$};
    \node at (-6+3.5,1.5) {$3$};
    \node at (-6+0.5,0.5) {$0$};
    \node at (-6+1.5,0.5) {$1$};
    \node at (-6+2.5,0.5) {$2$};
    \node at (-6+3.5,0.5) {$3$};

    \draw (0, 0) grid (4, 4);
    \node at (0.5,3.5) {$0$};
    \node at (1.5,3.5) {$1$};
    \node at (2.5,3.5) {$2$};
    \node at (3.5,3.5) {$3$};
    \node at (0.5,2.5) {$1$};
    \node at (1.5,2.5) {$2$};
    \node at (2.5,2.5) {$3$};
    \node at (3.5,2.5) {$4$};
    \node at (0.5,1.5) {$2$};
    \node at (1.5,1.5) {$3$};
    \node at (2.5,1.5) {$4$};
    \node at (3.5,1.5) {$5$};
    \node at (0.5,0.5) {$3$};
    \node at (1.5,0.5) {$4$};
    \node at (2.5,0.5) {$5$};
    \node at (3.5,0.5) {$6$};

    \draw (6, 0) grid (10, 4);
    \node at (6.5,3.5) {$3$};
    \node at (7.5,3.5) {$4$};
    \node at (8.5,3.5) {$5$};
    \node at (9.5,3.5) {$6$};
    \node at (6.5,2.5) {$2$};
    \node at (7.5,2.5) {$3$};
    \node at (8.5,2.5) {$4$};
    \node at (9.5,2.5) {$5$};
    \node at (6.5,1.5) {$1$};
    \node at (7.5,1.5) {$2$};
    \node at (8.5,1.5) {$3$};
    \node at (9.5,1.5) {$4$};
    \node at (6.5,0.5) {$0$};
    \node at (7.5,0.5) {$1$};
    \node at (8.5,0.5) {$2$};
    \node at (9.5,0.5) {$3$};

    \node at (-4,-1) {\texttt{column}};
    \node at (2,-1) {\texttt{diag1}};
    \node at (8,-1) {\texttt{diag2}};

  \end{scope}
\end{tikzpicture}
\end{center}

Sea $q(n)$ el número de formas
de colocar $n$ reinas en un tablero de ajedrez de $n \times n$.
El algoritmo de retroceso anterior
nos dice que, por ejemplo, $q(8)=92$.
Cuando $n$ aumenta, la búsqueda se vuelve rápidamente lenta,
porque el número de soluciones aumenta
exponencialmente.
Por ejemplo, calcular $q(16)=14772512$
utilizando el algoritmo anterior ya lleva aproximadamente un minuto
en una computadora moderna\footnote{No hay una forma conocida para
calcular eficientemente valores mayores de $q(n)$. El récord actual es
$q(27)=234907967154122528$, calculado en 2016 \cite{q27}.}.

\section{Poda de la búsqueda}

A menudo podemos optimizar el retroceso
podando el árbol de búsqueda.
La idea es agregar ''inteligencia'' al algoritmo
para que se dé cuenta lo antes posible
si una solución parcial no se puede extender
a una solución completa.
Estas optimizaciones pueden tener un tremendo
efecto en la eficiencia de la búsqueda.

Consideremos el problema
de calcular el número de caminos
en una cuadrícula de $n \times n$ desde la esquina superior izquierda
hasta la esquina inferior derecha, de modo que el
camino visite cada cuadrado exactamente una vez.
Por ejemplo, en una cuadrícula de $7 \times 7$,
hay 111712 caminos de este tipo.
Uno de los caminos es el siguiente:



\begin{center}
\begin{tikzpicture}[scale=.55]
  \begin{scope}
    \draw (0, 0) grid (7, 7);
    \draw[thick,->] (0.5,6.5) -- (0.5,4.5) -- (2.5,4.5) --
          (2.5,3.5) -- (0.5,3.5) -- (0.5,0.5) --
          (3.5,0.5) -- (3.5,1.5) -- (1.5,1.5) --
          (1.5,2.5) -- (4.5,2.5) -- (4.5,0.5) --
          (5.5,0.5) -- (5.5,3.5) -- (3.5,3.5) --
          (3.5,5.5) -- (1.5,5.5) -- (1.5,6.5) --
          (4.5,6.5) -- (4.5,4.5) -- (5.5,4.5) --
          (5.5,6.5) -- (6.5,6.5) -- (6.5,0.5);
  \end{scope}
\end{tikzpicture}
\end{center}

Nos centramos en el caso $7 \times 7$,
porque su nivel de dificultad es apropiado para nuestras necesidades.
Comenzamos con un algoritmo de retroceso directo,
y luego lo optimizamos paso a paso usando observaciones
de cómo se puede podar la búsqueda.
Después de cada optimización, medimos el tiempo de ejecución
del algoritmo y el número de llamadas recursivas,
para que veamos claramente el efecto de cada
optimización en la eficiencia de la búsqueda.

\subsubsection{Algoritmo básico}

La primera versión del algoritmo no contiene
ninguna optimización. Simplemente usamos retroceso para generar
todos los caminos posibles desde la esquina superior izquierda hasta
la esquina inferior derecha y contamos el número de estos caminos.

\begin{itemize}
\item
tiempo de ejecución: 483 segundos
\item
número de llamadas recursivas: 76 mil millones
\end{itemize}

\subsubsection{Optimización 1}

En cualquier solución, primero movemos un paso
hacia abajo o hacia la derecha.
Siempre hay dos caminos que 
son simétricos
respecto a la diagonal de la cuadrícula
después del primer paso.
Por ejemplo, los siguientes caminos son simétricos:

\begin{center}
\begin{tabular}{ccc}
\begin{tikzpicture}[scale=.55]
  \begin{scope}
    \draw (0, 0) grid (7, 7);
    \draw[thick,->] (0.5,6.5) -- (0.5,4.5) -- (2.5,4.5) --
          (2.5,3.5) -- (0.5,3.5) -- (0.5,0.5) --
          (3.5,0.5) -- (3.5,1.5) -- (1.5,1.5) --
          (1.5,2.5) -- (4.5,2.5) -- (4.5,0.5) --
          (5.5,0.5) -- (5.5,3.5) -- (3.5,3.5) --
          (3.5,5.5) -- (1.5,5.5) -- (1.5,6.5) --
          (4.5,6.5) -- (4.5,4.5) -- (5.5,4.5) --
          (5.5,6.5) -- (6.5,6.5) -- (6.5,0.5);
  \end{scope}
\end{tikzpicture}
& \hspace{20px}
& 
\begin{tikzpicture}[scale=.55]
  \begin{scope}[yscale=1,xscale=-1,rotate=-90]
    \draw (0, 0) grid (7, 7);
    \draw[thick,->] (0.5,6.5) -- (0.5,4.5) -- (2.5,4.5) --
          (2.5,3.5) -- (0.5,3.5) -- (0.5,0.5) --
          (3.5,0.5) -- (3.5,1.5) -- (1.5,1.5) --
          (1.5,2.5) -- (4.5,2.5) -- (4.5,0.5) --
          (5.5,0.5) -- (5.5,3.5) -- (3.5,3.5) --
          (3.5,5.5) -- (1.5,5.5) -- (1.5,6.5) --
          (4.5,6.5) -- (4.5,4.5) -- (5.5,4.5) --
          (5.5,6.5) -- (6.5,6.5) -- (6.5,0.5);
  \end{scope}
\end{tikzpicture}
\end{tabular}
\end{center}

Por lo tanto, podemos decidir que siempre nos movemos primero
un paso hacia abajo (o hacia la derecha),
y finalmente multiplicamos el número de soluciones por dos.

\begin{itemize}
\item
tiempo de ejecución: 244 segundos
\item
número de llamadas recursivas: 38 mil millones
\end{itemize}

\subsubsection{Optimización 2}

Si el camino llega a la casilla inferior derecha
antes de haber visitado todas las demás casillas de la cuadrícula,
es claro que
no será posible completar la solución.
Un ejemplo de esto es el siguiente camino:

\begin{center}
\begin{tikzpicture}[scale=.55]
  \begin{scope}
    \draw (0, 0) grid (7, 7);
    \draw[thick,->] (0.5,6.5) -- (0.5,4.5) -- (2.5,4.5) --
          (2.5,3.5) -- (0.5,3.5) -- (0.5,0.5) --
          (3.5,0.5) -- (3.5,1.5) -- (1.5,1.5) --
          (1.5,2.5) -- (4.5,2.5) -- (4.5,0.5) --
          (6.5,0.5);
  \end{scope}
\end{tikzpicture}
\end{center}
Usando esta observación, podemos terminar la búsqueda
inmediatamente si llegamos a la casilla inferior derecha demasiado pronto.
\begin{itemize}
\item
tiempo de ejecución: 119 segundos
\item
número de llamadas recursivas: 20 mil millones
\end{itemize}

\subsubsection{Optimización 3}

Si el camino toca una pared
y puede girar a la izquierda o a la derecha,
la cuadrícula se divide en dos partes
que contienen casillas no visitadas.
Por ejemplo, en la siguiente situación,
el camino puede girar a la izquierda o a la derecha:

\begin{center}
\begin{tikzpicture}[scale=.55]
  \begin{scope}
    \draw (0, 0) grid (7, 7);
    \draw[thick,->] (0.5,6.5) -- (0.5,4.5) -- (2.5,4.5) --
          (2.5,3.5) -- (0.5,3.5) -- (0.5,0.5) --
          (3.5,0.5) -- (3.5,1.5) -- (1.5,1.5) --
          (1.5,2.5) -- (4.5,2.5) -- (4.5,0.5) --
          (5.5,0.5) -- (5.5,6.5);
  \end{scope}
\end{tikzpicture}
\end{center}
En este caso, ya no podemos visitar todas las casillas,
por lo que podemos terminar la búsqueda.
Esta optimización es muy útil:

\begin{itemize}
\item
tiempo de ejecución: 1,8 segundos
\item
número de llamadas recursivas: 221 millones
\end{itemize}

\subsubsection{Optimización 4}

La idea de la Optimización 3
se puede generalizar:
si el camino no puede continuar hacia adelante
pero puede girar a la izquierda o a la derecha,
la cuadrícula se divide en dos partes
que ambas contienen casillas no visitadas.
Por ejemplo, considere el siguiente camino:
\begin{center}
\begin{tikzpicture}[scale=.55]
  \begin{scope}
    \draw (0, 0) grid (7, 7);
    \draw[thick,->] (0.5,6.5) -- (0.5,4.5) -- (2.5,4.5) --
          (2.5,3.5) -- (0.5,3.5) -- (0.5,0.5) --
          (3.5,0.5) -- (3.5,1.5) -- (1.5,1.5) --
          (1.5,2.5) -- (4.5,2.5) -- (4.5,0.5) --
          (5.5,0.5) -- (5.5,4.5) -- (3.5,4.5);
  \end{scope}
\end{tikzpicture}
\end{center}
Está claro que ya no podemos visitar todas las casillas,
por lo que podemos terminar la búsqueda.
Después de esta optimización, la búsqueda es
muy eficiente:

\begin{itemize}
\item
tiempo de ejecución: 0.6 segundos
\item
número de llamadas recursivas: 69 millones
\end{itemize}

~\\
Ahora es un buen momento para dejar de optimizar
el algoritmo y ver lo que hemos logrado.
El tiempo de ejecución del algoritmo original
era de 483 segundos,
y ahora después de las optimizaciones,
el tiempo de ejecución es de solo 0.6 segundos.
Por lo tanto, el algoritmo se volvió casi 1000 veces
más rápido después de las optimizaciones.

Este es un fenómeno habitual en el backtracking,
porque el árbol de búsqueda suele ser grande
e incluso observaciones simples pueden
podar la búsqueda de forma eficaz.
Son especialmente útiles las optimizaciones que
se producen durante los primeros pasos del algoritmo,
es decir, en la parte superior del árbol de búsqueda.

\section{Encuentro en el medio}

\index{encuentro en el medio}

\key{Encuentro en el medio} es una técnica
en la que el espacio de búsqueda se divide en
dos partes de aproximadamente igual tamaño.
Se realiza una búsqueda separada
para ambas partes,
y finalmente se combinan los resultados de las búsquedas.

La técnica se puede utilizar
si hay una forma eficiente de combinar las
resultados de las búsquedas.
En tal situación, las dos búsquedas pueden requerir menos
tiempo que una búsqueda grande.
Típicamente, podemos convertir un factor de $2^n$
en un factor de $2^{n/2}$ usando la técnica de encuentro en el
medio.

Como ejemplo, considere un problema en el que
se nos da una lista de $n$ números y
un número $x$,
y queremos saber si es posible
elegir algunos números de la lista para que
su suma sea $x$.
Por ejemplo, dada la lista $[2,4,5,9]$ y $x=15$,
podemos elegir los números $[2,4,9]$ para obtener $2+4+9=15$.
Sin embargo, si $x=10$ para la misma lista,
no es posible formar la suma.

Un algoritmo simple para el problema es
recorrer todos los subconjuntos de los elementos y
comprobar si la suma de alguno de los subconjuntos es $x$.
El tiempo de ejecución de tal algoritmo es $O(2^n)$,
porque hay $2^n$ subconjuntos.
Sin embargo, utilizando la técnica de encuentro en el medio,
podemos lograr un algoritmo más eficiente de tiempo $O(2^{n/2})$\footnote{Esta
idea fue introducida en 1974 por E. Horowitz y S. Sahni \cite{hor74}.}.
Tenga en cuenta que $O(2^n)$ y $O(2^{n/2})$ son diferentes
complejidades porque $2^{n/2}$ es igual a $\sqrt{2^n}$.

La idea es dividir la lista en
dos listas $A$ y $B$ de modo que ambas
listas contengan aproximadamente la mitad de los números.
La primera búsqueda genera todos los subconjuntos
de $A$ y almacena sus sumas en una lista $S_A$.
De manera correspondiente, la segunda búsqueda crea
una lista $S_B$ de $B$.
Después de esto, basta con comprobar si es posible
elegir un elemento de $S_A$ y otro
elemento de $S_B$ de modo que su suma sea $x$.
Esto es posible exactamente cuando hay una forma de
formar la suma $x$ usando los números de la lista original.

Por ejemplo, suponga que la lista es $[2,4,5,9]$ y $x=15$.
Primero, dividimos la lista en $A=[2,4]$ y $B=[5,9]$.
Después de esto, creamos listas
$S_A=[0,2,4,6]$ y $S_B=[0,5,9,14]$.
En este caso, la suma $x=15$ es posible de formar,
porque $S_A$ contiene la suma $6$,
$S_B$ contiene la suma $9$, y $6+9=15$.
Esto corresponde a la solución $[2,4,9]$.

Podemos implementar el algoritmo de modo que
su complejidad temporal sea $O(2^{n/2})$.
Primero, generamos listas \emph{ordenadas} $S_A$ y $S_B$,
lo que se puede hacer en tiempo $O(2^{n/2})$ utilizando una técnica similar a la fusión.
Después de esto, dado que las listas están ordenadas,
podemos comprobar en tiempo $O(2^{n/2})$ si
la suma $x$ se puede crear a partir de $S_A$ y $S_B$.