Как использовать предикат члена для указания ограничений в прологе

Question

Я пытаюсь написать программу Prolog, которая выполняет следующие действия: У меня есть некоторые отношения, определенные в списке отношений. (Например: [f1, s1] означает, что f1 требуется s1) В зависимости от того, какие функции (f1, f2, f3) выбраны в списке TargetFeat, я хотел бы создать список результатов с использованием программирования ограничений. Вот пример кода:

Relations =[[f1, s1], [f2, s2], [f3, s3], [f3, s4]], 
TargetFeat = [f3, f1], 
Result = [], 
member(f3,TargetFeat) #= member(s3,Result), %One of the constraints 
labeling(Result). 

Это не работает, потому что # = работает только с арифметическими выражениями, как операнды. Каковы альтернативы для достижения чего-то подобного?

Answer 1

Не решение, а некоторые наблюдения, которые не соответствовали бы комментарию.

Не используйте списки для представления отношений. Например, вместо [f1, s1] напишите requires(f1, s1). Если эти требования являются фиксированными, тогда определите requires/2 как предикат. Если вам нужно идентифицировать или перечислять функции, рассмотрите предикат feature/1. Например:

feature(f1). 
feature(f2). 
... 

То же самое для s1, s2 ... Е.Г.

support(s1). 
support(s2). 
... 

Answer 2

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

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

Перевод сущностей в соответствующие целые числа очень прямолинейный, и это одна из причин, по которым ограничения CLP (FD) также достаточны для моделирования задач над доменами, которые на самом деле не содержат целых чисел, но могут быть сопоставлены целым числам. Итак, давайте предположим, что вы не рассуждаете об особенностях f1, f2 и f3, но около целых0, 1 и 2, или любой другой набор чисел, который подходит вам.

Вы можете прямо перевести свои требования в этот новый домен. Например, вместо:

[f1,s1] означает: f1 потребности s1

мы можем сказать, например:

0 -> 3 означает: 0 необходим 3

И это приносит нам alr очень близки к ограничениям CLP (FD), которые позволяют моделировать всю проблему. Нам нужно только сделать еще один умственный скачок, чтобы получить представление, которое позволяет нам моделировать все требования.Вместо бетонных целых чисел, мы теперь используем переменные CLP (FD), чтобы указать, должно ли быть выполнено конкретное требование для получения желаемых функций. Мы будем использовать переменные R1, R2, R3, ... для обозначения того, какие требования необходимы, используя либо 0 (не обязательно), либо 1 (необходимо) для каждого из возможных требований.

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

1. список Fs из особенности
2. Перечень Ds из зависимостей между функциями и требованиями
3. a) Rs от требований

Мы уже рассмотрели, как представлять все эти права: (1) представляет собой список целых чисел, которые представляют функции, которые мы хотим получить. (2) представляет собой список из F -> R пар, который означает «свойство   F нуждается в требованиях» »» »» », и (3) представляет собой список булевых переменных, которые указывают, необходимо ли в конечном итоге каждое требование.

Теперь попробуем связать все эти права друг с другом.

Первые вещи первое: Если нет возможности не требуется, все тривиально:

features_dependencies_requirements([], _, _). 

Но что если функция на самом деле желательно? Ну, это просто: Нам нужно только учитывать зависимости от этой функции:

features_dependencies_requirements([F|Fs], Ds, Rs) :- 
    member(F->R, Ds), 

так что мы имеем в R требование признака F. Теперь нам нужно найти подходящую переменную в   Rs, что означает требование   R. Но как найти правильную переменную? В конце концов, переменная Пролога «не имеет галстука-бабочки», или — иностранцам — недостает знак, которым мы могли бы отличить его от других. Таким образом, на данный момент нам было бы удобно находить удобство выбора переменной из   Rs с указанием ее требования. Предположим, что мы представляем Rs в виде списка пар формы I=R, где I - это целое число, определяющее требование, а R - это булевский индикатор, который обозначает, требуется ли это требование. С учетом этого представления мы можем полностью сформулировать вышеизложенное положение следующим образом:

features_dependencies_requirements([F|Fs], Ds, Rs) :- 
    member(F->I, Ds), 
    member(I=1, Rs), 
    features_dependencies_requirements(Fs, Ds, Rs). 

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

На данный момент внимательный читатель увидит, что ограничений CLP (FD) вообще фактически были использованы в коде выше, и на самом деле перевод функций в целые числа был совершенно ненужным. Мы можем также использовать атомы для обозначения функций и требований, используя точный код , показанный выше.

Пример запроса и ответа:

 
?- features_dependencies_requirements([f3,f1], 
             [f1->s1,f2->s2,f3->s3,f3->s4], 
             [s1=S1,s2=S2,s3=S3,s4=S4]). 
S1 = S3, S3 = 1 ; 
S1 = S4, S4 = 1 ; 
false. 

Очевидно, я сделал следующее предположение: Зависимости дизъюнктивной, что означает, что функция может быть реализована, если по крайней мере один из требований satisifed. Если вы хотите превратить это в соединение, вам, очевидно, придется это изменить. Вы можете начать с представления зависимостей как F -> [R1,R2,...R_n].

Кроме этого, может ли быть полезным перевести ваши идеи на целые числа? Да, потому что многие из ваших ограничений могут быть сформулированы также с ограничениями CLP (FD), и вам нужны целые числа для этого до  .

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

• использование ограничений материализация, чтобы выразить то, что подразумевает, что. Например: F #==> R.
• использовать глобальные ограничения, такие как table/2, которые выражают отношения.

В частности, в первом случае ограничения CLP (B) также могут быть полезными. Вы всегда можете использовать логические переменные, чтобы выразить, должно ли быть требование  .