Prolog实现大学课程排课：查找无时间重叠的科目组合

核心逻辑说明 #

我们需要实现两个核心能力：

• 任意两门课程的时间冲突判断
• 遍历所有科目组合，筛选出无冲突的有效组合

完整补全代码 #

%% lesson(+Day: atom, +Begin: time, +End: time)
%% course(+Class: string, +Lessons: list)
%% subject(+Name: string, +Course: course)
% 测试科目数据
subject('SRE', course('3K2', [lesson(mon ,time(08, 00, 0), time(10, 25, 0))])).
subject('PAV', course('4K5', [lesson(mon, time(14, 55, 0), time(18, 05, 0)), lesson(thu, time(14, 55, 0), time(18, 05, 0))])).
subject('DSI', course('3K2', [lesson(tue, time(08, 00, 0), time(10, 25, 0)), lesson(wed, time(08, 00, 0), time(10, 25, 0))])).
subject('COM', course('3K2', [lesson(tue, time(10, 25, 0), time(12, 05, 0)), lesson(fri, time(11, 20, 0), time(12, 50, 0))])).
subject('TSB', course('3K3', [lesson(tue, time(14, 55, 0), time(18, 05, 0)), lesson(fri, time(14, 55, 0), time(18, 05, 0))])).
subject('TCO', course('4K3', [lesson(tue, time(19, 55, 0), time(23, 05, 0)), lesson(fri, time(19, 55, 0), time(21, 25, 0))])).
subject('PYE', course('2K4', [lesson(thu, time(08, 00, 0), time(10, 25, 0)), lesson(fri, time(08, 00, 0), time(10, 25, 0))])).
subject('LEG', course('3R3', [lesson(thu, time(18, 15, 0), time(19, 45, 0))])).

%% 辅助工具：将time结构转换为总分钟数，忽略秒字段方便比较
time_to_minutes(time(Hour, Min, _), TotalMin) :-
    TotalMin is Hour * 60 + Min.

%% 辅助工具：判断两节单节课是否时间重叠
lesson_overlap(lesson(Day1, Start1, End1), lesson(Day2, Start2, End2)) :-
    % 必须为同一天才可能冲突
    Day1 = Day2,
    time_to_minutes(Start1, S1),
    time_to_minutes(End1, E1),
    time_to_minutes(Start2, S2),
    time_to_minutes(End2, E2),
    % 时间段重叠核心判断：两个区间存在交集
    S1 < E2,
    S2 < E1.

%% overlaps(+Lessons1: list, +Lessons2: list)
%% 判断两个课程的课时列表是否存在时间冲突
overlaps(Lessons1, Lessons2) :-
    member(L1, Lessons1),
    member(L2, Lessons2),
    lesson_overlap(L1, L2),
    !. % 找到一个冲突就直接返回，无需遍历剩余课节

%% 辅助工具：判断单科目与已选科目列表均无冲突
no_conflict(_, []).
no_conflict(subject(_, course(_, Lessons)), [subject(_, course(_, ExistLessons))|Rest]) :-
    \+ overlaps(Lessons, ExistLessons),
    no_conflict(subject(_, course(_, Lessons)), Rest).

%% 辅助工具：校验科目列表内所有科目两两无冲突
valid_schedule([]).
valid_schedule([Sub|Rest]) :-
    no_conflict(Sub, Rest),
    valid_schedule(Rest).

%% scheduler(-ValidSubjects: list)
%% 输出所有无时间冲突的科目组合
scheduler(ValidSubjects) :-
    % 拉取所有候选科目
    findall(subject(Name, Course), subject(Name, Course), AllSubjects),
    % 生成任意科目子集
    subset(AllSubjects, ValidSubjects),
    % 校验子集无冲突
    valid_schedule(ValidSubjects).

使用示例 #

在SWI-Prolog中加载代码后，可通过以下方式查询：

1. 查询所有无冲突的科目组合：

?- scheduler(Valid).

2. 查询指定科目的组合是否有效：

?- scheduler([subject('SRE',_), subject('PAV',_), subject('DSI',_)]).

3. 查询最多可选多少门无冲突的课：

?- length(Valid, N), scheduler(Valid), \+ (length(Valid2, N2), N2 > N, scheduler(Valid2)).

内容的提问来源于stack exchange，提问作者sicro