En matemáticas e informática , una técnica algorítmica [1] es un enfoque general para implementar un proceso o cálculo . [2]
Técnicas generales
Hay varias técnicas algorítmicas ampliamente reconocidas que ofrecen un método o proceso probado para diseñar y construir algoritmos. Se pueden usar diferentes técnicas según el objetivo, que pueden incluir búsqueda , clasificación , optimización matemática , satisfacción de restricciones , categorización , análisis y predicción . [3]
Fuerza bruta
La fuerza bruta es una técnica simple y exhaustiva que evalúa todos los resultados posibles para encontrar una solución. [4]
Divide y conquistaras
La técnica de divide y vencerás descompone problemas complejos de forma recursiva en subproblemas más pequeños. Luego, cada subproblema se resuelve y estas soluciones parciales se recombinan para determinar la solución general. Esta técnica se utiliza a menudo para buscar y clasificar. [5]
Dinámica
La programación dinámica es una técnica sistemática en la que un problema complejo se descompone de forma recursiva en subproblemas más pequeños y superpuestos para su solución. La programación dinámica almacena los resultados de los subproblemas superpuestos localmente utilizando una técnica de optimización llamada memorización . [6]
Evolutivo
Un enfoque evolutivo desarrolla soluciones candidatas y luego, de manera similar a la evolución biológica, realiza una serie de alteraciones aleatorias o combinaciones de estas soluciones y evalúa los nuevos resultados frente a una función de adecuación. Los resultados más adecuados o prometedores se seleccionan para iteraciones adicionales, para lograr una solución óptima general. [7]
Recorrido del gráfico
El recorrido de gráficos es una técnica para encontrar soluciones a problemas que se pueden representar como gráficos . Este enfoque es amplio, e incluye la búsqueda en profundidad , búsqueda en amplitud , recorrido de árbol , y muchas variaciones específicas que pueden incluir optimizaciones locales y excluyendo espacios de búsqueda que se pueden determinar a ser no óptimo o no posible. Estas técnicas se pueden utilizar para resolver una variedad de problemas, incluido el camino más corto y los problemas de satisfacción de restricciones. [8]
Avaro
Un enfoque codicioso comienza evaluando un resultado posible del conjunto de resultados posibles y luego busca localmente una mejora en ese resultado. Cuando se encuentra una mejora local, repetirá el proceso y nuevamente buscará localmente mejoras adicionales cerca de este óptimo local. Una técnica codiciosa es generalmente simple de implementar, y esta serie de decisiones se pueden usar para encontrar óptimos locales dependiendo de dónde comenzó la búsqueda. Sin embargo, las técnicas codiciosas pueden no identificar el óptimo global en todo el conjunto de posibles resultados. [9]
Heurístico
Un enfoque heurístico emplea un método práctico para llegar a una solución inmediata que no se garantiza que sea óptima. [10]
Aprendiendo
Las técnicas de aprendizaje emplean métodos estadísticos para realizar la categorización y el análisis sin programación explícita. El aprendizaje supervisado , aprendizaje sin supervisión , aprendizaje por refuerzo y aprendizaje profundo técnicas se incluyen en esta categoría. [11]
Optimización matemática
La optimización matemática es una técnica que se puede utilizar para calcular un óptimo matemático minimizando o maximizando una función. [12]
Modelado
El modelado es una técnica general para abstraer un problema del mundo real en un marco o paradigma que ayuda con la solución. [13]
Recursividad
La recursividad es una técnica general para diseñar un algoritmo que se llama a sí mismo con una parte progresivamente más simple de la tarea hasta uno o más casos base con resultados definidos. [14] [15]
Ver también
- Ingeniería de algoritmos
- Caracterizaciones de algoritmos
- Teoría de la computación
Notas
- ^ "técnica | Definición de técnica en inglés por los diccionarios de Oxford" . Diccionarios de Oxford | Ingles . Consultado el 23 de marzo de 2019 .
- ^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). Introducción a los algoritmos . Prensa del MIT. pag. 9. ISBN 9780262032933.
- ^ Skiena, Steven S. (1998). El manual de diseño de algoritmos: texto . Springer Science & Business Media. ISBN 9780387948607.
- ^ "¿Qué es la fuerza bruta? Definición de Webopedia" . www.webopedia.com . Consultado el 23 de marzo de 2019 .
- ^ Bentley, Jon Louis; Shamos, Michael Ian (1976). "Divide y vencerás en el espacio multidimensional". Actas del Octavo Simposio Anual ACM sobre Teoría de la Computación . STOC '76. Nueva York, NY, EE. UU .: ACM: 220–230. doi : 10.1145 / 800113.803652 .
- ^ Bellman, Richard (1 de julio de 1966). "Programación dinámica". Ciencia . 153 (3731): 34–37. doi : 10.1126 / science.153.3731.34 . ISSN 0036-8075 . PMID 17730601 .
- ^ Coello Coello, Carlos A. (1 de agosto de 1999). "Una encuesta completa de técnicas de optimización multiobjetivo basadas en la evolución". Sistemas de conocimiento e información . 1 (3): 269-308. doi : 10.1007 / BF03325101 . ISSN 0219-3116 .
- ^ Kumar, Nitin; Wayne, Kevin (1 de febrero de 2014). Algoritmos . Addison-Wesley Professional. ISBN 9780133799101.
- ^ "algoritmo codicioso" . xlinux.nist.gov . Consultado el 23 de marzo de 2019 .
- ^ "heurístico" . xlinux.nist.gov . Consultado el 23 de marzo de 2019 .
- ^ Witten, Ian H .; Frank, Eibe; Hall, Mark A .; Pal, Christopher J. (1 de octubre de 2016). Minería de datos: herramientas y técnicas prácticas de aprendizaje automático . Morgan Kaufmann. ISBN 9780128043578.
- ^ Marler, RT; Arora, JS (1 de abril de 2004). "Estudio de métodos de optimización multiobjetivo para ingeniería". Optimización estructural y multidisciplinar . 26 (6): 369–395. doi : 10.1007 / s00158-003-0368-6 . ISSN 1615-1488 .
- ^ Skiena, Steven S. (1998). El manual de diseño de algoritmos: texto . Springer Science & Business Media. ISBN 9780387948607.
- ^ "recursividad" . xlinux.nist.gov . Consultado el 23 de marzo de 2019 .
- ^ "Programación - Recurrencia" . www.cs.utah.edu . Consultado el 23 de marzo de 2019 .
enlaces externos
- Diseño y técnicas algorítmicas - edX
- Técnicas algorítmicas y análisis - Carnegie Mellon
- Técnicas algorítmicas para datos masivos - MIT