Prolog 时间重叠问题 [英] Prolog Time Overlap Woes
问题描述
假设我有这个知识库:
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))).
因此，经过大量努力，我设法编写了一些内容，使用以下代码打印在特定时段内有空的第一人:
So, after a lot of effort, I managed to write something that prints the first person who has availability during a specific slot with the following code:
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，即预期的结果.
This prints bob, the expected result.
这就是它变得复杂的地方(至少对我而言).假设我想找出知识库中每个人都有的所有时间段.以下代码演示了我最终想要如何调用它:
Here's where it gets complicated (at least for me). Let's say I want to find out all the time slots everyone in the Knowledge Base has in common. The following code demonstrates how I ultimately want to call this:
people([ann,bob,carla]).
meet :- ???
main :- (setof(Slot,meet(Slot),Slots); halt),
write(Slots),
nl,
halt.
:- initialization(main).
这里有一些模糊的伪代码，我认为它们可以实现我正在寻找的东西，但我没有足够的经验来让它工作.
Here's some vague pseudocode that I think might accomplish what I'm looking for, but I'm not experienced enough to get it working.
- 从第一人的空闲位置开始.
- 递归遍历人员列表的其余部分，找到重叠的时间.
- 可以使用类似于 meetone 的东西来验证插槽是否重叠；在此验证之后，可以使用两个时隙开始时间的最大值和两个结束时间的最小值来确定准确的重叠时段.
- 打印插槽的最终列表.
最终输出将显示 8:00 - 8:30 和 10:00 - 10:15 的时段.不胜感激.
The final output would show slots of 8:00 - 8:30 and 10:00 - 10:15. Any help in accomplishing this would be greatly appreciated.
推荐答案
Prolog 有一些语法特性，恕我直言，确实有助于编写易于理解的代码.那么这是你的问题，利用运算符来获得可读性:
Prolog has some syntactic features that, imho, really help writing understandable code. Then here is your question, taking advantage from operators to gain readability:
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.拥有这样的代码片段有助于编写更复杂的逻辑......
I attempted to introduce two utilities, kind of reusable code: contains/2 and timepoints/3. Having such snippets could help while writing more complex logic...
运行这段代码，我明白了
Running this code, I get
?- main.
bob
true.
现在来回答您的主要问题:
now coming to your main question:
假设我想找出知识库中每个人共有的所有时间段
Let's say I want to find out all the time slots everyone in the Knowledge Base has in common
我会开始写一个 common_timeslot/3，解释(计算)什么是预期的:
I would start writing a common_timeslot/3, explaining (computing) what's expected:
common_timeslot(S1, S2, Common) :-
timepoints(S1, B1, E1),
timepoints(S2, B2, E2),
% do you mean intersection by common ?
...
否则，只考虑身份
common_timeslot(S, S, S).
定义了这个，所有的共同点都可以用
Having defined this one, all commons can be found with
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.
编辑垫子评论，现在我发布整个程序
edit accounting for mat comment, now I post the entire program
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，正如您在评论中所解释的那样.
The main change is that timepoints/3 is now 'bidirectional'. Then I introduced common_timeslot/3 as you explained in your comment.
我想你会明白那些小的句法抽象有助于拥有一个干净的应用"逻辑.当然，forall/2，或者setof/3，是您需要了解的内置程序，以便更熟练地使用 Prolog.
I think you could appreciate that those small syntactic abstractions help to have a clean 'applicative' logic. Of course, forall/2, or setof/3, are builtins that you need to learn about to gain more proficiency in Prolog.
这篇关于Prolog 时间重叠问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
