¿Qué son los algoritmos de modelado matemático?
1. Algoritmo de Montecarlo. Este algoritmo, también conocido como algoritmo de simulación aleatoria, es un algoritmo que resuelve problemas mediante simulación por computadora. Al mismo tiempo, puede probar la exactitud de su propio modelo mediante simulación. Es casi un método imprescindible durante las competiciones.
2. Algoritmos de procesamiento de datos como ajuste de datos, estimación de parámetros e interpolación. Las competiciones suelen encontrar una gran cantidad de datos que deben procesarse, y la clave para procesar datos radica en estos algoritmos, que suelen utilizar MATLAB como herramienta.
3. Algoritmos de planificación como programación lineal, programación entera, programación multivariada y programación cuadrática. La mayoría de los problemas en las competiciones de modelado son problemas de optimización. En muchos casos, estos problemas pueden describirse mediante algoritmos de programación matemática y, por lo general, se resuelven utilizando el software Lindo y Lingo.
4. Algoritmo de teoría de grafos. Este tipo de algoritmo se puede dividir en muchos tipos, incluido el camino más corto, el flujo de red, el gráfico bipartito y otros algoritmos que se pueden resolver utilizando estos métodos, y se requiere una preparación cuidadosa.
5. Algoritmos informáticos como programación dinámica, búsqueda de retroceso, algoritmo de divide y vencerás, ramificación y límite. Estos algoritmos son métodos comúnmente utilizados en el diseño de algoritmos y se utilizan en muchas ocasiones en competiciones.
6. Tres algoritmos no clásicos principales en la teoría de la optimización: algoritmo de recocido simulado, algoritmo de redes neuronales y algoritmo genético. Estas preguntas se utilizan para resolver algunos problemas de optimización más difíciles. Son muy útiles para algunos problemas, pero la implementación del algoritmo es más difícil y debe usarse con precaución.
7. Algoritmo grid y método exhaustivo. Ambos son algoritmos para la búsqueda de puntos óptimos por fuerza bruta y se han utilizado en muchas preguntas de competencia. Cuando la atención se centra en el modelo en sí y el algoritmo está subestimado, se puede utilizar esta solución de fuerza bruta. Lenguajes de nivel como herramientas de programación.
8. Algunos métodos de discretización continua de datos. Muchos problemas surgen de la realidad. Los datos pueden ser continuos, pero las computadoras solo pueden procesar datos discretos. Por lo tanto, es muy importante discretizarlos y luego usar diferencias en lugar de diferenciales y sumas en lugar de integrales.
9. Algoritmo de análisis numérico. Si se utilizan lenguajes de alto nivel para la programación en competiciones, los algoritmos comúnmente utilizados en análisis numérico, como la resolución de ecuaciones, operaciones matriciales, integración de funciones y otros algoritmos, requerirán que se escriban y llamen funciones de biblioteca adicionales.
10. Algoritmo de procesamiento de imágenes. Hay un tipo de problema en la competencia relacionado con los gráficos. Incluso si el problema no tiene nada que ver con los gráficos, se necesitarán imágenes para ilustrar el problema en el documento. que necesita ser resuelto. MATLAB se usa generalmente para el procesamiento.
A continuación se dará una explicación detallada de estos diez tipos de algoritmos basados en preguntas de competencias anteriores.
A continuación se dará una explicación detallada de estos diez tipos de algoritmos basados en preguntas de competencias anteriores.
2 Descripción detallada de diez tipos de algoritmos
2.1 Algoritmo de Monte Carlo
La mayoría de las preguntas de la competencia de modelado son inseparables de la simulación por computadora y la simulación aleatoria. Los algoritmos muy comunes.
Por ejemplo, la pregunta A en 1997. Cada pieza tiene su propio valor de calibración y su propio nivel de tolerancia. Para resolver el plan de combinación óptimo, se enfrentará a un Con fórmulas extremadamente complejas y 108 soluciones de selección de tolerancia. Es imposible encontrar una solución analítica. Entonces, ¿cómo encontrar la solución óptima? La búsqueda de simulación aleatoria de la solución óptima es uno de los métodos. En el intervalo factible de cada parte, se seleccionan aleatoriamente un valor de calibración y un valor de tolerancia de acuerdo con la distribución normal como solución y luego se simulan mediante el algoritmo de Monte Carlo. con muchas opciones y elige la mejor. Otro ejemplo es la segunda pregunta de la lotería del año pasado, que requirió el diseño de una mejor solución. En primer lugar, la calidad de la solución depende de muchos factores complejos. También es imposible dibujar un modelo de solución y sólo se puede confiar en él. en simulación aleatoria.
2.2 Ajuste de datos, estimación de parámetros, interpolación y otros algoritmos
El ajuste de datos se utiliza en muchos problemas de competencia. Muchos problemas relacionados con el procesamiento de gráficos están relacionados con el ajuste. Un ejemplo es la pregunta A. de la competencia estadounidense de 1998, el procesamiento de interpolación tridimensional de cortes de tejido biológico, la pregunta A de 1994 para abrir un camino a través de las montañas, el cálculo de interpolación de la altitud de la montaña y la ruidosa pregunta "SARS" que puede probarse también necesitan utilizar simulación de datos Combine el algoritmo y observe la tendencia de los datos para su procesamiento. Hay muchas funciones listas para usar que se pueden llamar en MATLAB para este tipo de problema. Si está familiarizado con MATLAB, puede utilizar estos métodos con facilidad.
2.3 Algoritmos para problemas de planificación
Muchos problemas de la competencia están relacionados con la programación matemática. Se puede decir que muchos modelos se pueden reducir a un conjunto de desigualdades como restricciones y varias funciones. expresiones Cuando se encuentra con este tipo de problemas, resolverlo es la clave. Por ejemplo, para la pregunta B en 1998, se pueden usar muchas desigualdades para describir el problema con claridad, por lo que es más conveniente usar Lindo, Lingo y otros programas para resolver. el problema después de enumerar el plan, por lo que aún debe estar familiarizado con estos dos programas.
2.4 Problemas de teoría de grafos
Los problemas B en 1998, el Problema B en 2000, el empaquetado de cerraduras en 1995 y otros problemas reflejan la importancia de los problemas de teoría de grafos. Existen muchos algoritmos para este tipo de problemas. , incluidos: Dijkstra, Floyd, Prim, Bellman-Ford, flujo máximo, coincidencia binaria y otros problemas. Cada algoritmo debe implementarse una vez; de lo contrario, será demasiado tarde para escribirlo nuevamente durante la competencia.
2.5 Problemas en el diseño de algoritmos informáticos
El diseño de algoritmos informáticos incluye muchos contenidos: programación dinámica, búsqueda de retroceso, algoritmo de divide y vencerás, bifurcación y límites. Por ejemplo, el problema B de 1992 utilizó el método de ramificación y limitación, el problema B de 1997 era un problema típico de programación dinámica y el problema B de 1998 incorporaba el algoritmo de divide y vencerás. Este aspecto del problema es similar al problema en la competencia de programación ACM. Se recomienda leer libros relacionados con algoritmos informáticos, como "Diseño y análisis de algoritmos informáticos" (Electronic Industry Press).
2.6 Tres algoritmos no clásicos principales de la teoría de la optimización
En los últimos diez años, la teoría de la optimización se ha desarrollado rápidamente y se han desarrollado tres tipos de algoritmos: recocido simulado, redes neuronales, y algoritmos genéticos pronto. En los últimos años, las preguntas de la competencia se han vuelto cada vez más complejas y no existen buenos modelos para aprender de muchos problemas. Por lo tanto, estos tres tipos de algoritmos a menudo pueden resultar útiles, como el algoritmo de recocido simulado para la pregunta A. 1997 y el algoritmo de recocido simulado para la pregunta B en 2000. El algoritmo de clasificación de redes neuronales también se puede utilizar para problemas difíciles como la pregunta B en 2001. La pregunta A en la competencia estadounidense de 1989 también está relacionada con el algoritmo BP. El algoritmo BP se propuso recién en 1986 y se probó en 1989. Explicar Las preguntas de la competencia pueden ser reflejos abstractos de la tecnología de vanguardia actual. El problema del Gamma Knife en la pregunta B de 2003 también es un tema de investigación actual. El mejor algoritmo actualmente es el algoritmo genético.
2.7 Algoritmo de cuadrícula y algoritmo exhaustivo
El algoritmo de cuadrícula es el mismo que el método exhaustivo, excepto que el método de cuadrícula es exhaustivo de problemas continuos. Por ejemplo, si se requiere un problema de optimización bajo la condición de N variables, entonces se toman puntos del espacio donde se pueden tomar estas variables. Por ejemplo, se toman M + 1 puntos en el intervalo [a; a; a+(b-a)/M; a+2 (b-a)/M; …… ; b Entonces dicho bucle requiere (M + 1)N operaciones, por lo que la cantidad de cálculo es muy grande. Por ejemplo, la pregunta A de 1997 y la pregunta B de 1999 se pueden buscar utilizando el método de cuadrícula. Este método se realiza mejor en una computadora con una velocidad de procesamiento rápida
y debe realizarse en una computadora de alta velocidad. lenguaje de nivel. Es mejor no utilizar MATLAB para hacer la cuadrícula, de lo contrario llevará mucho tiempo calcularlo. Todo el mundo está familiarizado con el método exhaustivo, por lo que no lo explicaré aquí.
2.8 Algunos métodos de discretización continua de datos
La programación de soluciones para la mayoría de los problemas físicos tiene cierta conexión con este método. Los problemas físicos reflejan que vivimos en un mundo continuo y las computadoras solo pueden procesar cantidades discretas, por lo que las cantidades continuas deben procesarse de manera discreta. Este método se utiliza ampliamente y está relacionado con muchos de los algoritmos anteriores. De hecho, el algoritmo de cuadrícula, el algoritmo de Monte Carlo y el recocido simulado utilizan esta idea.
2.9 Algoritmos de Análisis Numérico
Este tipo de algoritmo está especialmente diseñado para lenguajes de alto nivel. Si estás usando MATLAB o Mathematica, no necesitas prepararte, porque los hay. El software de matemáticas generales tiene muchas funciones.
2.10 Algoritmo de procesamiento de imágenes
La pregunta A en 2001 requiere que puedas leer imágenes BMP, la pregunta A en 1998 requiere que conozcas el cálculo de interpolación tridimensional, la pregunta B en 2003 requiere que sepas Más alto, no solo se requieren cálculos de programación sino también procesamiento, y hay muchas imágenes para mostrar en documentos digitales y analógicos, por lo que el procesamiento de imágenes es la clave. Para solucionar este tipo de problemas es importante conocer bien MATLAB, especialmente la parte de procesamiento de imágenes.