2. Algoritmos de procesamiento de datos, como ajuste de datos, estimación de parámetros e interpolación. Suele haber una gran cantidad de datos que hay que procesar en las competiciones, y la clave para procesar los datos reside en estos algoritmos, normalmente utilizando MATLAB como herramienta.
3. Algoritmos de programació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. Muchas veces estos problemas pueden describirse mediante algoritmos de programación matemática, generalmente resueltos por el software Lindo y Lingo.
4. Algoritmo de teoría de grafos. Este tipo de algoritmo se puede dividir en muchos tipos, incluido el algoritmo de ruta más corta, el algoritmo de flujo de red, el algoritmo de gráfico bipartito, etc. Los problemas relacionados con la teoría de grafos se pueden resolver utilizando estos métodos y requieren una preparación cuidadosa.
5. Algoritmos informáticos, como programación dinámica, búsqueda de retroceso, algoritmo de divide y vencerás, bifurcación y límite. Estos algoritmos se utilizan habitualmente en el diseño de algoritmos y se utilizan en muchas ocasiones en competiciones.
6. Tres algoritmos no clásicos de 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 difíciles y son muy útiles para algunos problemas, pero la implementación del algoritmo es difícil y debe usarse con precaución.
7. Algoritmo grid y método exhaustivo. Ambos son los mejores algoritmos para la búsqueda de fuerza bruta y se han aplicado en muchos problemas de competencia. Esta solución de fuerza bruta se puede utilizar cuando nos centramos en el modelo en sí y despreciamos el algoritmo, preferiblemente usando algún lenguaje de alto nivel como herramienta de programación.
8. Varios métodos de discretización para datos continuos. Muchos problemas son prácticos, los datos pueden ser continuos y las computadoras solo pueden procesar datos discretos, por lo que es muy importante discretizarlos e implementar ideas como diferencias en lugar de diferenciales y sumas en lugar de integrales.
9. Algoritmo de análisis numérico. Si se utiliza programación en lenguaje de alto nivel en la competencia, los algoritmos comúnmente utilizados en análisis numérico, como la resolución de ecuaciones, operaciones matriciales, integración de funciones, etc., requerirán escribir funciones de biblioteca adicionales para llamar.
10. Algoritmo de procesamiento de imágenes. Hay una categoría de problemas relacionados con los gráficos en la competencia. Incluso si la pregunta no tiene nada que ver con gráficos, se necesitarán imágenes en el documento para ilustrar el problema. Cómo mostrar estos gráficos y cómo procesarlos son problemas que deben resolverse y generalmente se manejan con MATLAB.
A continuación se explicarán estos diez algoritmos en detalle basándose en preguntas de competencias anteriores.
A continuación se explicarán estos diez algoritmos en detalle basándose en preguntas de competencias anteriores.
Descripción detallada de los 2 diez algoritmos
2.1 Algoritmo de Monte Carlo
La mayoría de las competiciones de modelado son inseparables de la simulación por computadora, y la simulación aleatoria es la más común. algoritmos.
Por ejemplo, en la pregunta A de 1997, cada pieza tiene su propio valor de calibración y nivel de tolerancia. Para encontrar la solución de combinación óptima se enfrentarán fórmulas extremadamente complejas y 108 opciones de selección de tolerancia, y es imposible encontrarla. una solución analítica. ¿Cómo encontrar la solución óptima? La simulación aleatoria y la búsqueda de la solución óptima son uno de los métodos. Dentro del intervalo factible de cada parte, se selecciona aleatoriamente un valor de calibración y un valor de tolerancia como solución de acuerdo con la distribución normal, y luego se utiliza un algoritmo de Monte Carlo para simular una gran cantidad de soluciones para seleccionar la mejor solución. Otro ejemplo es la segunda pregunta del sorteo del año pasado, que requería una mejor solución. En primer lugar, la calidad de la solución depende de muchos factores complejos y es imposible describir un modelo para resolverla. Sólo puede simularse mediante 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 juegos y muchos problemas relacionados con el procesamiento de gráficos están relacionados con el ajuste. Un ejemplo es el juego A de 1998 en los Estados Unidos, el procesamiento de interpolación tridimensional de cortes de tejido biológico, el cálculo de interpolación de la altitud de la montaña en el juego A de 1994 y las ruidosas preguntas sobre el SARS que pueden probarse en el examen. También se deben utilizar algoritmos de ajuste de datos para observar tendencias en los datos a procesar. Para este tipo de problema, existen muchas funciones listas para usar en MATLAB que se pueden llamar. Si está familiarizado con MATLAB, estos métodos funcionarán bien.
2.3 Algoritmos de problemas de programación
Muchos de los problemas de la competición están relacionados con la programación matemática. Se puede decir que muchos modelos pueden reducirse a un conjunto de desigualdades como restricciones y varias expresiones funcionales como funciones objetivas. Cuando nos encontramos con un problema de este tipo, la clave es resolverlo.
Por ejemplo, la pregunta B de 1998 se puede describir claramente con muchas desigualdades. Por lo tanto, es más conveniente utilizar Lindo, Lingo y otros programas para resolver el problema después de hacer un plan, por lo que es necesario estar familiarizado con estos dos programas.
2.4 Problemas de teoría de grafos
Los problemas de embalaje de cajas de seguridad 98 B, 00 B y 95 reflejan la importancia de la teoría de grafos. Existen muchos algoritmos para este tipo de problemas, entre ellos: Dijkstra, Floyd, Prim, Bellman-Ford, flujo máximo, coincidencia binaria, etc. Cada algoritmo debe implementarse una vez; de lo contrario, será demasiado tarde para escribirlo en el juego.
2.5 Cuestiones 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, ramificación y límites. Por ejemplo, en 1992, la pregunta B era el método de ramificación y unión; en 1997, la pregunta B era un problema típico de programación dinámica; además, la pregunta B en 1998 reflejaba el algoritmo de divide y vencerás; Las preguntas en esta área son similares a las de los concursos de programación de 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 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 tres tipos de algoritmos, recocido simulado, redes neuronales y algoritmos genéticos, se han desarrollado rápidamente. En los últimos años, las preguntas de competencia se han vuelto cada vez más complejas y no existen buenos modelos para aprender de muchos problemas, por lo que estos tres tipos de algoritmos a menudo pueden resultar útiles, como: algoritmo de recocido simulado para la pregunta 97 A, algoritmo neuronal Algoritmo de clasificación de redes para la pregunta 00 B. Problemas como la pregunta 01 B también pueden usar redes neuronales. La pregunta 89 A en la competencia estadounidense también está relacionada con el algoritmo BP recién propuesto en 1986 y 1989. El problema del Gamma Knife de la Pregunta B en 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 un método exhaustivo para problemas continuos. Por ejemplo, si se requiere un problema de optimización bajo la condición de n variables, seleccione el espacio donde se pueden tomar estas variables. Por ejemplo, tome el intervalo M + 1 punto en [a; B], que es a+(. b-a)/M; a+2(b-a)/ M;... ;b Entonces este bucle necesita operar (M+1)N veces, por lo que la cantidad de cálculo es muy grande. Por ejemplo, para la pregunta A de 1997 y la pregunta B de 1999, puede utilizar el método de cuadrícula para buscar. Este método es preferiblemente más rápido.
En las computadoras, existen lenguajes de alto nivel que se pueden hacer. Es mejor no usar MATLAB para hacer grillas, de lo contrario tomará mucho tiempo. 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 de datos continuos
La mayoría de soluciones de programación a problemas físicos están relacionadas con este método. Los problemas de física reflejan que vivimos en un mundo continuo. Las computadoras sólo pueden manejar cantidades discretas, por lo que necesitan procesar cantidades continuas 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 Algoritmo de Análisis Numérico
Este algoritmo está especialmente diseñado para lenguajes de alto nivel. Si utiliza MATLAB y Mathematica, no es necesario prepararse, porque hay muchas funciones en el análisis numérico.
2.10 Algoritmo de procesamiento de imágenes
01, es necesario poder ver imágenes BMP. En 1998, en los Estados Unidos, era necesario poder calcular la interpolación tridimensional. En 2003, pregunta B, los requisitos son mayores, no solo es necesario procesar los cálculos de programación, y los documentos digitales y analógicos tienen muchas imágenes para mostrar, por lo que el procesamiento de imágenes es la clave. Para hacer bien este tipo de preguntas es importante aprender bien MATLAB, especialmente la parte de procesamiento de imágenes.