prolog - 使用逻辑编程使用共享资源调度任务

Question

Time 5, 3, 8, 2, 7, 3, 9, 3, 3, 5, 7

您必须将玩家(使用时间)安排到三个不同的淋浴间。获得最佳解决方案。
到目前为止，我的解决方案是:

use_module(library(clpfd)).

shower(S, E, D, Done) :- 
    D = [5, 3, 8, 2, 7, 3, 9, 3, 3, 5, 7],
    R =  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    length(D, N),
    length(S, N),
    length(E, N),
    domain(S, 0, 100),
    domain(E, 0, 100),
    Done in 0..100,
    ready(E, Done),
    tasks(S, D, E, R, Tasks),
    cumulative(Tasks, [limit(3)]),
    labeling([minimize(Done)], [Done|S]).

tasks([], [], [], [], []).
tasks([S|Ss], [D|Ds], [E|Es], [R|Rs], [T|Ts]) :-
    T = task(S, D, E, R, 0),
    tasks(Ss, Ds, Es, Rs, Ts).

ready([], _).
ready([E|Es], Done) :-
    Done #>= E,
    ready(Es, Done).

如果我运行程序:

?- shower(S,D).

它会打印:

D = 19,
S = [0,0,0,3,5,5,8,8,11,14,12]

Done 是总时间(最长时间)，S 是每个任务的开始时间，E 是每个任务的结束时间，D 是任务的持续时间。

到现在为止还挺好。

但是现在，我正在为其他事情而苦苦挣扎。恰恰:

1)我怎样才能打印哪个玩家正在使用哪个淋浴？

2)我如何限制一个淋浴最多可以运行四名玩家？

我是 Prolog 的新手，很可能这可能是我在上面编写的最后一个程序。到目前为止我设法做到了这一点，但我需要完成这个(你猜对了，这是一项任务)。这是我在本类(class)中必须做的最后一件事，而且我以前从未做过任何约束逻辑编程。

感谢您阅读并最终回复此内容!

Answer 1

好问题，+1!

这是解决它的一种方法:假设您已经找到满足资源限制的计划。然后，您只需描述必须额外保留的内容，以便可以以所需方式将任务分配给机器。

例如:

distribution(Starts, Ends, Machines) :-
        pairs_keys_values(Pairs, Starts, Ends),
        length(Ms0, 4),
        maplist(=(0-[]), Ms0),
        foldl(task_machines0_machines, Pairs, Ms0, Ms1),
        pairs_values(Ms1, Machines0),
        maplist(reverse, Machines0, Machines1),
        msort(Machines1, Machines).

task_machines0_machines(Start-End, Ms0, [End-[Start|Starts]|Ms1]) :-
        Start #>= OccupiedUntil,
        select(OccupiedUntil-Starts, Ms0, Ms1),
        L #=< 2,
        length(Starts, L).

Machines每台机器包含一个列表，其中每个列表依次包含分配给该机器的任务的开始时间。

我将更准确地识别任务作为一个简单的练习。

示例用法及其结果:

?- shower(Starts, Ends, _, _), distribution(Starts, Ends, Machines).
Starts = [0, 0, 0, 1, 2, 3, 0],
Ends = [3, 3, 1, 2, 3, 4, 4],
Machines = [[0], [0], [0, 1, 2], [0, 3]] .

让我们看看在 的总持续时间内有多少独特的解决方案4 时隙，由于资源限制，我们已经知道这是最小值:

?- setof(Ms, Starts^Ends^Ds^(shower(Starts, Ends, Ds, 4),
                             distribution(Starts, Ends, Ms)),
         Mss),
   length(Mss, L).
Mss = [[[0], [0, 1], [0, 3], [0, 3]], ...]
L = 14.

这是实际唯一解决方案数量的下限，我们只有在考虑唯一任务标识符而不是开始时间时才能计算。

我已经这样做了，并找到了 20 种方法来分配受所有约束的任务，交替使用机器:

distributions([
    [[1],[2,3],[4,5,6],[7]], [[1],[2,4],[3,5,6],[7]], [[1],[2,5],[3,4,6],[7]],
    [[1],[2,6],[3,4,5],[7]], [[1,3],[2],[4,5,6],[7]], [[1,3],[2,4],[5,6],[7]],
    [[1,3],[2,5],[4,6],[7]], [[1,3],[2,6],[4,5],[7]], [[1,4],[2],[3,5,6],[7]],
    [[1,4],[2,3],[5,6],[7]], [[1,4],[2,5],[3,6],[7]], [[1,4],[2,6],[3,5],[7]],
    [[1,5],[2],[3,4,6],[7]], [[1,5],[2,3],[4,6],[7]], [[1,5],[2,4],[3,6],[7]],
    [[1,5],[2,6],[3,4],[7]], [[1,6],[2],[3,4,5],[7]], [[1,6],[2,3],[4,5],[7]],
    [[1,6],[2,4],[3,5],[7]], [[1,6],[2,5],[3,4],[7]]
  ]).