将需要求解的课表问题逐层分解,直到得到一个最小单元的不可在分解、可以直接求出答案的子问题。分解出来的所有子问题按层次关系构成一颗子问题树。树根是课程表问题。课程表问题的解依赖于子问题树中所有子问题的解。动态规划算法通常用于求一个问题在某种事先设定条件下的最优解。分解步骤如下:
1. 分析最优解的性质,并构造最有解结构。
2. 循环处理各层最优解。
3. 以自底向上的方式计算出最优解。
4. 根据计算最优解时得到的信息,构造一个最优解。
步骤1~3是动态规划算法的基本步骤。在只需要求出最优解的情形,步骤4可以省去。若需要求出问题的一个最优解,则必须执行步骤4。此时,在步骤3中计算最优解时,通常需记录更多的信息,以便在步骤4中,根据所记录的信息,快速地构造出一个最优解。
二、贪心算法
很多排课专家通常使用贪心算法去解决课程表编排问题,兴文排课软件利用人就是贪心算法。贪心算法就是做出在当前看来最好的选择。即:贪心算法并不是从整体最优上考虑,而是作出在某种意义上的局部最优的选择。贪心算法对所有问题不是都能得到整体最优解,但是对于范围相当广的许多问题它能产生整体最优解,如单源最短路径问题,最小支撑树问题等。在一些情况下,即使贪心算法不能得到整体最优解,但其最终结果却是最优解的很好的近似解。
三、回溯法
概括地说,回溯法是一个既带有系统性又带有跳跃性的搜索法。它在包含问题所有解的一颗状态空间树上,按照深度优先的策略,从根出发进行搜索。搜索每到达状态空间树的一个节点,总是先判断以该节点为根的子树是否肯定不包含问题的解。如果肯定不包含,则跳过对该子树的系统搜索,一层一层地向它的祖先节点继续搜索,直到遇到一个还有未被搜索过的儿子的节点,才转向该节点的一个未曾搜索过的儿子节点继续搜索;否则,进入子树,继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时,要回溯到根,且根的所有儿子都已被搜索过才结束;而在用来求问题的任一解时,只要搜索到问题的一个解就可结束。
模拟退火算法用来解决整体最优问题。比如为旅行推销员问题、货郎担问题,求函数极值问题等。 模拟退火算法属于贪心算法,该算法在贪心算法的基础上进行升级,算法过程中引入了随机因素,以一定的概率接受一个比当前解要差的解,并且这个概率随着时间的推移而逐渐降低。