CLP: ограничения на структурированные переменные?

Давайте предположим следующий гипотетический сценарий... сетка с 5x5 и скажем, 3 цифры. Мы хотим определить ограничение на позиции. В CLP мы обычно определяем ограничения целыми числами, так что это один из способов сделать это:

  ... Fig1X #\= 2, Fig1Y #\= 3, ....

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

 .... Fig1 #\= (2,4) ...

Сценарий только для иллюстрации.

Меня интересует, в основном, как вы обрабатываете структурированные переменные, есть ли стандартные практики.

Источник

2 ответа

Решение

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

  1. geost/N Эти ограничения предоставляют выделенный мини-язык для рассуждений о многомерных объектах. Это очень мощный и гибкий подход, который доступен в SICStus Prolog, а также в некоторых других системах ограничений.
  2. ограниченные ограничения. Например, вы можете заявить X #= 2 #==> Y #\= 4 выразить это Y не должно быть 4, если X равен 2. Таким образом, (X,Y) автоматически отличается от (2,4),
  3. экстенсиональные ограничения (доступны как table/2, fd_relation/2 и т. д. во многих системах Пролога) позволяют вам явно перечислить допустимый набор кортежей или его дополнение.
  4. переделывать вашу задачу как выбор между допустимыми позициями с помощью булевых индикаторов. См. Упаковочные квадраты для примера такого подхода.

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

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

Источник

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

Иногда эти кортежи лучше всего представлять в виде списков, потому что тогда вы можете напрямую применять глобальные ограничения, которые принимают списки в качестве аргументов. Например, чтобы ограничить точку [X,Y] чтобы не быть по диагонали, можно написать

alldifferent([X,Y])

или используйте ограничение таблицы, чтобы ограничить его заданным набором координат:

table([[X,Y]], [[1,2],[2,4],[3,1],[4,3]])

В других случаях лучше использовать структуры с описательными функторами, такими как point(X,Y) или же rect(X1,Y1,X2,Y2), а затем напишите ваши соответствующие обертки ограничения, такие как

points_differ(point(X,Y), point(V,W)) :-
    X#\=V or Y#\=W.

или же

rect_contains_point(rect(I,J,K,L), point(PI,PJ)) :-
    I #=< PI, PI #=< K,
    J #=< PJ, PJ #=< L.

(Последний пример взят из http://eclipseclp.org/examples/shikaku.ecl.txt)

Источник
Другие вопросы по тегам