Получение порядка в разрешении предикатов

Посмотрите на следующие цели (я использую swi-пролог с clpfd от Маркуса Триски):

result(Input,Result) :-
    Input #> 10,
    Result=decline.
result(Input,Result) :-
    Input in 0..20,
    Result=offer.

Возможный запрос выглядит так:

?- result(15,B).
B = decline ;
B = offer.

Я хочу добавить заказ или какой-то приоритет решения. Если "отклонение" является действительным ответом для Input=15то вторая цель больше не должна рассматриваться, так что только B=decline это решение, но не B=offer,

Я знаю, что я мог бы добавить !/0 но тогда наоборот не сработает. Дайте мне все возможные ответы для этого предиката.

Учитывая этот пример, Result=offer должно быть верно только для Input 0..10, потому что в противном случае более высокая цель предшествующего снижения должна выстрелить.

Думаю ли я слишком императивным, когда пытаюсь рассмотреть порядок в предикатах?

Источник

4 ответа

Решение

Здесь есть несколько проблем, давайте начнем с самых очевидных:

Проблемы моделирования

У вас есть отношение (result/2 может быть, не лучшее имя), и это отношение должно моделировать, когда decline и когда offer должно быть правдой. Прежде чем читать вашу программу, я предпочитаю спросить Пролога:

? - результат (X, снижение), результат (X, предложение).
Х в 11..20;
ложный.

Так что для значений от 11 до 20 ваше отношение неоднозначно. Если вы хотите принять решение, то сначала исправьте это отношение. На самом деле, я бы начал с

  • лучшее название для отношения, которое дает понять, что это отношение
  • нет обязательных слов (как Input или императивы)
  • более компактная формулировка, вам не нужно так много (=)/2 цели в вашей программе. Вместо этого вы можете написать это так: 
heigth_decision (I, отклонение):-
   Я #< 10.

Ответы и успех против решений в CLP

И тогда есть еще одна проблема, которая является более фундаментальной. Это на самом деле гораздо серьезнее, поскольку все SO-ответы, данные до сих пор, полностью игнорируют этот аспект. Речь идет о понятии ответов и успеха, а с другой стороны, о решении.

Когда вы задаете вопрос в Прологе, вы получаете ответ. Такой ответ может содержать решения, такие как ответ L = [_,_] который содержит бесконечно много решений. Или ответ может содержать ровно одно решение, например Decision = decline, Но есть гораздо больше между ними, если вы используете ограничения, такие как library(clpfd),

Теперь вы можете получить конечное число решений:

? - abs (X) # <3.
Х в -2,2.

Или бесконечно много

?- X #> Y.
Y#= 
Но вы можете получить также одно решение, которое не похоже на одно:
? - 2 ^ X #= 1.
2 ^ Х #= 1.

Итак, просто чтобы повторить это: у нас здесь есть только одно решение в целых числах, но для Пролога это слишком сложно. Мы получили ответ, который гласит: "Да, это все правда, при условии, что все эти мелкие шрифты верны".
Хуже того, иногда мы получаем ответы, которые не содержат никакого решения.
? - X ^ X # = 0.
X ^ X # = 0.

Если бы Пролог был достаточно умен, он бы ответил false, Но это не всегда может быть так умно, просто потому, что вы легко можете сформулировать неразрешимые проблемы. Такой ответ иногда называют несогласованностью. Немецкое понятие Scheinlösung (ложное решение, но с меньшим отрицательным значением) передает идею немного лучше.
Таким образом, ответ может содержать решения, но некоторые ответы не содержат решений вообще. По этой причине успех цели не может быть воспринят как существование решения! То есть все SO-ответы, предлагающие какой-либо коммит как (;)/2 - if-then-else, Once/1 или!/0, являются неверными, если они принимают успех как решение. Чтобы увидеть это, попробуйте их с:
? - X ^ X # = 0, результат (X, снижение).
X в 11..,
X^X#=0;
ложный.?- X^X#=0, результат (X, предложение).
Х в 0..20,
X^X#=0.

Так как же теперь вы можете быть уверены в чем-либо?
  • Вы можете рассчитывать на провал цели.
  • Ты можешь попробовать labeling/2, но это работает только на конечных доменах.
  • Ты можешь использовать call_residue_vars/2 а также copy_term/3 чтобы определить, есть ли ограничения "торчать"
  • К сожалению, вы не можете полностью полагаться на верхний уровень SWI, который скрывает ограничения, не связанные с переменными в ответе. Только SICStus отображает их правильно.
Источник

Часть, которая озадачивает меня, - это когда ты говоришь "обратный путь не сработает". Почему вы хотите пойти наоборот?

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

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

Источник

Предикатный заказ - это неотъемлемая часть программ Prolog. Это связано с тем, что поиск корректуры выполняется в строго определенном порядке с применением разрешения SLD.

Ваш предикат дает разумные результаты:

?- result(X,Y).
Y = decline,
X in 11..sup ;
Y = offer,
X in 0..20.

Вместо сокращения в результате /2, вы можете использовать один раз /1 при вызове, сохраняя правильное определение для общего использования.

?- once(result(X,Y)).
Y = decline,
X in 11..sup.
Источник

Здесь могут помочь некоторые идеи от конструктивного отрицания.

теория

Существует простой способ иметь логическое сокращение. Особенно для ограничений, поскольку ограничения, как правило, завершаются отрицанием. Поэтому, если у вас есть ограничение C, вы обычно можете найти ограничение C'со следующим свойством:

C' <=> ~C

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

p :- C, q.
p :- r

Просто сделайте следующее:

p :- C, q.
p :- C', r.

Если ваш решатель ограничений обеспечивает отрицание, например (#\)/1Вы могли бы даже определить оператор для этого:

:- op(1050,xfy,#?).
:- op(1100,xfy,#:).
(A #? B #: C) :- (A, B); (#\ A, C).

А затем напишите следующее:

p :- C #? q #: r.

Давайте применим эту стратегию к вашему примеру:

пример

Ваш код в настоящее время выглядит следующим образом:

result(Input, Result) :-
    Input #> 10,
    Result = decline.
result(Input, Result) :-
    Input in 0..20,
    Result = offer.

Затем сделайте следующее:

result(Input, Result) :-
    Input #> 10,
    Result = decline.
result(Input, Result) :-
    Input #=< 10, Input in 0..20,
    Result = offer.

Вот пример запуска:

?- result(15, X).
X = decline ;
false.

?- result(8, X).
X = offer.

А теперь с помощью (#?)/2 что, например, возможно в SWI-Prolog, поскольку библиотека CLP(FD) поддерживает реификацию. Предполагая, что мы обратились к библиотеке CLP(FD) и затем определили (#:)/2 как указано выше:

 result(Input, Result) :-
    Input #> 10 
    #? 
       Result = decline 
    #: 
       Input in 0..20,
       Result = offer.

Вот пример запуска:

?- result(15, X).
X = decline ;
false.

?- result(8, X).
X = offer.

отказ

Более поздний синтаксис (#?)/2 а также (#:)/2 вдохновлен Java-операторами if-then-else (?)/2 а также (:)/2, Более вдохновленный Прологом синтаксис невозможен, так как мы не можем переопределить или расширить определение (;)/2,

Для получения дополнительной информации о рификации см., Например, здесь раздел А.8.4 Реификация. Чего мы не делали, так это уточнили конъюнкцию и дизъюнкцию в нашем определении CLP(FD) if-then-else, так как тогда и тогда часть else может содержать другие цели, чем ограничения CLP(FD).

до свидания

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