As early as 1970s, the course scheduling problem was proved to be a NP-complete problem, that is, the calculation time of the algorithm increased exponentially, which established the theoretical depth of the problem. At present, there is no general algorithm that can completely solve NP problem. However, many NP-complete problems have great practical significance, such as. The well-known routing algorithm is a typical NP-complete problem. Routing needs to find the shortest path from many nodes to complete the transmission of information. Because they are NP-complete problems, many routing algorithms can be applied to solve the course scheduling problem, such as Dijkstra algorithm, the shortest path method of node subtree pruning to construct the network, and so on.
At present, the main idea of studying NP-complete problem is how to reduce its computational complexity. That is, an approximate algorithm is used to simplify the time to solve the problem from exponential growth to polynomial growth. Combining with the timetable problem is to establish a suitable and realistic simplified model, which can greatly reduce the complexity of the algorithm and facilitate the program implementation. This is a lot of ideas to solve the problem of class schedule.
In colleges and universities, the main way to train students is teaching. In teaching activities, there are a series of management work, among which the implementation of teaching plan is an important teaching link. Every semester, managers should sort out the teaching plan, issue the teaching assignment according to the teaching plan, and then arrange the courses according to the teaching assignment. In these teaching scheduling work, there are not only a lot of tedious data sorting work, but also rigorous mental work and a lot of forms to fill out. So the work is very heavy.
In addition, with the promotion of teaching reform and the implementation of "2 1 1" project, the new education system puts forward higher requirements for curriculum arrangement. It is extremely troublesome to send information when arranging courses manually, but when arranging courses by computer, the information in teaching can be clear at a glance, which is of great significance for optimizing students' learning process, evaluating each teacher's contribution to teaching and guiding reasonable decision-making, and will greatly promote the virtuous circle of teaching.
2 Application fields of this discipline
The research of this topic has a guiding role in developing the course arrangement system in colleges and universities.
The core of course arrangement is the conflict and preemption of multi-dimensional resources, and the research on it is also a reference for similar problems (especially those related to timetable, such as examination room arrangement, theater seating arrangement, airline, etc.).
3 the status of the project
At the end of 1990s, some people abroad began to study curriculum arrangement. 1962, Gotlieb put forward the mathematical model of timetable problem, and solved the three-dimensional linear transportation problem with Hungarian algorithm. After that, people have done a lot of in-depth discussions on the existence of the algorithm and solution of the timetable problem. However, the mathematical model used in most literatures is a simplification or supplement to Gotlieb's mathematical model. So far, there is no feasible algorithm to solve the timetable problem.
In recent 40 years, people have made many attempts to solve the problem of class schedule with computers. Among them, the integer programming model of course scheduling reduces the problem to the solution of a set of 0- 1 variables, but its calculation is very large. The branch-and-bound technique for solving 0- 1 linear optimization problem is only suitable for small-scale course scheduling problem. Mihoc and Balas( 1965) formulated the curriculum as an optimization problem, while Krawczk proposed a linear programming method. Junginger simplified the timetable problem as a three-dimensional transportation problem, while Tripathy regarded the timetable problem as an integer linear programming problem and put forward a mathematical model of university timetable.
In addition, some literatures try to solve the problem of timetable from the perspective of graph theory, but the coloring problem of graph is NP-complete. Only in extremely simple cases can the timetable be transformed into a bipartite graph matching problem. This mathematical model is far from reality and has no practical value for the arrangement of curriculum in most schools.
After entering the 1990s, the research on curriculum abroad is still very active. Representative figures are ArabindaTripathy from the School of Management, Poole University, Vasta, and Jean Aubin and Jacques Ferland from the University of Montreal. At present, there are many methods to solve the problem of timetable method, such as artificial timetable method, graph theory method, Lagrange method, secondary distribution method and so on. Due to the complex constraints of the curriculum, the scale of the problem often increases sharply when it is described by mathematical methods, which becomes a huge obstacle to the application of mathematical planning to solve curriculum problems. Foreign research shows that it is not feasible to solve the large-scale course scheduling problem simply by mathematical method, but it will be a promising method to decompose the problem by using the hierarchical planning idea in operational research.
The research on curriculum in China began in the early 1980s, with UTSS (a university timetable arrangement system) of Nanjing University of Science and Technology, TISER (curriculum arrangement system) of Tsinghua University, intelligent teaching organization management and curriculum arrangement of Dalian University of Technology, etc. Most of these systems simulate the manual course arrangement process and use heuristic functions to arrange courses. However, these systematic course scheduling systems often depend on the teaching systems of various schools and are not suitable for wide-scale promotion.
Judging from the actual use, the practicability of these software systems developed at home and abroad is still not satisfactory. On the one hand, as a very complicated system, it is very difficult to arrange courses in all aspects; On the other hand, due to the particularity of each school, automatic course scheduling software is difficult to be widely used, especially in the course scheduling process, a small change will cause a big adjustment of all courses, which means a big change of the whole school curriculum, which is difficult to achieve in practical application.
4 Several algorithms for solving NP problems and their comparison
Solving NP-complete problem can only rely on approximate algorithm, so the following introduces the design ideas of several commonly used algorithms, including dynamic programming, greedy algorithm, backtracking method and so on.
Dynamic programming method is to decompose the solved problem into sub-problems with decreasing scale step by step until the sub-problems of its solution can be solved directly. All the decomposed subproblems form a subproblem tree according to the hierarchical relationship. The root cause is the original problem. The solution of the original problem depends on the solutions of all subproblems in the subproblem tree. Dynamic programming algorithm is usually used to find the optimal solution of a problem in a sense. Design a dynamic programming algorithm, usually according to the following steps:
1. Analyze the properties of the optimal solution and characterize its structural characteristics.
2. Recursively define the optimal solution.
3. Calculate the optimal solution in a bottom-up way.
4. According to the information obtained when calculating the optimal solution, construct an optimal solution.
Step 1~3 is the basic step of dynamic programming algorithm. In the case that only the optimal solution needs to be found, step 4 can be omitted. If you need to find the best solution to the problem, you must perform step 4. At this time, when calculating the optimal solution in step 3, it is usually necessary to record more information so that in step 4, the optimal solution can be quickly constructed according to the recorded information.
greedy algorithm
When a problem has the optimal substructure property, we will think of using dynamic programming to solve it, but sometimes there is a simpler and more effective algorithm, that is greedy algorithm. As the name implies, the greedy algorithm always makes the best choice at present. In other words, the greedy algorithm is not considered in the global optimization, and his choice is only a local optimal choice in a sense. Although the greedy algorithm can't get the global optimal solutions of all problems, it can produce the global optimal solutions of many problems with a wide range, such as the single-source shortest path problem and the minimum spanning tree problem in the algorithm shown in the figure. In some cases, even if the greedy algorithm cannot get the global optimal solution, the final result is a good approximate solution of the optimal solution.
Among greedy algorithms, Dijkstra algorithm is the most famous one. It is used as a routing algorithm to find the shortest path between two nodes. The idea of Dijkstra algorithm is that if G has n vertices, we always need to find n- 1 shortest paths. The solution is as follows: first, try to write the path length from V0 (the starting vertex) to each vertex (the final vertex), or if there is a path, make the path length the weight of the edge; Or no path, then it is ∞. Then each shortest path is generated in the order of increasing length. In fact, the process of generating the shortest path is the process of increasing intermediate points between the starting vertex V and the ending vertex W. Because every shortest path has a final vertex U after it is generated, those paths that have not yet generated the shortest path will be shorter than the original path because they pass through U, so let it pass through U.
(3) backtracking method
Backtracking method is known as "universal problem solving method". It can be used to find all or any solution to the problem. Generally speaking, backtracking is a systematic and jumping search method. It searches from the root in the state space tree containing all the solutions of the problem according to the depth-first strategy. Every time a node of the state space tree is searched, it is always judged whether the subtree with the node as the root definitely does not contain the solution of the problem. If it is definitely not included, it skips the system's search for the subtree, and continues to search for its ancestor node layer by layer until it meets an unsearchable child node, and then turns to the unsearchable child node of the node to continue the search; Otherwise, enter the subtree and continue the search according to the depth-first strategy. When solving all the solutions of the problem by backtracking method, we should backtrack to the root, and all the children of the root have been searched before the end; When it is used to find any solution to a problem, it can be ended as long as a solution to the problem is found.
Come on!