Técnicas de Diseño de Algoritmos

¿Qué es un algoritmo? 

Un algoritmo es un procedimiento para resolver un problema particular en un número finito de pasos para una entrada de tamaño finito. 
Los algoritmos se pueden clasificar de varias maneras. Están: 
 

1. Método de implementación
2. Método de diseño
3. Enfoques de diseño
4. Otras clasificaciones

En este artículo, se discuten los diferentes algoritmos en cada método de clasificación. 

Clasificación por método de implementación: existen principalmente tres categorías principales en las que se puede nombrar un algoritmo en este tipo de clasificación. Están: 
 

1. Recursión o iteración: un algoritmo recursivo es un algoritmo que se llama a sí mismo una y otra vez hasta que se logra una condición base, mientras que los algoritmos iterativos usan bucles y/o estructuras de datos como pilas , colas para resolver cualquier problema. Cada solución recursiva se puede implementar como una solución iterativa y viceversa. 
   Ejemplo: La Torre de Hanoi se implementa de forma recursiva, mientras que el problema Stock Span se implementa de forma iterativa.
2. Exacto o Aproximado: Los algoritmos que son capaces de encontrar una solución óptima para cualquier problema se conocen como algoritmo exacto. Para todos aquellos problemas, donde no es posible encontrar la solución más optimizada, se utiliza un algoritmo de aproximación. Los algoritmos aproximados son el tipo de algoritmos que encuentran el resultado como un resultado promedio de los subresultados de un problema. 
   Ejemplo: Para problemas NP-Hard , se utilizan algoritmos de aproximación. Los algoritmos de clasificación son los algoritmos exactos.
3. Algoritmos Serial o Paralelos o Distribuidos: En los algoritmos seriales se ejecuta una instrucción a la vez mientras que los algoritmos paralelos son aquellos en los que dividimos el problema en subproblemas y los ejecutamos en diferentes procesadores. Si los algoritmos paralelos se distribuyen en diferentes máquinas, se conocen como algoritmos distribuidos.

Clasificación por método de diseño: existen principalmente tres categorías principales en las que se puede nombrar un algoritmo en este tipo de clasificación. Están: 
 

1. Método Greedy: En el método Greedy , en cada paso, se toma la decisión de elegir el óptimo local , sin pensar en las consecuencias futuras. 
   Ejemplo: Mochila fraccionada , Selección de actividad .
2. Divide y vencerás: la estrategia Divide y vencerás consiste en dividir el problema en subproblemas, resolverlos recursivamente y luego volver a combinarlos para obtener la respuesta final. 
   Ejemplo: Ordenación por combinación , Ordenación rápida .
3. Programación Dinámica: El enfoque de la programación Dinámica es similar a divide y vencerás . La diferencia es que cada vez que tenemos llamadas a funciones recursivas con el mismo resultado, en lugar de volver a llamarlas, intentamos almacenar el resultado en una estructura de datos en forma de tabla y recuperar los resultados de la tabla. Por lo tanto, se reduce la complejidad global del tiempo. «Dinámico» significa que decidimos dinámicamente si llamar a una función o recuperar valores de la tabla. 
   Ejemplo: 0-1 Mochila , problema de suma de subconjuntos .
4. Programación lineal: en la programación lineal, existen desigualdades en términos de entradas y maximización o minimización de algunas funciones lineales de entradas. 
   Ejemplo: flujo máximo de gráfico dirigido
5. Reducción (Transformar y Conquistar): En este método, resolvemos un problema difícil transformándolo en un problema conocido para el cual tenemos una solución óptima. Básicamente, el objetivo es encontrar un algoritmo reductor cuya complejidad no esté dominada por los algoritmos reducidos resultantes. 
   Ejemplo: el algoritmo de selección para encontrar la mediana en una lista implica primero ordenar la lista y luego encontrar el elemento central en la lista ordenada. Estas técnicas también se denominan transformar y conquistar.
6. Backtracking: Esta técnica es muy útil para resolver problemas combinatorios que tienen una sola solución única . Donde tenemos que encontrar la combinación correcta de pasos que lleven al cumplimiento de la tarea. Dichos problemas tienen múltiples etapas y hay múltiples opciones en cada etapa. Este enfoque se basa en explorar cada opción disponible en cada etapa, una por una. Al explorar una opción, si se llega a un punto que no parece conducir a la solución, el control del programa retrocede un paso y comienza a explorar la siguiente opción. De esta forma, el programa explora todos los posibles cursos de acción y encuentra la ruta que conduce a la solución.  
   Ejemplo: problema de N-reina, problema de maíz.
7. Branch and Bound: Esta técnica es muy útil para resolver problemas de optimización combinatoria que tienen múltiples soluciones y nos interesa encontrar la solución más óptima. En este enfoque, todo el espacio de soluciones se representa en forma de un árbol de espacio de estado. A medida que avanza el programa, se explora cada combinación de estados, y la solución anterior se reemplaza por una nueva si no es la óptima que la solución actual. 
   Ejemplo: Secuenciación de trabajos, problema del viajante de comercio.

Clasificación por enfoques de diseño: hay dos enfoques para diseñar un algoritmo. estos enfoques incluyen 

1. Enfoque de arriba hacia abajo :
2. Enfoque de abajo hacia arriba

• Enfoque de arriba hacia abajo: en el enfoque de arriba hacia abajo, un gran problema se divide en pequeños subproblemas. y siga repitiendo el proceso de descomposición de problemas hasta que se resuelva el problema complejo.
• Enfoque de abajo hacia arriba: El enfoque de abajo hacia arriba también se conoce como el reverso de los enfoques de arriba hacia abajo.
  En un enfoque diferente, parte de un programa complejo se resuelve utilizando un lenguaje de programación y luego se combina en un programa completo.

Otras clasificaciones: además de clasificar los algoritmos en las categorías amplias anteriores, el algoritmo se puede clasificar en otras categorías amplias como: 
 

1. Algoritmos aleatorios: los algoritmos que toman decisiones aleatorias para soluciones más rápidas se conocen como algoritmos aleatorios . 
   Ejemplo: Algoritmo Quicksort aleatorio .
2. Clasificación por complejidad: algoritmos que se clasifican en función del tiempo necesario para obtener una solución a cualquier problema por tamaño de entrada. Este análisis se conoce como análisis de la complejidad del tiempo . 
   Ejemplo: algunos algoritmos toman O(n), mientras que otros toman un tiempo exponencial.
3. Clasificación por Área de Investigación: En CS cada campo tiene sus propios problemas y necesita algoritmos eficientes. 
   Ejemplo: algoritmo de clasificación, algoritmo de búsqueda, aprendizaje automático, etc.
4. Enumeración de rama y límite y retroceso: se utilizan principalmente en inteligencia artificial.