具有优先级的未实现分布

Question

我正在处理gnu的发行问题。我试着根据时间条件把老师分配给几个学校科目。理想情况下的代码如下。

soln(X) :-
    X = [T1M, T1E, T1H, T2M, T2E, T2H, T3M, T3E, T3H],
    fd_domain(X, 0, 10),

    %% subject constraints
    T1M + T2M + T3M #= 6,
    T1E + T2E + T3E #= 6,
    T1H + T2H + T3H #= 6,

    %% teacher constraints b/w 0 and 6 hrs
    0 #=< T1M + T1E + T1H, T1M + T1E + T1H #=< 6,
    0 #=< T2M + T2E + T2H, T2M + T2E + T2H #=< 6,
    0 #=< T3M + T3E + T3H, T3M + T3E + T3H #=< 6,
    fd_labeling(X).

上面的变量X让所有的三位教师都有他们的学科，他们能够教书。T代表教师，1是人的ID，M=数学，E=英语和H=历史。这门学科的限制意味着每门课每周需要教6个小时。教师的约束规定了他们每周所能教的最少和最长的时间。

这个例子非常有效，因为所有的约束条件都是偶数的，而且方程也很简单。但是，我面临着教师无法与学科约束相匹配的情况。因此，如果发生这种情况，代码就无法工作。

soln(X) :-
    X = [T1M, T1E, T1H, T2M, T2E, T2H, T3M, T3E, T3H],
    fd_domain(X, 0, 10),

    %% subject constraints
    T1M + T2M + T3M #= 6,
    T1E + T2E + T3E #= 6,
    T1H + T2H + T3H #= 6,

    %% teacher constraints b/w 0 and 6 hrs
    0 #=< T1M + T1E + T1H, T1M + T1E + T1H #=< 4,
    0 #=< T2M + T2E + T2H, T2M + T2E + T2H #=< 4,
    0 #=< T3M + T3E + T3H, T3M + T3E + T3H #=< 6,
    fd_labeling(X).

此代码将不返回任何解决方案。他们的回应只是“不”。

这就是为什么我将主题约束放宽到#<而不是#=的原因，但这.

soln(X) :-
    X = [T1M, T1E, T1H, T2M, T2E, T2H, T3M, T3E, T3H],
    fd_domain(X, 0, 10),

    %% subject constraints
    T1M + T2M + T3M #=< 6,
    T1E + T2E + T3E #=< 6,
    T1H + T2H + T3H #=< 6,

    %% teacher constraints b/w 0 and 6 hrs
    0 #=< T1M + T1E + T1H, T1M + T1E + T1H #=< 4,
    0 #=< T2M + T2E + T2H, T2M + T2E + T2H #=< 4,
    0 #=< T3M + T3E + T3H, T3M + T3E + T3H #=< 6,
    fd_labeling(X).

...will的结果是X = [0,0,0,0,0,0,0,0,0] ?，所以Prolog只是完全填充了最小条件。

为了描述我需要的结果，我将使它更加简单。

学校的科目:数学-英语-历史，这三门课每周都要教6个小时。

教师1可以每周3小时教授数学和英语，2可以每周8小时教授英语和历史，3可以每周2小时教授数学和历史

我的第一个要求是按给定的顺序排列主题的优先顺序。我的意思是，数学首先要包括在内。因此，如果没有足够的教师，所有可能的时间都需要分配给数学。如果数学得到尽可能多的时间，即使是这样，也意味着它还没有完全覆盖，那么英语就是下一个要讨论的问题。这也是我的第二个要求，要尽可能接近需求，而不是停留在最低限度。

对于上面给出的例子，我的预期结果是:老师1和老师3被分配给数学，因为它是第一优先科目。他们都只会得到5，而不是所需的6个小时，但我希望它得到一个可能的接近。所以两位老师都百分之百地学习数学。从老师2开始，6小时将分配给英语。这是因为它是第二个优先主题，需要6个小时才能涵盖。剩下的两个小时将成为历史。

数学:5小时(老师1+老师3)英语:6小时(教师2)历史:2小时(教师2)

我读到在gnu-prolog中有fd_maximize。这听起来很有可能解决我的问题，但到目前为止我还不能使它发挥作用。它总是在错误中解决。还有我想要达到的目标吗？

提前谢谢大家。

Answer 1

我想和你分享我正在寻找的解决方案。我希望这能对任何有同样问题的人有所帮助。

所以我在找两样东西。尽可能接近主题需求，并为主题使用优先级。我的一个朋友想出了一个很酷的逻辑来解决这个问题。下面是我在最初的文章中所写的例子的代码。

soln(T1M,T1E,T2E,T2H,T3M,T3H) :-
    VARIABLES = [
        T1M,                           % Teacher 1 can teach Math
        T1E,                           % Teacher 1 can teach English
        T2E,                           % Teacher 2 can teach English
        T2H,                           % Teacher 2 can teach History
        T3M,                           % Teacher 1 can teach Math
        T3H,                           % Teacher 1 can teach History
        PM,                            % If we cannot cover the Math hours, there will be PM penalities
        PE,                            % If we cannot cover the English hours, there will be PE penalities
        PH                             % If we cannot cover the History hours, there will be PH penalities
    ],

    fd_domain(VARIABLES, 0, 10),       % Each of the variables can take 0 to 10 (at most 8 for this case, larger is okay)

    % Constraints for teachers
    T1M + T1E #=< 3,                   % Teacher 1 can have at most 3 hours
    T2E + T2H #=< 8,                   % Teacher 2 can have at most 8 hours
    T3M + T3H #=< 2,                   % Teacher 3 can have at most 2 hours

    % Constraints for subjects         % To prevent the solver to fail solving when the constraint cannot match
    T1M + T3M + PM #= 6,               % Instead of insisting there must be at least 6 hours
    T1E + T2E + PE #= 6,               % but it will be penalized by the optimizer
    T2H + T3H + PH #= 6,               % below

    % Constraints for penalities       % penalities can only be positive
    PM #>= 0,
    PE #>= 0,
    PH #>= 0,

    %% Optimization
    F #= PM * 100 + PE * 10 + PH,      % Note how we use the multipliers to enforce the priority, the optimizer will 
                                       % always optimize for math first because it is penalized heavily
                                       % F can reach 0 only if the constraints are feasible

    fd_minimize(fd_labeling(VARIABLES), F).

main :- soln(T1M,T1E,T2E,T2H,T3M,T3H),
    write('Teacher 1 spent '), write(T1M), write(' hours on Math'),nl,
    write('Teacher 1 spent '), write(T1E), write(' hours on English'),nl,
    write('Teacher 2 spent '), write(T2E), write(' hours on English'),nl,
    write('Teacher 2 spent '), write(T2H), write(' hours on History'),nl,
    write('Teacher 3 spent '), write(T3M), write(' hours on Math'),nl,
    write('Teacher 3 spent '), write(T3H), write(' hours on History'),nl.

我希望你觉得这有帮助。至少它解决了我的问题。我也很抱歉，如果我最初的问题不够清楚，导致这个解决方案。

顺便说一句，我想和你们分享我在这个过程中的另外两个洞察力。我不清楚这个求解器只能处理整数值。我的真实生活数据是使用十进制值。我把这个解决方案用于一所有45名教师的学校。在这种情况下，由于值的数量(2小时是我等待的时间最长的^^)，gnu-prolog变得非常慢。这就是我停止在这个项目上使用的原因，我现在正试图在R中解决它。

Answer 2

最初的学科约束意味着所有Tij =3*6= 18的总和。因此，对教师的约束(以不同的顺序表示相同的总和)不能< 18。因此，您的表述方式如下：

    %% subject constraints
    T1M + T2M + T3M #= 6,
    T1E + T2E + T3E #= 6,
    T1H + T2H + T3H #= 6,

    %% teacher constraints b/w 0 and 6 hrs
    0 #=< T1M + T1E + T1H, T1M + T1E + T1H #=< 4,
    0 #=< T2M + T2E + T2H, T2M + T2E + T2H #=< 4,
    0 #=< T3M + T3E + T3H, T3M + T3E + T3H #=< 6,

没有解决方案(因此gprolog回答了No )。

顺便说一下，表单0 #=< T1M + T1E + T1H的约束是无用的:所有变量都是≥0，它们的和也是≥0。

放松所有约束，就像您在任何地方用#=替换所有‘#=<’一样，提供了许多解决方案，第一个解决方案都是Tij = 0。您可以使用fd_maximize寻找更有趣的解决方案(见下文)。

这是一个版本，其中对科目的限制保持在6，而对教师的限制被放宽为≤6(不能像上面解释的那样<6)。它使和最大化(并以F的形式返回)。

soln(X, F) :-
    X = [T1M, T1E, T1H, T2M, T2E, T2H, T3M, T3E, T3H],
    fd_domain(X, 0, 10),

    %% subject constraints
    T1M + T2M + T3M #= 6,
    T1E + T2E + T3E #= 6,
    T1H + T2H + T3H #= 6,

    %% teacher constraints b/w 0 and 6 hrs
    T1M + T1E + T1H #=< 6,
    T2M + T2E + T2H #=< 6,
    T3M + T3E + T3H #=< 6,

    %% Optimization: objective function (value put in a variable F)
    F #= T1M + T1E + T1H + T2M + T2E + T2H + T3M + T3E + T3H,
    
    fd_maximize(fd_labeling(X), F).

执行给出：

| ?- soln(L, F).

L = [0,0,6,0,6,0,6,0,0]
F = 18 ? ;

L = [0,0,6,1,5,0,5,1,0]
F = 18 ? ;

L = [0,0,6,2,4,0,4,2,0]
F = 18 ? ;

L = [0,0,6,3,3,0,3,3,0]
F = 18 ? a
...

有406种解决办法。

如果您想要“平衡”分布以最小化教师之间的差异，您可以将所有Tij的最小值最大化如下：

soln(X, F) :-
    X = [T1M, T1E, T1H, T2M, T2E, T2H, T3M, T3E, T3H],
    fd_domain(X, 0, 10),

    %% subject constraints
    T1M + T2M + T3M #= 6,
    T1E + T2E + T3E #= 6,
    T1H + T2H + T3H #= 6,

    %% teacher constraints b/w 0 and 6 hrs
    T1M + T1E + T1H #=< 6,
    T2M + T2E + T2H #=< 6,
    T3M + T3E + T3H #=< 6,

    %% Optimization: objective function (value put in a variable F)
    min(X, F),
    
    fd_maximize(fd_labeling(X), F).


min([X], X) :-
    !.

min([X|Xs], M) :-
        M #= min(X, M1),
        min(Xs, M1).

现在只有一个解决方案：

| ?- soln(L, F).                  

F = 2
L = [2,2,2,2,2,2,2,2,2]

Answer 3

您的初始问题没有解决方案(我们称之为过度约束问题)，但是您希望找到一个放松一些约束的解决方案。

首先，一个过度约束的问题通常是(多？)比承认至少一个解决方案的问题更难解决(因为发现它没有解决方案需要对搜索空间进行彻底的探索)。

在目前的情况下，我们可以通过在有关主题的约束中添加人工变量来缓解问题：

    T1M + T2M + T3M #= 6,
    T1E + T2E + T3E #= 6,
    T1H + T2H + T3H #= 6,

成为

    T1M + T2M + T3M + A1 #= 6,
    T1E + T2E + T3E + A2 #= 6,
    T1H + T2H + T3H + A3 #= 6,

其中A1, A2, A3是新的人工变量。这样，我们用不等式(≤)代替方程(=)，因为所有的Aj都是正的。为了避免所有Tij =0的解，我们可以要求一个最小和Aj与fd_minimize的解。我们甚至可以考虑系数的优先级(数学3，英语2，历史1)。我们称这些系数为权值。以下是节目：

soln(X, F) :-
    X = [T1M, T1E, T1H, T2M, T2E, T2H, T3M, T3E, T3H],
    fd_domain(X, 0, 10),

    %% subject constraints
    T1M + T2M + T3M + A1 #= 6,
    T1E + T2E + T3E + A2 #= 6,
    T1H + T2H + T3H + A3 #= 6,

    %% teacher constraints b/w 0 and 6 hrs
    T1M + T1E + T1H #=< 4,
    T2M + T2E + T2H #=< 4,
    T3M + T3E + T3H #=< 6,

    %% Optimization: objective function (value put in a variable F)
    F #= 3*A1 + 2*A2 + A3,
    
    fd_minimize(fd_labeling(X), F).

解决办法：

| ?- soln(L, F).

F = 4
L = [0,2,2,0,4,0,6,0,0] ? ;

F = 4
L = [0,2,2,1,3,0,5,1,0] ? ;

F = 4
L = [0,2,2,2,2,0,4,2,0] ? a (to obtain all solutions)

...

有101个解决方案。