1

我目前正在开发一个答案集程序来为一所学校创建一个时间表。我使用的规则库类似于：

teacher(a). teacher(b). teacher(c). teacher(d). teacher(e). teacher(f).teacher(g).teacher(h).teacher(i).teacher(j).teacher(k).teacher().teacher(m).teacher(n).teacher(o).teacher(p).teacher(q).teacher(r).teache(s).teacher(t).teacher(u).

teaches(a,info). teaches(a,math). teaches(b,bio). teaches(b,nawi). teaches(c,ge). teaches(c,gewi). teaches(d,ge). teaches(d,grw). teaches(e,de). teaches(e,mu). teaches(f,de). teaches(f,ku). teaches(g,geo). teaches(g,eth). teaches(h,reli). teaches(h,spo). teaches(i,reli). teaches(i,ku). teaches(j,math). teaces(j,chem). teaches(k,math). teaches(k,chem). teaches(l,deu). teaches(l,grw). teaches(m,eng). teaches(m,mu). teachs(n,math). teaches(n,geo). teaches(o,spo). teaches(o,fremd). teaches(p,eng). teaches(p,fremd). teaches(q,deu). teaches(q,fremd). teaches(r,deu). teaches(r,eng). teaches(s,eng). teaches(s,spo). teaches(t,te). teaches(t,eng). teaches(u,bio). teaches(u,phy).

subject(X) :- teaches(_,X).

class(5,a). class(5,b). class(6,a). class(6,b). class(7,a). class(7,b). class(8,a). class(8,b). class(9,a). class(9,b). class(10,a). class(10,b).

%classes per week (for class 5 only at the moment)
classperweek(5,de,5). classperweek(5,info,0). classperweek(5,eng,5). classpereek(5,fremd,0). classperweek(5,math,4). classperweek(5,bio,2). classperweek(5,chem,0). classperweek(5,phy,0). classperweek(5,ge,1). classperweek(5,grw,0). cassperweek(5,geo,2). classperweek(5,spo,3). classperweek(5,eth,2). classperwek(5,ku,2). classperweek(5,mu,2). classperweek(5,tec,0). classperweek(5,nawi,0) .classperweek(5,gewi,0). classperweek(5,reli,2).

room(1..21).

%for monday to friday
weekday(1..5). 

%for lesson 1 to 9 
slot(1..9).

为了创建一个时间表，我想创建我正在使用的所有谓词的所有可能组合，然后过滤所有错误的答案。这就是我创建时间表的方式：

{timetable(W,S,T,A,B,J,R):class(A,B),teacher(T),subject(J),room(R)} :- weekday(W), slot(S).

到目前为止，一切正常，除了这个解决方案可能相对低效。

为了过滤没有班级同时使用同一个房间，我制定了以下约束。

:- timetable(A,B,C,D,E,F,G), timetable(H,I,J,K,L,M,N), A=H, B=I, G=N, class(D,E)!=class(K,L).

看起来这会导致问题如此之大，以至于接地失败，因为我收到以下错误消息

clingo version 5.4.0
Reading from timetable.asp
Killed

因此，我一直在寻找一种方法来创建不同的时间表实例，而不会得到由选择规则创建的太多“无意义”的答案。我想到的一种可能性是使用否定循环。因此，您可以将 choiserule 替换为 {a;b}并a :- not b. b :- not a.排除所有房间被占用两次的情况。不幸的是，我对这种方法的理解不足以将其应用于我的问题。

经过大量的反复试验（和在线搜索），我还没有找到一个解决方案来消除选择规则，同时消除房间和教师的重复。

因此，我想知道我是否可以使用这种方法来解决我的问题，或者是否有另一种方法根本不创建许多毫无意义的答案集。

编辑：规则库现在可以工作，并更新了第 5 课的每节课时数

4

1 回答 1

0

我认为您正在寻找类似的东西：

% For each teacher and each timeslot, pick at most one subject which they'll teach and a class and room for them.
{timetable(W,S,T,A,B,J,R):class(A,B),room(R),teaches(T,J)} <= 1 :- weekday(W);slot(S);teacher(T).

% Cardinality constraint enforcing that no room is occupied more than once in the same timeslot on the timetable.
:- #count{uses(T,A,B,J):timetable(W,S,T,A,B,J,R)} > 1; weekday(W); slot(S); room(R).

替换你的两条规则。

请注意，这种方式 cligo 不会为教授他们不知道的科目的教师生成虚假的基础术语。此外，通过使用与二元子句相反的基数约束，您可以大大减少接地大小（从房间数量的 O(n^2) 到 O(n)）。

顺便说一句，由于输入中的拼写错误，您可能会丢失答案。我建议将其表述为：

teacher(a;b;c;d;e;f;g;h;i;j;k;l;m;n;o;p;q;r;s;t;u).
teaches(
    a,info;
    a,math;
    b,bio;
    b,nawi;
    c,ge;
    c,gewi;
    d,ge;
    d,grw;
    e,de;
    e,mu;
    f,de;
    f,ku;
    g,geo;
    g,eth;
    h,reli;
    h,spo;
    i,reli;
    i,ku;
    j,math;
    j,chem;
    k,math;
    k,chem;
    l,deu;
    l,grw;
    m,eng;
    m,mu;
    n,math;
    n,geo;
    o,spo;
    o,fremd;
    p,eng;
    p,fremd;
    q,deu;
    q,fremd;
    r,deu;
    r,eng;
    s,eng;
    s,spo;
    t,te;
    t,eng;
    u,bio;
    u,phy
).
subject(X) :- teaches(_,X).
class(
    5..10,a;
    5..10,b
).
%classes per week (for class 5 only at the moment)
classperweek(
    5,de,5;
    5,info,0;
    5,eng,5;
    5,fremd,0;
    5,math,4;
    5,bio,2;
    5,chem,0;
    5,phy,0;
    5,ge,1;
    5,grw,0;
    5,geo,2;
    5,spo,3;
    5,eth,2;
    5,ku,2;
    5,mu,2;
    5,tec,0;
    5,nawi,0;
    5,gewi,0;
    5,reli,2
).
room(1..21).
%for monday to friday
weekday(1..5).

%for lesson 1 to 9 
slot(1..9).
于 2021-01-02T19:23:30.000 回答