Пролог: foreach или forall для решения ограничений?

Я пытаюсь планировать проект с помощью пролога SWI и CLP. Мне удалось поддерживать последовательные зависимости, но я изо всех сил пытаюсь избежать двойного бронирования людей.

У меня есть список Schedule, содержащий такие элементы, как [taskname, starttime], где starttime — это свободная переменная для решателя ограничений. Они уже ограничены последовательными зависимостями.

Я пытаюсь написать такой цикл, чтобы исключить двойное бронирование:

  forall /* or maybe foreach*/ (isa(P,person), (
    % Filter scheduled tasks on that person...
    include(\[T,S]^(assigned(T,P)), Schedule, HisSchedule),
    % Present what serialized expects..
    maplist(\[T,S]^S^true, HisSchedule, Sts),
    % duration is just user-defined data... 
    maplist(\[T,S]^D^(duration(T,D)), HisSchedule, Dus),
    % Hit it...
    serialized(Sts, Dus)
  )),

С foreach это всегда терпит неудачу, а с forall всегда удается, ничего не ограничивая.

Расписание является глобальным для этого цикла, и цель состоит в том, чтобы ограничить его элементы времени начала с помощью сериализации. OTOH, HisSchedule, Sts и Dus зависят от конкретного человека. Поэтому я думаю, что мне нужно foreach, чтобы сделать Schedule счастливым, но forall, чтобы сделать HisSchedule и т. д. счастливыми. В этом проблема? И если да, то как мне это исправить?


lambda constraint-programming prolog resource-scheduling clpfd
person Adrian May    schedule 15.11.2014    source источник
comment
Обратите внимание, что стандартное определение предиката forall/2: forall(Generator, Test) :- \+ (Generate, \+ Test). Использование отрицания (как отказа), вероятно, является причиной того, что ваш запрос завершается успешно без каких-либо ограничений.   -  person Paulo Moura    schedule 15.11.2014

Ответы (2)


arrow_upward
8
arrow_downward

Встроенная функция forall/2 предлагается некоторыми системами Prolog, она в значительной степени опирается на немонотонные конструкции и никогда не предназначалась для взаимодействия с ограничениями. То же самое верно и для foreach/2, который пытается быть немного умнее.

Ответы, решения, ограничения

Итак, в чем здесь большая, фундаментальная проблема? Большая часть Пролога приобрела свою нынешнюю форму, когда ограничения не были широко известны. Таким образом, во многих конструкциях успех цели рассматривается как «да» как истина в последней инстанции. Но с ограничениями все немного иначе. Успешная цель дает ответ, который теперь может вообще не содержать решения! По этой причине успех уже не тот, что был раньше. Вот пример использования SICStus:

| ?- asserta(clpfd:full_answer).
yes
| ?- X mod 2 #= 1.
clpfd:(X mod 2#=1),
X in inf..sup ? 
yes
| ?- X mod 2 #= 1, X mod 2 #= 0.
clpfd:(X mod 2#=0),
clpfd:(X mod 2#=1),
X in inf..sup ? ;
no
| ?- X mod 2 #= 1, X mod 2 #= 0, X in 0..9.
no

Ответы теперь могут вообще не содержать решения, другими словами, они могут быть ложными.

В вашем примере include/3 очень проблематично, как и forall/2. А еще setof/3 сходит с ума от ограничений:

| ?- setof(t, (I in 1..3 ; I in 3..5 ), _). % SICStus
yes

?- setof(t, (I in 1..3 ; I in 3..5 ),_).  % SWI
I = 3.

Если вообще, правильный ответ будет I in 1..5.

Чтобы решить эту проблему, сначала преобразуйте реляционные данные в списки:

   ...,
   setof(P, isa(P, person), Ps),
   maplist(perperson(P,Global),Ps),
   ...
person false    schedule 15.11.2014
comment
Спасибо за это. Просто из интереса, знаете ли вы какой-нибудь хороший материал о том, как планировать ресурсы с помощью CLP? Я боюсь того момента, когда я рассматриваю возможность разделения задач, например. праздники или другие высокоприоритетные задачи и представляют время, потерянное, когда работник меняет тему. В этот момент больше нет простого начала, продолжительности и конца. - person Adrian May; 16.11.2014
comment
@AdrianMay: Может быть, начать с этого - person false; 16.11.2014

arrow_upward
2
arrow_downward

Я исправил сам так:

  findall(Per, isa(Per,person), People),
  maplist(nodoublebookings(Schedule),People),

nodoublebookings(Schedule, Per):-
  include(\[T,S]^(assigned(T,Per)), Schedule, HisSchedule),
  maplist(\[T,S]^S^true, HisSchedule, Sts),
  maplist(\[T,S]^D^(duration(T,D)), HisSchedule, Dus),
  serialized(Sts, Dus).

Почему-то не получилось написать nodoublebookings как лямбду.

person Adrian May    schedule 16.11.2014
comment
Использование findall/3 вместо setof/3 означает, что случайные изменения в последовательности решений могут изменить способ решения задачи. - person false; 16.11.2014
comment
..., maplist(Schedule+\Per^( include ... ), People), ... по умолчанию переменные являются локальными для ``, вам нужно объявить те, которые не являются. - person false; 16.11.2014