De lo fácil a lo imposible (primera parte)

Los expertos en computación tienen clasificados los problemas por su dificultad computacional, es decir, qué tán eficiente es resolverlos con una computadora. Cada problema puede tener diversas soluciones, pero sólo cuentan las mejores soluciones, no las peores.

Un primer ejemplo simple es la búsqueda de información. Al busccar un nombre en una lista se puede proceder revisando uno por uno hasta encontrarlo. Si hay 1000 nombres lo más que podemos tardar es 1000 pasos (mala suerte) o 1 paso en el mejor casos. Por término medio esperamos hacer alrededor de 500 pasos en cada búsqueda.  Esto se conoce como búsqueda secuencial.

Si los nombres están en orden alfabético es mucho más fácil. Miramos en la posición del centro. Si no está, enconces si el que buscamos va antes que el del centro continuamos la búsqueda en la primera mitad. Si es mayor al central, buscamos en la segunda mitad. Cada paso se descarta la mitad de los elementos. Así, si tenemos los mismos 1000, en el primer paso dejamos a un lado 500, luego 250, 125, hasta que nos queda 2 y la búsqueda es inmediata. En menos de 10 pasos encontraremos el nombre o determinaremos que no está. Esto se conoce como búsqueda binaria.

Las búsquedas secuencial y binaria son estrategias distintas. Cada estrategia para resolver un problema se llama algoritmo, que es la secuencia de pasos para lograr un fin. Se trata de una receta, en términos coloquiales. Siempre es posible encontrar peores algoritmos. Por ejemplo, busquemos el nombre en la lista de 1000, seleccionando posiciones al azar. Seguramente algún día lo encontraremos, pero no hay garantía de cuándo (y nunca estaremos seguros de que no está). Por supuesto, los que interesan son los mejores algoritmos, no los peores.

Para aplicar algoritmos eficientes de búsqueda se requiere que la información esté ordenada, lo que nos lleva a muchos algoritmos que ordenan la información, algoritmos de ordenamiento. Es más rápido buscar que ordenar, por lo que el problema de búsqueda es menos complejo que el de ordenamiento. Así, cada problema tiene su propia complejidad, medida en el tiempo que invierte el mejor algoritmo que lo resuelve.

En el problema de ordenamiento (una tarea de lo más frecuente en todas partes), hay muchas maneras de hacerlo. Se pueden revisar los objetos para localizar el menor y ponerlo al inicio. Luego se revisan los que quedan, buscando el segundo menor y se pone en segunda posición. Así hasta terminar. Este algoritmo se llama selección y para 1000 objetos requiere cerca de un millón de pasos. Claro, una computadora ahce un millon de pasos bastante rápido actualmente. Otra forma de ordenar es poner los mayores en la seguna mitad y los menores en la primera parte. Luego se ordena cada parte repitiendo el procedimiento de partir en dos. Este algoritmo se llama Quick sort (ordenamiento rápido) y, en efecto, es bastante rápido, ordena 1000 elementos en menos de 10 mil pasos.

Problemas mucho más complejos son, por ejemplo, los de ruta mínima. Dadas dos direcciones en una ciudad, ¿cuál es la ruta más rápida? Dadas dos ciudades en el país, ¿cuál es la ruta de carreteras más barata? ¿Cuál es la ruta de carreteras más rápida? Este problema en general es más complejo que el de ordenamiento pero tampoco es demsiado difícil. Por otra parte, si lo que queremos es encontrar u na ruta que visite cada ciudad una sóla vez, recorriendo todas con el costo mínimo y terminando en la ciudad inicial, ahí sí estamos ante algo difícil. Hasta nombre tiene: el problema del agente viajero. Para un mapa general de solo 10 ciudades este problema ya se tarda más de 3 millones de pasos, no se conoce un algoritmo eficiente.

Estos tres ejemplos bastan para decir que todos los problemas se pueden clasificar en fáciles (buscar, ordenar y ruta mínima), difíciles (agente viajero), muy difíciles (jugar ajedrez o damas) e imposibles. De esta última categoría sólo se conocen ejemplos teóricos, por fortuna todo problema práctico es soluble, siempre que haya suficiente tiempo para reslverlo. De no haberlo, al menos se pueden aproximar soluciones. En otra oportunidad, nos referiremos a los problemas imposibles.