Prolog 时间重叠问题

Question

假设我有这个知识库:

free(ann,slot(time(8,0),time(9,0))).
free(ann,slot(time(10,0),time(11,0))).

free(bob,slot(time(7,0),time(8,30))).
free(bob,slot(time(10,0),time(11,0))).

free(carla,slot(time(8,0),time(9,0))).
free(carla,slot(time(10,0),time(10,15))).

因此，经过大量努力，我设法编写了一些内容，使用以下代码打印在特定时段内第一个有空的人:

meetone(Person, slot(time(BeginHour, BeginMinute), time(EndHour, EndMinute)))
:- free(Person, slot(time(BH, BM), time(EH, EM))),
   BH*60 + BM =< EndHour*60 + EndMinute,
   EH*60 + EM >= BeginHour*60 + BeginMinute.

main :- (meetone(Person,slot(time(7,15),time(7,20))); halt),
       write(Person),
       nl,
       halt.

:- initialization(main).

这将打印 bob，即预期结果。

这就是事情变得复杂的地方(至少对我来说)。假设我想找出知识库中每个人共有的所有时间段。以下代码演示了我最终想要如何调用它:

people([ann,bob,carla]).

meet :- ???

main :- (setof(Slot,meet(Slot),Slots); halt),
        write(Slots),
        nl,
        halt.

:- initialization(main).

这里有一些模糊的伪代码，我认为它们可能会实现我正在寻找的目标，但我没有足够的经验来让它工作。

1. 从第一人的空闲位置开始。
2. 递归遍历人员列表的其余部分，找到重叠时间。
3. 可以使用类似于 meetone 的方法来验证插槽是否重叠；经过此验证后，可以使用两个时隙的开始时间的最大值和两个结束时间的最小值来找到确切的重叠周期。
4. 打印最终的槽位列表。

最终输出将显示 8:00 - 8:30 和 10:00 - 10:15 的时段。任何帮助实现这一目标的帮助将不胜感激。

Answer 1

Prolog 有一些语法特征，恕我直言，确实有助于编写易于理解的代码。那么这是你的问题，利用运算符来获得可读性:

free(ann, 08:00 > 09:00).
free(ann, 10:00 > 11:00).

free(bob, 07:00 > 08:30).
free(bob, 10:00 > 11:00).

free(carla, 08:00 > 09:00).
free(carla, 10:00 > 10:15).

meetone(Person, Slot) :- free(Person, SlotP), contains(SlotP, Slot).

contains(Slot1, Slot2) :-
   timepoints(Slot1, B1, E1),
   timepoints(Slot2, B2, E2),
   B1 =< E2, E1 >= B2.

timepoints(BH:BM > EH:EM, B, E) :-
   B is BH*60 + BM,
   E is EH*60 + EM.

main :- setof(Person, meetone(Person, 7:15 > 7:20), Available),
    maplist(writeln, Available).

我试图引入两个实用程序，一种可重用的代码:contains/2 和 timepoints/3。拥有这样的片段可以帮助编写更复杂的逻辑......

运行这段代码，我明白了

?- main.
bob
true.

现在回答你的主要问题:

Let's say I want to find out all the time slots everyone in the Knowledge Base has in common

我将开始编写一个 common_timeslot/3，解释(计算)预期的内容:

common_timeslot(S1, S2, Common) :-
   timepoints(S1, B1, E1),
   timepoints(S2, B2, E2), 
   % do you mean intersection by common ?
   ...

否则，仅考虑身份

common_timeslot(S, S, S).

定义了这个之后，所有的公共(public)资源都可以通过

找到

main :-
    setof(Sc/P/Q, Sp^Sq^(
        free(P, Sp), free(Q, Sq), Q \= P,
        common_timeslot(Sp, Sq, Sc)
    ), Commons),
    maplist(writeln, Commons).

结果

?- main.
(8:0>9:0)/ann/carla
(8:0>9:0)/carla/ann
(10:0>11:0)/ann/bob
(10:0>11:0)/bob/ann
true.

编辑记录垫子评论，现在我发布整个程序

free(ann, 08:00 < 09:00).
free(ann, 10:00 < 11:00).

free(bob, 07:00 < 08:30).
free(bob, 10:00 < 11:00).

free(carla, 08:00 < 09:00).
free(carla, 10:00 < 10:15).

meetone(Person, Slot) :- free(Person, SlotP), contains(SlotP, Slot).

contains(Slot1, Slot2) :-
   timepoints(Slot1, B1, E1),
   timepoints(Slot2, B2, E2),
   B1 =< E2, E1 >= B2.

timepoints(BH:BM < EH:EM, B, E) :-
    (   ( var(B), var(E) )
    ->  B is BH * 60 + BM,
        E is EH * 60 + EM
    ;   BH is B // 60,
        BM is floor(B mod 60),
        EH is E // 60,
        EM is floor(E mod 60)
    ).

% common_timeslot(S, S, S).
common_timeslot(S1,S2,S) :-
    timepoints(S1,B1,E1),
    timepoints(S2,B2,E2),
    B is max(B1,B2),
    E is min(E1,E2),
    B < E,
    timepoints(S,B,E).

% base case: C passed all commonality test
check_common(C, [], C).

% S is the current common, to be checked for availability on person P
check_common(S, [P|Ps], C) :-
    free(P, Sp),
    common_timeslot(S, Sp, Ct),
    check_common(Ct, Ps, C).

main :- setof(P, S^free(P,S), [FirstP|Others]),
    forall(free(FirstP, S), (
        check_common(S, Others, C),
        writeln(FirstP:C)
    )).

结果

?- main.
ann: (8:0<8:30)
ann: (10:0<10:15)
true.

主要变化是 timepoints/3 现在是“双向”的。然后我按照您在评论中的解释介绍了 common_timeslot/3 。

我认为您会欣赏这些小的句法抽象有助于拥有清晰的“应用”逻辑。当然，forall/2，或setof/3 是您需要了解的内置函数，以便更熟练地使用 Prolog。