Пример ограничения канала ECLiPSe

Question

Пример ограничения канала ECLiPSe

Может ли кто-нибудь привести простой пример ограничений канала?

Канальные ограничения используются для объединения точек зрения проблемы ограничения. Руководство по ограниченному программированию дает хорошее объяснение того, как оно работает и почему оно может быть полезным:

Переменные поиска могут быть переменными одной из точек обзора, скажем, X1 (это обсуждается ниже). По мере продолжения поиска распространение ограничений C1 удаляет значения из доменов переменных в X1. Ограничения на каналирование могут затем позволять удалять значения из доменов переменных в X2. Распространение этих удалений значений с использованием ограничений второй модели, C2, может удалить дополнительные значения из этих переменных, и снова эти удаления могут быть переведены обратно в первую точку обзора посредством ограничений канализации. Конечным результатом может быть то, что в точке обзора V1 удаляется больше значений, чем только с помощью ограничений C1, что приводит к сокращению поиска.

Я не понимаю, как это реализовано. Каковы именно эти ограничения, как они выглядят в реальной проблеме? Простой пример был бы очень полезен.

8

prolog constraints constraint-programming clpfd eclipse-clp

Источник

user3296266 21 июн '16 в 14:48

3 ответа

Решение

Канальные ограничения используются, когда в модели аспекты проблемы представлены более чем одним способом. Затем им необходимо синхронизировать эти множественные представления, даже если они сами не моделируют аспект проблемы.

Как правило, при моделировании проблемы с ограничениями у вас есть несколько способов выбора переменных. Например, в задаче планирования вы можете выбрать

целочисленная переменная для каждого задания (указывающая, какой компьютер выполняет задание)
целочисленная переменная для каждой машины (указывающая, какую работу она выполняет)
матрица логических значений (указывающая, какое задание выполняется на каком компьютере)
или что-то более экзотическое

В достаточно простой задаче вы выбираете представление, которое облегчает формулировку ограничений задачи. Однако в реальных задачах со многими неоднородными ограничениями зачастую невозможно найти такое единственное наилучшее представление: некоторые ограничения лучше всего представлены одним типом переменной, другие - другим.

В таких случаях вы можете использовать несколько наборов переменных и формулировать каждое отдельное ограничение задачи для наиболее удобного набора переменных. Конечно, вы в конечном итоге получите несколько независимых подзадач, и их решение в отдельности не даст вам решения всей проблемы. Но, добавив канальные ограничения, наборы переменных могут быть синхронизированы, и, таким образом, подзадачи будут повторно связаны. Результатом является действительная модель для всей проблемы.

Как указывалось в цитате из справочника, в такой формулировке достаточно выполнить поиск только по одному из наборов переменных ("точек обзора"), поскольку значения других подразумеваются каналирующими ограничениями.

Некоторые распространенные примеры для ченнелинга между двумя представлениями:

Целочисленная переменная и массив логических значений: рассмотрим целочисленную переменную T с указанием временного интервала 1..N когда происходит событие, и массив логических значений Bs[N] такой, что Bs[T] = 1 если событие происходит во временном интервале T, В ЭКЛИПЕ:

    T #:: 1..N,
    dim(Bs, [N]), Bs #:: 0..1,

Канализация между двумя представлениями может быть установлена с помощью

    ( for(I,1,N), param(T,Bs) do Bs[I] #= (T#=I) )

которая будет распространять информацию в обоих направлениях между T а также Bs, Другим способом реализации этого ченнелинга является специальное ограничение bool_channeling/3.

Начальные / конечные целочисленные переменные и массив логических значений (расписание): у нас есть целочисленные переменные S,E с указанием времени начала и окончания действия. С другой стороны массив логических Bs[N] такой, что Bs[T] = 1 если деятельность происходит во время T, В ЭКЛИПЕ:

    [S,E] #:: 1..N,
    dim(Bs, [N]), Bs #:: 0..1,

Ченнелинг может быть достигнут через

    ( for(I,1,N), param(S,E,Bs) do Bs[I] #= (S#=<I and I#=<E) ).

Двойное представление целочисленных переменных Job/Machine: Здесь Js[J] = M означает, что работа J выполнен на машине M в то время как двойная формулировка Ms[M] = J означает, что машина M выполняет работу J

    dim(Js, [NJobs]), Js #:: 0..NMach,
    dim(Ms, [NMach]), Ms #:: 1..NJobs,

И ченнелинг достигается через

    ( multifor([J,M],1,[NJobs,NMach]), param(Js,Ms) do
        (Js[J] #= M) #= (Ms[M] #= J)
    ).

Переменная набора и массив логических значений: если вы используете решатель (такой как библиотека (ic_sets)), который может непосредственно обрабатывать переменные набора, они могут быть отражены в массив логических значений, указывающих на принадлежность элементов в наборе. Для этой цели библиотека предоставляет специальное ограничение members_booleans/2.

5

Источник

user2353967 26 июн '16 в 00:54

Вот простой пример, работает в SWI-Prolog, но также должен работать в ECLiPSe Prolog (в дальнейшем вы должны использовать (::)/2 вместо (in)/2):

Ограничение C1:

 ?- Y in 0..100.
 Y in 0..100.

Ограничение C2:

 ?- X in 0..100.
 X in 0..100.

Ограничение канала:

 ?- 2*X #= 3*Y+5.
 2*X#=3*Y+5.

Все вместе:

?- Y in 0..100, X in 0..100, 2*X #= 3*Y+5.
Y in 1..65,
2*X#=3*Y+5,
X in 4..100.

Таким образом, ограничение канала работает в обоих направлениях, оно уменьшает область C1, а также область C2.

В некоторых системах используются итеративные методы, в результате чего это ченнелинг может занимать довольно много времени, вот пример, который требует около 1 минуты для вычисления в SWI-Prolog:

?- time(([U,V] ins 0..1_000_000_000, 36_641*U-24 #= 394_479_375*V)).
% 9,883,559 inferences, 53.616 CPU in 53.721 seconds 
(100% CPU, 184341 Lips)
U in 346688814..741168189,
36641*U#=394479375*V+24,
V in 32202..68843.

С другой стороны, ECLiPSe Prolog делает это в одно мгновение:

[eclipse]: U::0..1000000000, V::0..1000000000, 
              36641*U-24 #= 394479375*V.
U = U{346688814 .. 741168189}
V = V{32202 .. 68843}
Delayed goals:
     -394479375 * V{32202 .. 68843} + 
     36641 * U{346688814 .. 741168189} #= 24
Yes (0.11s cpu)

до свидания

1

Источник

user502187 24 июн '16 в 22:10

Другие вопросы по тегам prolog constraints constraint-programming clpfd eclipse-clp

user1153801 15 июл '16 в 10:02 2016-07-15 10:02 · Accepted Answer · 2016-07-15 10:02

Как указано в " Эвристике двойных точек зрения для проблем удовлетворения двоичных ограничений" (П. А. Гилен):

Канальные ограничения двух разных моделей позволяют выразить взаимосвязь между двумя наборами переменных, по одной для каждой модели.

Это подразумевает, что назначения в одной из точек обзора могут быть преобразованы в назначения в другой и наоборот, а также, когда поиск начинается, исключенные значения из одной модели также могут быть исключены из другой.

Позвольте мне привести пример, который я реализовал некоторое время назад, когда писал решатель судоку.

Классическая точка зрения

Здесь мы интерпретируем проблему так же, как это сделал бы человек: используя целые числа от 1 до 9 и определение, что все строки, столбцы и блоки должны содержать каждое целое число ровно один раз.

Мы можем легко заявить об этом в ECLiPSe, используя что-то вроде:

% Domain
dim(Sudoku,[N,N]),
Sudoku[1..N,1..N] :: 1..N

% For X = rows, cols, blocks
alldifferent(X)

И этого еще достаточно, чтобы решить головоломку судоку.

Двоичная булева точка зрения

Тем не менее, можно выбрать представление целых чисел их двоичными логическими массивами (показано в ответе @jschimpf). В случае, если неясно, что это делает, рассмотрим небольшой пример ниже (это встроенная функциональность!):

? ic_global:bool_channeling(Digit, [0,0,0,1,0], 1).
    Digit = 4
    Yes (0.00s cpu)
? ic_global:bool_channeling(Digit, [A,B,C,D], 1), C = 1.
    Digit = 3
    A = 0
    B = 0
    C = 1
    D = 0
    Yes (0.00s cpu)

Если мы используем эту модель для представления судоку, каждое число будет заменено его двоичным логическим массивом, и соответствующие ограничения могут быть записаны. Будучи тривиальным для этого ответа, я не буду включать весь код для ограничений, но одного ограничения суммы все же достаточно, чтобы решить головоломку Судоку в ее двоичном логическом представлении.

Ченнелинг

Наличие этих двух точек зрения с соответствующими ограниченными моделями теперь дает возможность провести канал между ними и посмотреть, были ли сделаны какие-либо улучшения.

Поскольку обе модели по-прежнему являются платой NxN, различий в представлении не существует, и ченнелинг становится очень простым.

Позвольте мне сначала привести последний пример того, как будет выглядеть блок, заполненный целыми числами 1..9, в обеих наших моделях:

% Classic viewpoint
1 2 3
4 5 6
7 8 9

% Binary Boolean Viewpoint
[](1,0,0,0,0,0,0,0,0)  [](0,1,0,0,0,0,0,0,0)  [](0,0,1,0,0,0,0,0,0) 
[](0,0,0,1,0,0,0,0,0)  [](0,0,0,0,1,0,0,0,0)  [](0,0,0,0,0,1,0,0,0) 
[](0,0,0,0,0,0,1,0,0)  [](0,0,0,0,0,0,0,1,0)  [](0,0,0,0,0,0,0,0,1)

Теперь мы ясно видим связь между моделями и просто пишем код для направления наших переменных решения. Используя Sudoku и BinBools в качестве наших плат, код будет выглядеть примерно так:

( multifor([Row,Col],1,N), param(Sudoku,BinBools,N) 
do
  Value is Sudoku[Row,Col], 
  ValueBools is BinBools[Row,Col,1..N], 
  ic_global:bool_channeling(Value,ValueBools,1) 
).

На данный момент у нас есть канальная модель, в которой во время поиска, если значения отбрасываются в одной из моделей, ее влияние также будет иметь место в другой модели. Это, конечно, может привести к дальнейшему распространению общего ограничения.

аргументация

Чтобы объяснить полезность бинарной булевой модели для головоломки Судоку, мы должны сначала провести различие между некоторыми alldifferent/1 реализации ECLiPSe:

Что это означает на практике, можно показать следующим образом:

? [A, B, C] :: [0..1], ic:alldifferent([A, B, C]). 
  A = A{[0, 1]} 
  B = B{[0, 1]} 
  C = C{[0, 1]} 
  There are 3 delayed goals. 
  Yes (0.00s cpu) 

? [A, B, C] :: [0..1], ic_global:alldifferent([A, B, C]). 
  No (0.00s cpu)

Поскольку еще не было выполнено ни одного назначения, использующего Forward Checking (библиотека ic), недействительность запроса еще не обнаружена, тогда как версия Bounds Consistent немедленно это замечает. Такое поведение может привести к значительным различиям в распространении ограничений при поиске и обратном отслеживании в сильно ограниченных моделях.

В дополнение к этим двум библиотекам есть библиотека ic_global_gac, предназначенная для глобальных ограничений, для которых поддерживается обобщенная согласованность дуг (также называемая согласованность гипер-дуг или согласованность доменов). Это ограничение alldifferent/1 предоставляет даже больше возможностей сокращения, чем ограничение, ограниченное границами, но сохранение полной доменной согласованности имеет свою стоимость, и использование этой библиотеки в моделях с высокими ограничениями обычно приводит к потере производительности работы.

Из-за этого я обнаружил, что для головоломки Судоку было интересно попробовать поработать с последовательной (ic_global) реализацией реализации границ alldifferent, чтобы максимизировать производительность, а затем попытаться самостоятельно приблизиться к согласованности доменов, направив двоичную логическую модель.

Результаты эксперимента

Ниже приведены результаты возврата для головоломки Sudoku "Platinumblonde" (на которую ссылаются как на самую сложную и хаотичную головоломку Sudoku, которую нужно решить в The Chaos Within Sudoku, M. ErcseyRavasz и Z. Toroczkai), используя соответственно предварительную проверку, согласованность границ, согласованность доменов, автономная двоичная булева модель и, наконец, канальная модель:

      (ic)   (ic_global)  (ic_global_gac)  (bin_bools)  (channelled)
BT    6 582      43             29             143           30

Как мы видим, наша направленная модель (использующая согласованность границ (ic_global)) по-прежнему нуждается в одном возврате больше, чем согласованная реализация домена, но она определенно работает лучше, чем автономная согласованная версия границ.

Теперь, когда мы посмотрим на время выполнения (результаты - это результат вычисления среднего значения для нескольких выполнений, чтобы избежать крайностей), исключая реализацию прямой проверки, поскольку доказано, что она больше не интересна для решения головоломок Судоку:

          (ic_global)  (ic_global_gac)  (bin_bools)  (channelled)
Time(ms)     180ms          510ms           100ms        220ms

Глядя на эти результаты, я думаю, что мы можем успешно завершить эксперимент (эти результаты были подтверждены 20+ другими примерами головоломки Судоку):

Направление двоичной логической точки зрения в согласованную автономную реализацию с ограничениями приводит к несколько менее сильному поведению распространения ограничений, чем в автономной реализации с согласованной областью, но со временем выполнения от столь же длительного до заметно более быстрого.

РЕДАКТИРОВАТЬ: попытка уточнить

Представьте, что некоторая переменная домена, представляющая ячейку на доске Судоку, имеет оставшийся домен 4..9. Используя согласованность границ, гарантируется, что как для значений 4, так и для 9 могут быть найдены другие значения домена, которые удовлетворяют всем ограничениям и, таким образом, обеспечивают согласованность. Однако согласованность явно не гарантируется для других значений в домене (это и есть "согласованность домена").

Используя двоичную булеву модель, мы определяем следующие два ограничения суммы:

Сумма каждого двоичного логического массива всегда равна 1
Сумма каждого N-го элемента каждого массива в каждой строке / столбце / блоке всегда равна 1

Дополнительная сила ограничения обеспечивается вторым ограничением, которое, помимо ограничения строки, столбцов и блоков, также неявно говорит: "каждая ячейка может содержать каждую цифру только один раз". Это поведение не выражается активно, когда используется только ограничение согласования границ alldifferent/1!

Заключение

Ясно, что ченнелинг может быть очень полезным для улучшения автономной модели с ограничениями, однако, если прочность новой модели слабее, чем у текущей модели, очевидно, что никаких улучшений не будет. Также обратите внимание, что наличие более ограниченной модели не обязательно означает и общую лучшую производительность! Добавление большего количества ограничений фактически уменьшит количество возвратов, необходимых для решения проблемы, но также может увеличить время выполнения вашей программы, если потребуется выполнить больше проверок ограничений.