Что может привести к тому, что Prolog преуспеет в совпадении, но потерпит неудачу, когда его попросят пометить выходные данные?

Question

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

Когда я запускаю функцию решения, Пролог плюет назад: да и список переменных, все ограничены в диапазоне 0..1 (логические, как я их ограничил). Проблема в том, что когда я пытаюсь добавить предложение fd_labeling (Solution), Пролог о лицах и выплевывает: нет.

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

Answer 1

Очевидно, вы не "правильно" сопоставили проблему с FD, поскольку вы получаете "нет" при попытке пометить переменные.

То, что вы делаете в Constraint Logic Programming, - это настройка модели ограничений, в которой у вас есть переменные с доменом (в вашем случае логические значения с доменом [0,1]) и ряд ограничений между этими переменными. Каждое ограничение имеет правило распространения, которое пытается достичь согласованности для доменов переменных, на которых размещено ограничение. Несоответствующие значения удаляются из доменов. Существует несколько типов согласованности, но у них есть одна общая черта: ограничения, как правило, сами по себе не дают полного решения или даже не сообщают, существует ли решение для модели ограничений.

В качестве примера, скажем, у вас есть две переменные X и Y, обе с доменами [1..10] и ограничением X

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

Поскольку каждое ограничение нацелено только на согласованность доменов переменных, в которых оно размещено, возможно, что на этапе распространения не будет обнаружена невозможность, возникающая из комбинации ограничений. Например, три переменные X, Y, Z с областями [1..2], и ограничения попарного неравенства. Похоже, это произошло с вашей моделью ограничения.

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

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

Answer 2

(@ twinterer уже дал объяснение, мой ответ пытается принять его под другим углом)

Когда вы вводите запрос в Пролог, вы получаете ответ .Часто ответ содержит решение , иногда оно содержит несколько решений, а иногда вообще не содержит решения.Довольно часто эти два понятия перепутаны.Давайте рассмотрим примеры с GNU Prolog:

| ?- length(Vs,3), fd_domain_bool(Vs).                                       

Vs = [_#0(0..1),_#19(0..1),_#38(0..1)]

yes

Здесь у нас есть ответ, содержащий 8 решений.То есть:

| ?- length(Vs,3), fd_domain_bool(Vs), fd_labeling(Vs).

Vs = [0,0,0] ? ;

Vs = [0,0,1] ? ;

...

Vs = [1,1,1]

yes

А теперь еще один запрос.Вот пример, на который ссылается @twinterer.

| ?- length(Vs,3), fd_domain_bool(Vs), fd_all_different(Vs).

Vs = [_#0(0..1),_#19(0..1),_#38(0..1)]

yes

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

| ?- length(Vs,3), fd_domain_bool(Vs), fd_all_different(Vs), fd_labeling(Vs).

no

В идеале, в таком случае, верхний уровень не скажет «да», но «возможно».Фактически, CLP (R), одна из самых первых систем ограничений, сделала это.

Другой способ сделать это немного менее загадочным - показать действительные ограничения.SWI делает это:

?- length(Vs,3), Vs ins 0..1, all_different(Vs).
Vs = [_G565,_G568,_G571],
_G565 in 0..1,
all_different([_G565,_G568,_G571]),
_G568 in 0..1,
_G571 in 0..1.

?- length(Vs,3), Vs ins 0..1, all_different(Vs), labeling([], Vs).
false.

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

И еще один способ решить эту проблему - этополучить реализацию all_different/1 с большей согласованностью.Но это работает только в определенных случаях.

?- length(Vs,3), Vs ins 0..1, all_distinct(Vs).
false.

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

• Поддержание согласованности может быть очень дорогим.Часто лучше делегировать такие решения на маркировку.На самом деле, простой all_different/1 часто быстрее, чем all_distinct/1.

• Более эффективные алгоритмы согласованности часто очень сложны.

• ВВ общем случае поддержание глобальной согласованности является неразрешимой проблемой.