序言怎么能花几分钟时间来检查一堆可能的组合中的答案呢？

Question

以下示例程序在匹配特定条件时生成计划。

条件：

每班分配一名员工
任何员工都不应连续工作
不分配员工个人假期

该程序提供了有效的解决方案，但大约需要 4 分钟，尽管应该只有 128 种可能的组合（组合 7 个轮班的 2 名员工）。该程序是在单核虚拟机中使用 gprolog 实现执行的。

这怎么可能？发生了什么事？

% which shifts have to be assigned to employees
shift(1, monday).   
shift(2, tuesday).
shift(3, wednesday).
shift(4, thursday).
shift(5, friday).
shift(6, saturday).
shift(7, sunday).

% available employees
employee(xerxes).
employee(yasmin).

% holidays specified in advance
unavailable(xerxes, shift(1, monday)).


get_all_employees(Employees) :-
    findall(employee(E), employee(E), Employees).

get_all_shifts(Shifts) :-
    findall(shift(D, N), shift(D, N), Shifts).

get_random_assignment(A) :-
    get_all_employees(Es), member(E, Es), 
    get_all_shifts(Ss), member(S, Ss),
    findall(assign(E,S), (E,S), A).

init_schedule(Schedule) :-
    length(Ss, N),
    get_all_shifts(Ss),
    length(Schedule, N),
    get_init_schedule_(Schedule).

get_init_schedule_([]).
get_init_schedule_([H|Schedule]) :-
    get_random_assignment(A),
    member(H, A),
    get_init_schedule_(Schedule).

get_schedule(Schedule) :-
    init_schedule(Schedule),
    one_employee_per_shift(Schedule),
    no_consecutive_shifts(Schedule),
    no_shift_on_personal_holiday(Schedule).

dif_assignment(assign(employee(_), shift(D, N)), assign(employee(_), shift(D2, N2))) :-
    D \== D2,
    N \== N2.

alldiff([]).
alldiff([E|Es]) :-
    maplist(dif_assignment(E), Es),
    alldiff(Es).

%
% 1. condition
%
one_employee_per_shift(Schedule) :-
    alldiff(Schedule).
%
% 2. Condition
%
no_consecutive_shift_(assign(employee(E), shift(D, _)), assign(employee(E2), shift(D2, _))) :-
    D_TMP is D + 1, 
    (D2 =:= D_TMP -> E \== E2 ; true).

no_consecutive_shifts([]).
no_consecutive_shifts([A|As]) :- 
    maplist(no_consecutive_shift_(A), As),
    no_consecutive_shifts(As).

%
% 3. Condition
%
no_shift_on_personal_holiday([]).
no_shift_on_personal_holiday([assign(employee(E), shift(D, N))|Schedule]) :-
    (unavailable(E2, shift(D, N)) -> E \== E2 ; true),
    no_shift_on_personal_holiday(Schedule).

Answer 1

takes about 4 minutes although there should be only 128 possible combinations (combine 2 employees on 7 shifts)

的确，这应该是搜索 space，但您进行了更多探索。考虑谓词的前两个答案：

?- get_schedule(S).
S = [assign(employee(xerxes), shift(2, tuesday)), assign(employee(xerxes), shift(4, thursday)), assign(employee(xerxes), shift(6, saturday)), assign(employee(yasmin), shift(1, monday)), assign(employee(yasmin), shift(3, wednesday)), assign(employee(yasmin), shift(5, friday)), assign(employee(yasmin), shift(7, sunday))] ;
S = [assign(employee(xerxes), shift(2, tuesday)), assign(employee(xerxes), shift(4, thursday)), assign(employee(xerxes), shift(6, saturday)), assign(employee(yasmin), shift(1, monday)), assign(employee(yasmin), shift(3, wednesday)), assign(employee(yasmin), shift(7, sunday)), assign(employee(yasmin), shift(5, friday))] .

这些是相同的时间表（即相同的人员分配到班次），元素只是以不同的方式排列。您不是在探索 128 个时间表的解决方案 space，而是在探索类似于 128 个七元素列表的所有排列的集合。太过分了

即使速度很快，给出所有这些排序不直观的冗余答案也不是很好。因此，解决方案是通过仅尝试 "properly sorted" 人类期望的方式来打破这种对称性。

您的 get_all_shifts/1 已经为我们提供了预期的转变：

?- get_all_shifts(Shifts).
Shifts = [shift(1, monday), shift(2, tuesday), shift(3, wednesday), shift(4, thursday), shift(5, friday), shift(6, saturday), shift(7, sunday)].

我们只需要将 init_schedule/1 更改为仅生成以这种方式安排班次的时间表。换句话说，我们只需要将员工与给定的这些班次配对：

init_schedule(Schedule) :-
    get_all_shifts(Shifts),
    shifts_schedule(Shifts, Schedule).

shifts_schedule([], []).
shifts_schedule([Shift | Shifts], [Assignment | Assignments]) :-
    employee(Employee),
    Assignment = assign(employee(Employee), Shift),
    shifts_schedule(Shifts, Assignments).

现在真的只有128个解：

?- time(findall(S, init_schedule(S), AllSchedules)), length(AllSchedules, N).
% 544 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 3239908 Lips)
AllSchedules = [[assign(employee(xerxes), shift(1, monday)), assign(employee(xerxes), shift(2, tuesday)), assign(employee(xerxes), shift(3, wednesday)), assign(employee(xerxes), shift(4, thursday)), assign(employee(xerxes), shift(5, friday)), assign(employee(xerxes), shift(6, saturday)), assign(employee(...), shift(..., ...))], [assign(employee(xerxes), shift(1, monday)), assign(employee(xerxes), shift(2, tuesday)), assign(employee(xerxes), shift(3, wednesday)), assign(employee(xerxes), shift(4, thursday)), assign(employee(xerxes), shift(5, friday)), assign(employee(...), shift(..., ...)), assign(..., ...)], [assign(employee(xerxes), shift(1, monday)), assign(employee(xerxes), shift(2, tuesday)), assign(employee(xerxes), shift(3, wednesday)), assign(employee(xerxes), shift(4, thursday)), assign(employee(...), shift(..., ...)), assign(..., ...)|...], [assign(employee(xerxes), shift(1, monday)), assign(employee(xerxes), shift(2, tuesday)), assign(employee(xerxes), shift(3, wednesday)), assign(employee(...), shift(..., ...)), assign(..., ...)|...], [assign(employee(xerxes), shift(1, monday)), assign(employee(xerxes), shift(2, tuesday)), assign(employee(...), shift(..., ...)), assign(..., ...)|...], [assign(employee(xerxes), shift(1, monday)), assign(employee(...), shift(..., ...)), assign(..., ...)|...], [assign(employee(...), shift(..., ...)), assign(..., ...)|...], [assign(..., ...)|...], [...|...]|...],
N = 128.

其余的按预期工作，非常快速地生成一个解决方案：

?- time(get_schedule(S)).
% 8,664 inferences, 0.003 CPU in 0.002 seconds (108% CPU, 3426483 Lips)
S = [assign(employee(yasmin), shift(1, monday)), assign(employee(xerxes), shift(2, tuesday)), assign(employee(yasmin), shift(3, wednesday)), assign(employee(xerxes), shift(4, thursday)), assign(employee(yasmin), shift(5, friday)), assign(employee(xerxes), shift(6, saturday)), assign(employee(yasmin), shift(7, sunday))] ;
% 3,610 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 4158272 Lips)
false.

序言怎么能花几分钟时间来检查一堆可能的组合中的答案呢？

How can prolog take minutes to check for answers within a bunch of possible combinations only?

performance

prolog

combinatorics