练习

Question

我必须成对与6个项目学生见面，我有3个可以做到这一点，但是有一些约束。

LLET的呼叫学生1 et equest 1 eq and插槽插槽等。在较低的插槽之后发生了一个较高的插槽。

约束是：

Student1必须在插槽中见面1.

1. student2和Student3必须在同一插槽中见面。
student1和Student4不能在同一插槽中相遇。
2. student6无法在slot1或slot3中相遇。
3. 我应该准确见到每个学生一次。
我已经写了以下程序来解决此计划难题：

student(student1).
student(student2).
student(student3).
student(student4).
student(student5).
student(student6).


slot(slot1).
slot(slot2).
slot(slot3).


constraint1(Slot1, _Slot2, _Slot3) :-
    member(student1-_, Slot1).

constraint2(Slot1, Slot2, Slot3) :-
    ( member(student2-_, Slot1), member(student3-_, Slot1) );
    ( member(student2-_, Slot2), member(student3-_, Slot2) );
    ( member(student2-_, Slot3), member(student3-_, Slot3) ).

constraint3(Slot1, Slot2, Slot3) :-
    \+ ( member(student1-_, Slot1), member(student4-_, Slot1) ),
    \+ ( member(student1-_, Slot2), member(student4-_, Slot2) ),
    \+ ( member(student1-_, Slot3), member(student4-_, Slot3) ).

constraint4(Slot1, _, Slot3) :-
    \+ member(student6-_, Slot1),
    \+ member(student6-_, Slot3).


meetings_one_two_three(Slot1, Slot2, Slot3) :-

    % Generate all possible assignments of students to slots.
    findall( (Slot1, Slot2, Slot3), (

        % Slot 1
        select_two_students(S1_1, S1_2, _Remaining1),
        Slot1 = [S1_1-S1_2, S1_2-S1_1], % Assign to slot 1.
    
        % Slot 2
        select_two_students(S2_1, S2_2, _Remaining2),
        Slot2 = [S2_1-S2_2, S2_2-S2_1], % Assign to slot 2.

        % Slot 3
        select_two_students(S3_1, S3_2, _Remaining3),
        Slot3 = [S3_1-S3_2, S3_2-S3_1], % Assign to slot 3.

        all_different([S1_1, S1_2, S2_1, S2_2, S3_1, S3_2]), % All students must be different.

        constraint1(Slot1, Slot2, Slot3),
        constraint2(Slot1, Slot2, Slot3),
        constraint3(Slot1, Slot2, Slot3),
        constraint4(Slot1, Slot2, Slot3)

    ), Solutions),

    member( (Slot1, Slot2, Slot3), Solutions). % Select one solution.


select_two_students(S1, S2, Remaining) :-
    student(S1),
    student(S2),
    S1 @< S2,    % Ensure we do not generate (A, B) and (B, A) which is essential for efficiency. This condition reduces the search space.
    findall(Other, (student(Other), Other \= S1, Other \= S2), Remaining).


all_different([]).
all_different([H|T]) :-
    \+ member(H,T),
    all_different(T).

当我在序言提示下咨询并查询知识库并输入以下内容时，我会收到这些结果：

?- consult(scheduling).
true.

?- meetings_one_two_three(Slot1, Slot2, Slot3).
Slot1 = [student1-student5, student5-student1],
Slot2 = [student4-student6, student6-student4],
Slot3 = [student2-student3, student3-student2].

这是正确的，但是

S1 @< S2

应该阻止同时产生

student1-student5

和

student5-student1

的产生。 然后，意识到问题必须是以下三行：

Slot1 = [S1_1-S1_2, S1_2-S1_1], % Assign to slot 1.
Slot2 = [S2_1-S2_2, S2_2-S2_1], % Assign to slot 2.
Slot3 = [S3_1-S3_2, S3_2-S3_1], % Assign to slot 3.

，我将它们修改为以下内容：

Slot1 = [S1_1-S1_2], % Assign to slot 1.
Slot2 = [S2_1-S2_2], % Assign to slot 2.
Slot3 = [S3_1-S3_2], % Assign to slot 3.

我相信这将解决这个问题，但不幸的是我得到了

false.

我想念什么？有人可以帮助我了解我在做错了什么，以及如何通过最小的变化来解决它？

member

太简单了，因此缓慢/不理 - 想要

select

或实际上是一个更灵活的自定义变体：

：

Answer 1

select

swi-prolog：

sched_slots(Slots) :-
    % Create ordered list - and do not scramble the order
    numlist(1, 6, Vars),
    % student1 must meet in slot1
    Slots = [s(1, S1Pos2), _, s(S3Pos1, S3Pos2)|_],
    Not6 = [S1Pos2, S3Pos1, S3Pos2],
    assign_slots(Vars, Slots),
    % student2 and student3 must meet in the same slot
    memberchk(s(2, 3), Slots),
    % student1 and student4 cannot meet in the same slot
    \+ memberchk(s(1, 4), Slots),
    % student6 cannot meet in slot1 or slot3
    \+ memberchk(6, Not6).

assign_slots([], []).
assign_slots([H|T], [s(Lower, Upper)|Slots]) :-
    grab_2([H|T], Lower, Upper, Rem),
    assign_slots(Rem, Slots).

grab_2(Vars, Lower, Upper, Rem) :-
    select_forward_remainder_prev_tail(Lower, Vars, Forw, _, Rem, PrevTail),
    % Preventing slow append by unifying PrevTail
    select_forward_remainder_prev_tail(Upper, Forw, _, PrevTail, _, _).

% Based on select/3
select_forward_remainder_prev_tail(E, [H|T], F, R, P, PT) :-
    select_forward_remainder_prev_tail_(T, H, E, F, R, P, PT).

select_forward_remainder_prev_tail_(T, H, H, T, T, PT, PT).
select_forward_remainder_prev_tail_([H|T], A, E, F, [A|R], [A|P], PT) :-
    select_forward_remainder_prev_tail_(T, H, E, F, R, P, PT).