Búsqueda Completa (II): Ejemplos más avanzados

En el manual anterior hemos explicado las ideas principales de las técnicas de búsqueda completa y backtracking. La mayoría de problemas son susceptibles a ser atacados de esta forma: escribir un programa que genere todas las configuraciones posibles es generalmente fácil y suele ser suficiente para obtener la respuesta correcta. El inconveniente que hay es la gran ineficiencia que supone generar todas las opciones: en problemas con soluciones más eficientes, un programa que haga una búsqueda completa solo pasará los casos con tamaños de entrada muy pequeños, lo que en un concurso se traduce en obtener pocos puntos (o incluso ninguno). Sin embargo, sigue siendo bastante útil poder escribir un programa que te de la respuesta correcta aunque solo valga para casos pequeños: así puedes comprobar que otro programa con otra solución más eficiente funcione correctamente. Además, en muchos problemas ver la respuesta para casos particulares puede servir de inspiración para encontrar la solución general.

Hay problemas que sí están pensados para resolverse mediante la técnica de búsqueda completa, aunque los que aparecen en concursos normalmente requieren hacer ciertas observaciones que optimicen la búsqueda. Aquí incluimos dos problemas (el primero más fácil y el segundo más difícil) de concursos internacionales que utilizan esta idea. Recomendamos pensarlos un poco antes de leer la solución.

Ejemplo 1 (IOI 1998, modificado):

Hay $N  (N \leq 10^9)$ lámparas, numeradas de $1$ a $N$, que inicialmente están encendidas (ON). Hay 4 botones que permiten cambiar los estados de las lámparas:

• Botón 1: Invierte los estados de todas las lámparas (de ON a OFF y de OFF a ON)

• Botón 2: Invierte los estados de las lámparas con número par.

• Botón 3: Invierte los estados de las lámparas con número impar.

• Botón 4: Invierte los estados de las lámparas cuyo número es de la forma $3k+1$, para un entero no negativo $k$. (Es decir, lámparas 1, 4, 7…)

Hay un contador $C$ de cuántas veces se ha pulsado algún botón desde el principio. Dado $C$ $(C \leq 10^9)$ y dada la información del estado final de algunas $(\leq 10^5)$ lámparas (es decir, para algunas lámparas se conoce si después de las $C$ operaciones esa lámpara está ON o OFF), se pide contar el número de estados finales posibles de todas las lámparas que son consistentes con la información dada. (Click aquí para el enunciado original.)

Ejemplo 2 (ICPC World Finals 2012):

Se da un grafo dirigido (aquí puedes aprender lo que significa) $G$ con \(n\) \((n \leq 75)\) vértices que cumple la propiedad de que entre cada par de vértices hay una (y solo una) arista (en una de las dos direcciones). Encontrar un conjunto de vértices $S$ de tamaño mínimo tal que para todo vértice $v$ de $G$, o bien $v$ está en $S$ o bien hay una arista desde un elemento de $S$ hacia $v$.   (Click aquí para el enunciado original, que incluye ejemplos de entrada y salida)
 

Solución Ejemplo 1:

Una búsqueda completa directa tendría una complejidad de $\mathcal{O}(4^C \cdot C \cdot N)$ (hay $4^C$ posibles formas de pulsar los botones $C$ veces, y procesar cada una de ellas directamente requiere $C \cdot N$ operaciones). Esta complejidad es absolutamente inapropiada para los valores que pueden tomar $C$ y $N$. Se puede mejorar mucho con las siguientes tres observaciones:

1. El orden en el que se pulsan los botones no importa.

2. Pulsar dos veces un botón es lo mismo que no pulsarlo.

3. El patrón de lámparas encendidas y apagadas se repite cada 6 lámparas.

Utilizando las observaciones 1 y 2, vemos que sólo tenemos que tratar $2^4 = 16$ estados posibles en los que estén las lámparas. De hecho, utilizando que pulsar dos de los primeros tres botones causa el mismo efecto que pulsar el otro, vemos que sólo hay $8$ estados posibles en realidad. El problema, pues, se reduce a ver a cuáles de esos estados se puede llegar con $C$ pulsaciones de botones y que sean consistentes con la información de las lámparas que tenemos. No es complicado ver que si $C \geq 3$ se puede conseguir cualquier combinación de pulsaciones, y los casos $C = 1, 2$ se pueden tratar por separado. Para tener en cuenta la información que tenemos de algunas de las lámparas, la tercera observación nos indica que sólo nos tenemos que fijar en el resto al dividir por $6$ de los números de las lámparas.

Implementar una solución a este problema es un buen ejercicio para practicar con máscaras de bits: podemos expresar los estados de las 6 lámparas con 6 bits y las transformaciones de los botones con máscaras para tener un programa corto.

Solución Ejemplo 2:

La observación clave en este problema es la siguiente: para los valores de $n$ que nos dan \( (n \leq 75) \) siempre existe un conjunto de tamaño como mucho $6$. Más generalmente, se cumple lo siguiente:

Sea \( f(n) \) el menor número tal que para cualquier dígrafo de n vértices que cumpla la hipótesis del enunciado existe un conjunto solución con \( f(n) \) elementos. Entonces

\[ f(n) \leq f\left(\left\lfloor\frac{n-1}{2}\right\rfloor\right)+1 \]

Demostración: Utilizaremos que existe un vértice con al menos \( \left\lceil\frac{n-1}{2}\right\rceil \) aristas saliendo de él. Esto se debe a que el número total de aristas es \( \binom{n}{2} = \frac{(n(n-1))}{2} \), y si \( d(i) \) es el número de aristas salientes del i-ésimo vértice, tenemos que

\[ \sum_{i=1}^n d(i) = \frac{n(n-1)}{2} \]

y por tanto el máximo de los \(d(i)\) tiene que ser al menos \(\frac{n-1}{2}\) para que se cumpla la igualdad. Si retiramos este vértice y todos a los que se llega por una arista a través de él, tenemos un digrafo de como máximo \(\frac{n-1}{2}\) vértices que también cumple la hipótesis del enunciado, por lo que puede ser cubierto por un conjunto de \(f\left(\left\lfloor\frac{n-1}{2}\right\rfloor\right)\) vértices (se ve fácilmente que $f$ es creciente, así que esto es cierto aunque el número de vértices sea menor que \(\frac{n-1}{2}\)). Por tanto, añadiendo a este conjunto el vértice que habíamos seleccionado tenemos todo el dígrafo cubierto con un conjunto de \(f\left(\left\lfloor\frac{n-1}{2}\right\rfloor\right)+1\) elementos.

Ahora vemos que \(f(75) \leq f(37) + 1 \leq f(18) + 2 \leq f(8) + 3 \leq f(3) + 4 \leq f(1) + 5 = 6\), Esta observación nos permite aplicar la técnica de búsqueda completa: comprobamos todas los conjuntos con 1, 2, 3, 4, 5 vértices (para un total de \(\binom{75}{1} + \ldots + \binom{75}{5} \approx 2\cdot10^7\) posibilidades en el peor caso, que son razonables porque comprobar cada una se puede hacer rápidamente). Si no encontramos ninguna solución, sabemos que existe una con $6$ vértices: comprobar todos los conjuntos de $6$ vértices es bastante costoso, pero por suerte la demostración de que $6$ vértices siempre valen nos indica cómo construir uno: si vamos cogiendo los vértices con mayor número de aristas saliendo de ellos y considerando el grafo restante eliminando los vértices que ya controlamos recursivamente obtenemos siempre una solución.

Ejercicio: Si no comprobamos primero los subconjuntos de tamaño $1, 2, 3, 4, 5$ y vorazmente hacemos la solución recursiva de ir cogiendo los vértices de los que salen más aristas hasta quedarnos sin vértices, ¿llegamos a la solución correcta?