En el tema anterior se analizó el paradigma de recursividad para el diseño de algoritmos y en el capítulo 1 se presentó uno más sencillo: el de búsqueda exhaustiva, que no hace más que explorar todas las posibles soluciones a un problema, con un costo usualmente enorme. En el caso del problema del regalo de Arcadio, el algoritmo simplemente consideraba una por una todas las combinaciones posibles de obsequios para Úrsula y elegía el mejor. Los algoritmos de búsqueda exhaustiva frecuentemente son de tiempo exponencial. Es necesario ser ingenioso para obtener algoritmos eficientes, pero no hay que olvidar que en ocasiones la búsqueda exhaustiva es la única posibilidad para resolver un problema.
Considérese el problema de colorear una gráfica con el menor número de colores. Un algoritmo muy sencillo sería simplemente probar todas las coloraciones posibles; sin embargo, esto tomaría tiempo exponencial. Por ejemplo, supóngase que se quieren probar todas las coloraciones posibles con cuatro colores en una gráfica de n vértices. Escójanse un vértice y uno de los cuatro colores para éste. Para el siguiente vértice se tienen otra vez cuatro posibilidades, y así sucesivamente. El número total de posibilidades a explorar es 4n.
Desafortunadamente, para el problema de coloración, no se sabe si existe un algoritmo mejor que éste; se trata de un problema NP-completo (véase el tema 1). No se sabe siquiera si existe un algoritmo eficiente (polinomial) para decidir si un mapa requiere de los cuatro colores, o si se puede colorear con tres. Sin embargo, ya se ha descrito un algoritmo eficiente para cuando no se exige ser tan rigurosos, y es suficiente colorear un mapa con seis colores.
