En las matemáticas y la informática, un algoritmo es una descripción precisa de la serie de operaciones a realizar con el fin de resolver un problema o un conjunto de problemas.
Si un proceso es algorítmico puede ser descrito como la serie de operaciones que se pueden realizar a través de los cálculos.
Tipos de algoritmos.
Los algoritmos son muchos, pero los que utilizan un enfoque similar de resolución de problemas se pueden agrupar juntos, este esquema de clasificación abarca los que consideramos más importantes.
El propósito en realidad no es ser capaz de clasificar un algoritmo como de un tipo u otro, sino destacar las diversas formas en que un problema puede ser atacado.
Algoritmos recursivos simples
Los algoritmos recursivos resuelven los casos base directamente, aunque utilizan la repetición en base a un problema derivado del problema inicial aunque más sencillo.
¿Tiene algún trabajo extra para encontrar la solución? el problema derivado más simple se convierte en una solución para el problema dado.
Algoritmos de rastreo hasta el origen.
Los algoritmos de rastreo hasta la fuente se basan en una búsqueda recursiva primero en profundidad, es decir, un algoritmo de retroceso.
Se hacen las pruebas para ver si se ha encontrado una solución, y si es así, lo resuelve; de otra manera: para cada opción que se puede hacer en este punto, se toma esa decisión, se repite; si la recursividad devuelve una solución, se resuelve, si las opciones siguen siendo insuficientes, vuelve al ciclo.
Algoritmo divide y vencerás.
Un algoritmo divide y vencerás consta de dos partes:
- Dividir en problemas derivados más pequeños del mismo tipo, y resolver estos problemas de forma recursiva.
- Combinar y convertir las soluciones a los problemas derivados en una solución al problema original.
Tradicionalmente, a un algoritmo sólo se le llama divide y vencerás si contiene dos o más llamadas recursivas.
Algoritmos de programación dinámica.
Un algoritmo de programación dinámica recuerda los resultados anteriores y los utiliza para encontrar nuevos resultados. La programación dinámica se utiliza generalmente para resolver problemas de optimización
- Existen múltiples soluciones, se necesita encontrar la «mejor»
- Requieren de una «subestructura óptima» y «problemas derivados superpuestos»
La subestructura óptima es la solución óptima y contiene soluciones óptimas a los problemas derivados.
Los problemas derivados superpuestos vendrían a ser las soluciones a los problemas derivados que se pueden almacenar y reutilizar de forma ascendente.
Esto difiere del algoritmo divide y vencerás, donde los problemas derivados en general no necesitan solapamiento.
Algoritmos ramificados y consolidados.
Estos algoritmos se utilizan generalmente para resolver problemas de optimización, conforme el algoritmo avanza, se forma un árbol de problemas derivados.
El problema original es considerado como el «problema raíz»; un método se utiliza para construir un límite superior e inferior para un problema dado, en cada nodo, aplican los métodos que lo limitan.
Si los límites coinciden, se considera una solución factible a ese problema derivado en particular, pero si los límites no coinciden, se reparte el problema representado por ese nodo, y se hacen dos problemas derivados.
Continuar, utilizando la solución factible más conocida para recortar secciones del árbol, hasta que todos los nodos se han resuelto o recortado a su mínima expresión.
Un ejemplo de esto es el problema del viajante: Un vendedor tiene que visitar cada una de n ciudades (al menos) una vez cada una, y quiere minimizar la distancia total recorrida.
Consideramos que el problema de raíz es encontrar la ruta más corta a través de un conjunto de ciudades visitando cada ciudad una vez.
Dividimos el nodo en dos problemas derivados:
- Ruta más corta visita a la ciudad A primero.
- Ruta más corta no visita a la ciudad A primero.
Continuar subdividiendo de manera similar así como el árbol va creciendo.
Algoritmos codiciosos.
Un «algoritmo codicioso» a veces funciona bien para problemas de optimización, este tipo de algoritmo trabaja en fases, en cada fase:
- Se toma la mejor solución que se puede conseguir en este momento, sin tener en cuenta las consecuencias futuras.
- Uno espera que al elegir un resultado óptimo local en cada paso, el resultado final será en un óptimo global.
Algoritmos de fuerza bruta.
Un algoritmo de fuerza bruta simplemente trata todas las posibilidades hasta que se encuentre una solución satisfactoria.
Este algoritmo puede ser:
- Óptimo: Encontrar la mejor solución, lo que puede requerir encontrar todas las soluciones, o si se conoce un valor para la mejor solución, que se puede detener cuando se encontró ninguna mejor solución
Ejemplo: Encontrar la mejor ruta para un viajante de comercio
- Satisfactorio: Para tan pronto como se encuentra una solución que es lo suficientemente bueno
Ejemplo: Encontrar un camino para un viajante de comercio que esté dentro del 10% de la solución óptima.
Algoritmos aleatorios.
Un algoritmo aleatorio utiliza un número aleatorio al menos una vez durante el cálculo para tomar una decisión.
- Ejemplo: En Quicksort, utilizando un número aleatorio para elegir un pivote.
- Ejemplo: Tratando de factorizar un número primo grande eligiendo números al azar como posibles divisores.