PROLOG CLPFD минимизировать выражение

У меня есть список переменных L по конечной области. Например:

:- use_module(library(clpfd)).

example :-
    L = [_,_,_],
    L ins 1..10,
    ...

Более того, у меня есть предикат

pred(L,C)

что для любого присвоения L значениям домена дает стоимость C.

Вопрос в том, как использовать функцию маркировки CLPFD, чтобы найти присвоение L, которое минимизирует C.

example :-
    L = [_,_,_],
    L ins 1..10,
    pred(L,C),
    labeling([min(C)],L),
    write(L).

Не работает. Он просто выбирает первое назначение (т. Е. [1,1,1]).


label labeling prolog clpfd
person user2460978    schedule 12.01.2014    source источник
comment
Возможно, это единственное решение, потому что 0 нельзя использовать?   -  person joel76    schedule 12.01.2014
comment
joel76, вы предполагаете кое-что о пред   -  person user2460978    schedule 12.01.2014

Ответы (1)


arrow_upward
4
arrow_downward

Скорее всего, C уже создан на момент вызова labeling/2 в этом примере. Тогда цель будет выглядеть примерно так:

labeling([min(1)], Ls)

и, конечно, не осталось места для фактического минимизации C здесь в течение labeling/2.

Чтобы это работало, вы должны сформулировать pred/2 так, чтобы C был детерминированно связан с переменными Vs через ограничения. Например:

sum(Vs, #=, C), labeling([min(C)], Vs)

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

Я проиллюстрирую свои дальнейшие предложения, переписав ваш пример как:

example(Ls) :-
    Ls = [_,_,_],
    Ls ins 1..10,
    pred(Ls, C),
    labeling([min(C)], Ls).

Обратите внимание, в частности:

  1. Мне не нужно использовать write/1, потому что на верхнем уровне Prolog будет отображаться решение, когда я буду запрашивать ?- example(Ls).
  2. Я позволяю именам переменных, обозначающих списки, заканчиваться на s по аналогии с построением множественного числа в английском языке.
person mat    schedule 12.01.2014
comment
Спасибо, теперь я понимаю, почему не работает. Однако в этом случае я думаю, что это слишком сложно сформулировать с помощью ограничений. Безусловно, он должен включать рекурсию. - person user2460978; 12.01.2014
comment
Реификация ограничений часто бывает полезна для выражения более сложных ограничений. Если ничего не помогает, вы также можете реализовать собственный пропагатор. - person mat; 12.01.2014