2015-07-03 7 views
4

Это проблема: 16 детей должны сидеть в 4 x 4 стульях. У детей 8 девочек (число 1,8) и 8 мальчиков (с номером 9,16). 1,3,5,8 думаю, что мальчики yucky 9,10,11,14 считают, что девочки являются грубыми эти пары являются врагами: [[1,2], [4,6], [4,7], [4, 9], [9,11], [12, 14], [14,16]]Исключая список tuples_in в прологе

предикат, чтобы найти двух детей не враги определяется как:

not_enemy(A, B) :- 
    NotA #\= A #\/ NotB #\= B, 
    tuples_in([[NotA, NotB]], 
       [[1,2], [4,6], [4,7], [4, 9],[9,11], [12, 14], [14,16]]). 

выше код был найден here

но когда я запрашиваю? - not_enemy (1,2), вывод является истинным.

Я должен использовать этот длинный код вместо:

not_enemy(A, B) :- 
      A #=1 #==> B #\= 2, 
      A #=4 #==> B #\= 6, 
      A #=4 #==> B #\= 7, 
      A #=4 #==> B #\= 9, 
      A #=9 #==> B #\= 11, 
      A #=12 #==> B #\= 14, 
      A #=14 #==> B #\= 16. 

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

+1

Пример неправильный, и смешение reifications с помощью 'tuples_in/2', безусловно, не является хорошим способом выразить заданные ограничения с помощью CLP (FD). Ваш код - один правильный способ сделать это (+1!). Другой способ - применить метод @repeat: вы можете построить дополнение к отношению и использовать 'tuples_in/2', чтобы ограничить пары * совместимыми * элементами. Еще один способ - свести на нет отдельные ограничения 'tuples_in/2'. Будьте осторожны, но не случайно отрицайте ограничение 'tuples_in/2', которое включает в себя более одной пары, поскольку это не будет логически эквивалентно другим способам. – mat

ответ

5

Я бы уточнить код, просто чтобы сделать это родовое

not_enemy(A, B) :- 
    maplist(not_enemy(A,B), [[1,2], [4,6], [4,7], [4,9], [9,11], [12,14], [14,16]]). 
not_enemy(A,B,[X,Y]) :- 
    X #= A #==> Y #\= B. 

Я не могу найти подходящий способ использовать tuples_in, чтобы решить эту проблему.

3

Неправильное использование tuples_in/2.

Придумайте tuples_in как способ определения «таблицы совместимости»: Тогда это должно быть очевидно, что комбинация с (#\=)/2 не может работать для выражения «несовместимость таблиц».

Почему? Потому что --- с таблицей несовместимости --- мы не хотим исключать любой несовместимый кортеж, но все из них в то же время.

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

+0

Как? Таблица совместимости? – false

+0

Спасибо, я понял концепцию концептуально, я попробую ее пролог. –

3

Я нашел еще один ответ, вместо того, чтобы использовать эту

not_enemy(A, B) :- 
    NotA #\= A #\/ NotB #\= B, 
    tuples_in([[NotA, NotB]], 
       [[1,2], [4,6], [4,7], [4, 9],[9,11], [12, 14], [14,16]]). 

Просто отрицать tuples_in с # \

not_enemy(A, B) :- 
    #\ tuples_in([[A,B]], 
       [[1,2], [4,6], [4,7], [4, 9],[9,11], [12, 14], [14,16]]). 
+1

Это работает? Замечательно! Я думал, что \ # для надежных ограничений, и tuples_in не попадает в эту категорию. Поэтому я не пробовал ... – CapelliC

+3

Я проверил документы, и если после дальнейшего расследования ваш ответ окажется правильным, я напишу отчет об ошибке на clpfd docs – CapelliC

+0

Да, это действительно сработало. \ # отменяет все, что следует (в clpfd). –

1

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

Во-первых, рассмотрим явно неправильный ответ not_enemy/2:

?- not_enemy(1, 2). 
true. 

Однако, есть больше к ней, и вы видите, что после того, как вы используете:

?- set_prolog_flag(toplevel_residue_vars, true). 
true. 

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

?- not_enemy(1, 2). 
% with pending residual goals 
_G454 in 0..1, 
_G454#\/_G460#<==>1, 
etc. 

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

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

Флаг toplevel_residue_vars работает, неявно обертывая запрос в важный предикат с именем call_residue_vars/2. Это доступно в SICStus и SWI, чтобы показать все остаточные ограничения. Используйте его, чтобы убедиться, что вы случайно не создаете неудовлетворительные ограничения где-то в своей формулировке.

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