Un algoritmo (del latín, dixit algorithmus y este del griego arithmos, que significa «número», quizá también con influencia del nombre del matemático persa Al-Juarismi) es un conjunto de instrucciones o reglas definidas y no-ambiguas, ordenadas y finitas que permite, típicamente, solucionar un problema, realizar un cómputo, procesar datos y llevar a cabo otras tareas o actividades. Dados un estado inicial y una entrada, siguiendo los pasos sucesivos se llega a un estado final y se obtiene una solución. Los algoritmos son el objeto de estudio de la algoritmia.
El esquema voraz (greedy algorithms) se aplica a problemas de optimización en los que la solución se puede construir paso a paso sin necesidad de reconsiderar decisiones ya tomadas. Genéricamente el problema que se puede resolver con este tipo de esquema es: encontrar un conjunto de candidatos que constituya una solución y que optimice una función objetivo. Este esquema se utiliza principalmente en problemas de planificación de tareas y en problemas que se pueden modelar con grafos, en los que hay que realizar una búsqueda, cálculo de recorridos u optimización de pesos, entre otras tareas.
Los problemas que se pueden resolver con este esquema constan de n candidatos y se trata de encontrar una solución basada en hallar un subconjunto de esos candidatos, o una secuencia ordenada de los mismos, de manera que se optimice (maximice o minimice) una función objetivo. En este esquema se trabaja por etapas, considerando la elección de un candidato en cada etapa. Habrá que seleccionar en cada una el candidato más prometedor de los aún disponibles y decidir si se incluye o no en la solución.
Si quieres profundizar más sobre los algoritmos voraces, dispones de más información aquí.
La estrategia de Divide y Vencerás es una técnica algorítmica que se basa en la descomposición de un problema en subproblemas de su mismo tipo, lo que permite disminuir la complejidad y en algunos casos, paralelizar la resolución de los mismos.
La estrategia del algoritmo es la siguiente:
Puedes ampliar la información en el siguiente enlace.
La programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas.
Una subestructura óptima significa que se pueden usar soluciones óptimas de subproblemas para encontrar la solución óptima del problema en su conjunto. En general, se pueden resolver problemas con subestructuras óptimas siguiendo estos tres pasos:
Los subproblemas se resuelven a su vez dividiéndolos en subproblemas más pequeños hasta que se alcance el caso fácil, donde la solución al problema es trivial.
Puedes encontrar más información en Programación dinámica.
La estrategia de los algoritmos de vuelta atrás consiste en recorrer el espacio completo de soluciones de un problema dado, pero se puede optimizar aplicando una poda a aquellas ramas que sabemos de antemano que no conducen a una solución. Se suele utilizar cuando no existe ningún otro algoritmo más eficiente que pueda aplicarse.
El procedimiento es el siguiente:
Si quieres profundizar más, pulsa aquí.
Este esquema se utiliza en aquellos problemas en los que se trata de optimizar uno o más criterios para alcanzar la solución. Se puede aplicar en los mismos casos que el esquema voraz pero es menos eficiente que éste. Este esquema explora todos los caminos que permiten llegar a una solución, podando aquellas ramas que no pueden alcanzarla, y además evitando aquellas ramas que sólo podrán alcanzar una solución peor que las que ya se han encontrado.
Las ideas principales son:
Puedes encontrar más información aquí.