Técnicas de construcción de algoritmos (A3C34A2D01)

Una de las mayores dificultades a la hora de resolver un problema con un ordenador no es la escritura del programa sino el paso previo: la construcción del algoritmo, es decir su diseño y su definición. Para ello, no basta con conocer las herramientas que existen para su especificación (como el pseudocódigo o los diagramas de flujo) sino que es indispensable identificar el cuerpo del algoritmo, esto es, los datos de entrada y de salida, y la secuencia de instrucciones que hay que realizar para obtener los resultados deseados. El principal inconveniente es que no se pueden aplicar fórmulas ni recetas por lo que se requieren ciertas dosis de creatividad para buscar soluciones. No obstante, podemos beneficiarnos de algunas técnicas o estrategias que facilitan la tarea cuando la solución del problema no es trivial ni sencilla.

La primera de ellas es la del uso de la abstracción para que, de forma jerárquica, y mediante refinamientos sucesivos, se pueda descomponer un problema en subproblemas. De este modo, según evoluciona el diseño del algoritmo, cada nivel de su estructura representa un refinamiento en el nivel de abstracción. Por ejemplo, si salimos de ver una película del cine y nos encontramos con alguien que nos pregunta de qué iba la película, le haremos un resumen de la misma. En ese momento, se está realizando un proceso de abstracción porque se destacan las principales ideas del argumento y se ignoran detalles de escenas concretas. Si después nos pregunta por una subtrama o similar, profundizaremos en ella, dando más detalles de la subtrama e ignorando las demás. De esta forma, vamos contando la película mediante un proceso “jerárquico”.

En el contexto de la programación, la abstracción puede ser de distintos tipos: la evolución de los lenguajes de programación depende del nivel de abstracción del ordenador; y los paradigmas de programación surgen al aplicar la abstracción a los datos y/o a las instrucciones. Estos temas se tratan con más detalle posteriormente. Ahora es importante describir cómo hacer uso de la abstracción para realizar la descomposición de un problema complejo en subproblemas más simples. De esta forma, se puede abordar la resolución de cada uno de ellos de forma independiente delos demás, de forma similar a cuando cuentas una película. Precisamente, esta estrategia  consistente en descomponer un problema en subproblemas es la base de la técnica “Divide y Vencerás”, utilizada para el diseño de algoritmos “rápidos” de ordenación de multiplicación de enteros grandes o para multiplicar matrices. Un poco más adelante se explica con más profundidad esta estrategia.

Otra técnica, muy útil para resolver problemas de optimización, esto es, aquellos en los que se pretende maximizar o minimizar algún aspecto de estos, es la técnica voraz (o greedy, en inglés). Un ejemplo típico en el que se suele aplicar esta técnica en la vida real es el de la devolución de cambio con el menor número de monedas posible. La estrategia voraz consiste en elegir lo mejor en cada momento, en base a la información de la que se dispone, de forma que las decisiones son inamovibles. Por ejemplo, en el caso de la devolución del cambio, en cada momento se elige la moneda de mayor valor disponible que no supere la cantidad a devolver. Para poder aplicar la estrategia voraz, la solución del problema debe cumplir dos requisitos: ser un subconjunto de un conjunto de elementos (en la devolución del cambio, la solución es un subconjunto de las monedas disponibles) y poder construirse por etapas (la elección de una moneda constituye una etapa). En general, los algoritmos voraces suelen seguir el esquema que se ilustra en el listado siguiente:

Como ves, en el algoritmo se distinguen una serie de elementos:

• Objetivo para optimizar
• Candidatos a formar parte de la solución
• Candidatos seleccionados
• Criterio de solución, que decide si los elementos seleccionados constituyen la solución al problema
• Criterio de factibilidad, que decide si un candidato se
  puede incluir en la solución
• Criterio de selección, que elige el mejor candidato de los
  posibles.

En el ejemplo de la devolución del cambio, el objetivo es minimizar el número de monedas que forman parte de la solución; los candidatos son las monedas de las que disponemos; el criterio de solución es que el valor de las monedas seleccionadas coincida con el valor del cambio; el de factibilidad es el no considera las monedas que, al incluirlas en la solución, superan el valor del cambio; y el criterio de selección elige la moneda de mayor valor entre las disponibles. Esta estrategia es óptima con nuestro sistema de monedas. Sin embargo, si las monedas de 10 céntimos fueran de 11, por ejemplo, y no existieran las monedas de 2 céntimos, la estrategia no es óptima. Por ejemplo, para devolver 15 céntimos, usaría 1 de 11 y 4 de 1, 5 monedas en total, mientras que la mejor solución sería devolver 3 monedas de 5.

Los algoritmos voraces suelen ser muy sencillos y rápidos (complejidad polinomial). Por eso, aunque la solución óptima no está garantizada en algunos casos, se utilizan porque se prefiere una solución buena en poco tiempo que la mejor en mucho tiempo. Otro problema típico en el que se aplica esta técnica es el de la mochila. En él se tiene una mochila de capacidad M(>0) y N(>0) objetos fraccionables (es decir, que se pueden partir) con un peso y un valor determinado. El objetivo es llenar la mochila maximizando su valor. Como ves, se ajusta a su resolución voraz: es un problema de optimización y la solución es un subconjunto de los objetos, que se puede construir por etapas. Además, se pueden identificar los elementos voraces:

• Objetivo: maximizar el valor de la mochila.
• Candidatos: los N objetos.
• Candidatos seleccionados (S): los que se han incluido en la mochila.
• Criterio de solución: el peso de los elementos en S igual a la capacidad M.
• Criterio de factibilidad: no sobrepasar la capacidad de la mochila al incluir en S el nuevo elemento seleccionado.
• Criterio de selección: elegir el objeto de mayor relación valor/peso, que proporciona una solución óptima.

Otros problemas en los que la estrategia voraz se aplica con éxito son los de la planificación de tareas para maximizar rendimiento o en los de recorrido de una serie de puntos con la menor distancia posible.