通用高校排课算法的研究

课题背景与研究意义
排课问题早在70年代就证明是一个NP完全问题，即算法的计算时间是呈指数增长的，这一论断确立了排课问题的理论深度。对于NP问题完全问题目前在数学上是没有一个通用的算法能够很好地解决。然而很多NP完全问题目具有很重要的实际意义，例如。大家熟悉地路由算法就是很典型的一个NP完全问题，路由要在从多的节点中找出最短路径完成信息的传递。既然都是NP完全问题，那么很多路由算法就可以运用到解决排课问题上，如Dijkstra算法、节点子树剪枝构造网络最短路径法等等。

Topic background and significance
Course Scheduling problems as early as the 1970s to prove to be an NP-complete problems, namely, the algorithm for computing time is growing exponentially, this thesis established the theoretical depth of the course arrangement. The NP-complete problems in mathematics is not a generic algorithm can solve well. However, many NP-complete heads have a very important practical significance, for example. We are familiar with the routing algorithm is very typical of an NP-complete problems, routing to the number of nodes find the shortest path to complete the transfer of information. Since the NP-complete problems are, then a lot of routing algorithm can be applied to resolve the issue of arranging schedule, such as Dijkstra algorithm, the node network structure of the tree pruning the shortest path method, and so on.

4800字