1 Antecedentes e importancia de la investigación
Ya en la década de 1970, se demostró que el problema de programación de cursos era un problema NP completo, es decir, el tiempo de cálculo del algoritmo aumenta exponencialmente. Se establece esta conclusión. Se ha mejorado la profundidad teórica de los problemas de programación del curso. Actualmente no existe ningún algoritmo general que pueda resolver bien el problema NP-completo en matemáticas. Sin embargo, muchos problemas NP-completos tienen, por ejemplo, un significado práctico muy importante. El algoritmo de enrutamiento con el que todos están familiarizados es un problema típico de NP completo. El enrutamiento requiere encontrar el camino más corto entre múltiples nodos para completar la transmisión de información. Dado que todos son problemas NP completos, se pueden aplicar muchos algoritmos de enrutamiento para resolver problemas de programación de clases, como el algoritmo de Dijkstra, la poda de subárboles de nodos para construir el método de ruta más corta de la red, etc.
En la actualidad, la idea principal de todas las investigaciones sobre problemas NP-completos es cómo reducir su complejidad computacional. Es decir, en su lugar se utiliza un algoritmo aproximado, esforzándose por simplificar el tiempo para resolver el problema desde un crecimiento exponencial hasta un crecimiento polinomial. Combinarlo con el problema de programación de clases es establecer un modelo simplificado realista adecuado. El uso de este modelo simplificado puede reducir en gran medida la complejidad del algoritmo y facilitar la implementación del programa.
En colegios y universidades, la principal forma de formar a los estudiantes es la enseñanza. En las actividades docentes existe una serie de trabajos de gestión, entre los cuales la implementación de planes docentes es un eslabón docente importante. Cada semestre, los administradores deben organizar planes de enseñanza, emitir asignaciones de enseñanza basadas en los planes de enseñanza y luego compilar horarios de cursos basados en las asignaciones de enseñanza. En estas tareas de programación docente, no solo hay una gran cantidad de tedioso trabajo de recopilación de datos, sino también un riguroso trabajo mental y una gran cantidad de formularios para completar. Entonces el trabajo es muy pesado.
Además, con el avance de la reforma docente y la implementación del proyecto "211", el nuevo sistema educativo ha planteado mayores requisitos para la organización de los horarios de clases. Cuando se programan clases manualmente, es extremadamente problemático pasar información hacia arriba y hacia abajo, pero con la programación por computadora, la información en la enseñanza se puede ver de un vistazo, lo cual es importante para optimizar el proceso de aprendizaje de los estudiantes, evaluar la contribución de cada maestro a la enseñanza y Liderar la toma de decisiones razonable. La importancia definitivamente promoverá en gran medida el círculo virtuoso de la enseñanza.
2 Campos de aplicación del tema
La investigación sobre este tema tiene un papel rector en el desarrollo de sistemas de programación de cursos en colegios y universidades.
El núcleo del problema de la programación de clases es el conflicto y la preferencia de recursos multidimensionales. La investigación sobre problemas similares (especialmente aquellos relacionados con los horarios: como problemas de programación de exámenes, problemas de asientos en el cine, preguntas sobre rutas aéreas). ) también es una referencia.
3 Situación actual de la materia
A finales de los años 1990, algunas personas en el extranjero comenzaron a estudiar el tema de la organización curricular. En 1962, Gotlieb propuso un modelo matemático del problema curricular y utilizó el algoritmo húngaro para resolver el problema del transporte lineal tridimensional. Desde entonces, la gente ha debatido mucho en profundidad sobre el algoritmo del problema curricular y la existencia de soluciones. Sin embargo, los modelos matemáticos utilizados en la mayor parte de la literatura son simplificaciones o complementos del modelo matemático de Gotlieb, y hasta el momento no existe ningún algoritmo factible para resolver el problema curricular.
En los últimos 40 años, la gente ha hecho muchos intentos de encontrar soluciones informáticas al problema curricular. Entre ellos, el modelo de programación entera de disposición curricular reduce el problema a encontrar la solución a un conjunto de variables 0-1, pero su cantidad de cálculo es muy grande. La técnica de ramificación y límite para resolver problemas de optimización lineal 0-1 sólo es adecuada para arreglos curriculares a pequeña escala. Mihoc y Balas (1965) formularon el plan de estudios como un problema de optimización y Krawczk propuso un método de programación lineal. Junginger simplificó el problema del horario de clases en un problema de transporte tridimensional, mientras que Tripathy consideró el problema del horario de clases como un problema de programación lineal entera y propuso un modelo matemático de los horarios de clases universitarias.
Además, parte de la literatura intenta resolver el problema de la programación de clases desde la perspectiva de la teoría de grafos, pero el problema de coloración de las gráficas también es un problema NP-completo. Solo en casos extremadamente simples se puede realizar la programación de clases. transformarse en un problema de dos partes Para los problemas de correspondencia de gráficos, dicho modelo matemático está demasiado lejos de la realidad, por lo que no tiene valor práctico para la mayoría de los problemas de organización del horario escolar.
Tras entrar en la década de 1990, la investigación extranjera sobre la cuestión curricular sigue siendo muy activa. Ejemplos más representativos incluyen a Arabinda Tripathy de la Escuela de Administración de la Universidad de Vastapur en India, y a Jean Aubin y Jacques Ferland de la Universidad de Montreal en Canadá. En la actualidad, los métodos para resolver el problema del horario de clases incluyen: método de programación de clases manual simulada, método de teoría de grafos, método lagrangiano, método de asignación cuadrática y otros métodos. Debido a las complejas limitaciones del plan de estudios, describirlo utilizando métodos matemáticos a menudo conduce a un aumento dramático en la escala del problema, lo que se ha convertido en un gran obstáculo para aplicar la programación matemática para resolver problemas del plan de estudios. La investigación extranjera muestra que no es factible resolver el problema de los horarios de clases a gran escala únicamente mediante métodos matemáticos. Utilizar la idea de planificación jerárquica en la investigación de operaciones para descomponer el problema será un método prometedor para tener éxito.
En China, la investigación sobre la cuestión de los horarios comenzó a principios de la década de 1980. Ejemplos representativos incluyen: el sistema UTSS (A University Timetable Scheduling System) del Instituto de Tecnología de Nanjing, el sistema TISER (Timetable SchedulER) de la Universidad de Tsinghua, Dalian. La gestión inteligente de la organización docente y la programación de cursos de la Universidad de Tecnología, etc. La mayoría de estos sistemas simulan el proceso de programación manual de cursos y utilizan funciones heurísticas para organizarlos en unidades de "clase". Sin embargo, estos horarios sistemáticos dependen a menudo del sistema de enseñanza de cada escuela y no son adecuados para una promoción a gran escala.
A juzgar por el uso real, la practicidad de estos sistemas de software desarrollados en el país y en el extranjero sigue siendo insatisfactoria. Por un lado, la razón es que, al ser un sistema muy complejo, es muy difícil programar todos los aspectos de las clases. Por otro lado, debido a la singularidad de cada escuela, es difícil que el software de programación automática de clases sea universal; práctico, especialmente en la programación. Un pequeño cambio en el proceso provocará un ajuste importante de todo el plan de estudios, lo que significa un cambio importante en todo el plan de estudios de la escuela, lo que es difícil de lograr en aplicaciones reales.
4 Varios algoritmos para resolver problemas NP y sus comparaciones
La resolución de problemas NP completos solo puede depender de algoritmos aproximados, por lo que a continuación se presentan las ideas de diseño de varios algoritmos de uso común, incluidos programación dinámica, algoritmo codicioso, método de retroceso, etc.
El método de programación dinámica consiste en descomponer el problema a resolver en subproblemas nivel por nivel con una escala reducida gradualmente hasta que la solución del subproblema pueda obtenerse directamente. Todos los subproblemas descompuestos jerárquicamente forman un árbol de subproblemas. Las raíces son el problema original. La solución del problema original depende de las soluciones de todos los subproblemas del árbol de subproblemas. Los algoritmos de programación dinámica se suelen utilizar para encontrar la solución óptima a un problema en cierto sentido. Para diseñar un algoritmo de programación dinámica, normalmente se pueden seguir los siguientes pasos:
1. Analizar las propiedades de la solución óptima y caracterizar sus características estructurales.
2. Defina recursivamente la solución óptima.
3. Calcular la solución óptima de forma ascendente.
4. Construir una solución óptima a partir de la información obtenida al calcular la solución óptima.
Los pasos 1 a 3 son los pasos básicos del algoritmo de programación dinámica. En situaciones en las que sólo se requiere la solución óptima, se puede omitir el paso 4. Si necesita encontrar una solución óptima al problema, debe realizar el paso 4. En este momento, al calcular la solución óptima en el paso 3, generalmente es necesario registrar más información para que en el paso 4 se pueda construir rápidamente una solución óptima basada en la información registrada.
(2) Algoritmo codicioso
Cuando un problema tiene propiedades de subestructura óptimas, pensaremos en usar programación dinámica para resolverlo, pero a veces existe un método algorítmico más simple y efectivo, es decir, el algoritmo codicioso. Como sugiere el nombre, los algoritmos codiciosos siempre toman la mejor decisión en este momento. En otras palabras, el algoritmo codicioso no se considera en términos de optimización general. Las elecciones que hace son solo elecciones óptimas locales en cierto sentido. Aunque el algoritmo codicioso no puede obtener la solución óptima general para todos los problemas, puede producir la solución óptima general para una amplia gama de problemas, como el problema del camino más corto de fuente única, el problema del árbol de soporte mínimo, etc. en el algoritmo que se muestra. en la figura.
En algunos casos, incluso si el algoritmo codicioso no puede obtener la solución óptima general, su resultado final es una buena solución aproximada a la solución óptima.
El algoritmo más famoso entre los algoritmos codiciosos es el algoritmo de Dijkstra. Se utiliza como algoritmo de enrutamiento para encontrar el camino más corto entre dos nodos. La idea del algoritmo de Dijkstra es: si G tiene n vértices, entonces siempre necesitamos encontrar n-1 caminos más cortos. El método de solución es: prueba preliminar, escriba V0 (vértice inicial) en cada vértice (vértice final) La longitud. del camino, o si hay un camino, sea la longitud del camino el peso del borde, si no hay un camino, sea ∞; Luego genere cada camino más corto en orden creciente de longitud. De hecho, el proceso de generar el camino más corto es agregar continuamente puntos intermedios entre el vértice inicial V y el vértice final W, porque después de generar cada camino más corto, hay un vértice final U del camino, por lo que aquellos que no lo han hecho aún se ha generado El camino del camino más corto será más corto que el camino original porque pasa por U, así que déjelo pasar por U.
(3) Método de retroceso
El método de retroceso se conoce como el "método universal de resolución de problemas". Se puede utilizar para encontrar todas o cualquier solución al problema. En resumen, el método de retroceso es un método de búsqueda sistemático y saltante. Busca desde la raíz de acuerdo con la estrategia de profundidad primero en un árbol de espacio de estados que contiene todas las soluciones al problema. Cada vez que la búsqueda llega a un nodo en el árbol del espacio de estados, siempre se juzga primero si el subárbol enraizado en ese nodo definitivamente no contiene la solución al problema. Si definitivamente no está incluido, omita la búsqueda sistemática del subárbol y continúe buscando sus nodos ancestros capa por capa hasta que encuentre un nodo con hijos no buscados, buscará uno de los nodos secundarios que no se han incluido. lo buscado continúa siendo buscado; de lo contrario, ingrese al subárbol y continúe buscando de acuerdo con la estrategia de profundidad primero. Cuando se utiliza el método de retroceso para encontrar todas las soluciones a un problema, se debe volver a la raíz y se han buscado todos los hijos de la raíz antes de finalizar cuando se utiliza para encontrar cualquier solución al problema, siempre que haya una solución; Si se encuentra el problema, se puede solucionar. Este artículo proviene del blog de CSDN. Indique la fuente al reimprimir: /hanpoyangtitan/archive/2009/04/03/4046709.aspx
.