时间表问题中的定额匹配算法  

Grouped matching algorithm accordingto constant on timetable problem

作　　者：王祜民[1] 赵致格 

机构地区：[1]清华大学应用数学系

出　　处：《清华大学学报（自然科学版）》1998年第6期8-11,共4页Journal of Tsinghua University(Science and Technology)

摘　　要：大学排课表是一个多因素优化决策问题。该文提出的最大定额匹配算法，给出了一大类课程的课表编排模型，定额匹配算法是图论中二分图最大匹配算法的推广（匹配常数Ｋ≥１）。清华大学的计算机自动排课表系统ＵＴＰＳ（ｕｎｉｖｅｒｓｉｔｙｔｉｍｅｔａｂｌｅｐｌａｎｎｉｎｇｓｙｓｔｅｍ）已使用１０年，该算法在计算机自动编排课表的过程中起到了重要作用。University timetable planning is a multifactor optimum problem which many researchers inbroad and abroad have pay great attention to for a long time. The university timetable planning system (UTPS) of Tsinghua University have been used for nearly ten years. It shows that the pivotal algorithm of this system is very effective. The paper proposes a maximum grouped matching algorithm according to costant K≥1, that is used in timetable planning of several special course which have students coming from several classes. This algorithm have played a significant rold in the UTPS. The algorithm is heuristic, depthfirst, recursive that used to acquire maximum grouped matching according constant K≥1. Well knowing maximum cardinality matching problem (stable marriages) on bipartite graph is a special case for constant K=1 of the maximum grouped matching problem.

关 键 词：时间表 二分图 匹配树 课表 定额匹配算法 

分 类 号：G642.3[文化科学—高等教育学] O157.5[文化科学—教育学]