Пролог ручная или нестандартная маркировка

Question

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

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

У меня вопрос, как я могу вручную пометить мои переменные? Я боюсь, что после определения переменной clpfd, как это:

X in Xinf..Xsup

и ограничивая его, если я сделаю что-то вроде:

    fd_sup(X, Xmax),
    X = Xmax,
...

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

Кроме того, есть ли более умный способ маркировки моих переменных, чем написание пользовательских процедур маркировки? Моя идея эвристики состоит в том, чтобы альтернативно попробовать экстремумы переменной области (например, max(X), min(X), max(X-1), min(X-1) и т. Д.)

Надеюсь, вы можете помочь мне:)

Answer 1

Во-первых, всегда пробуйте встроенную эвристику. ff часто хорошая стратегия.

Для пользовательских стратегий маркировки часто проще сначала преобразовать домен в список, затем изменить порядок списка, а затем просто использовать member/2 назначить значения домена, используя новый порядок.

Хорошее строение черного цвета dom_integers/2, связывающий конечный домен CLP(FD) со списком целых чисел:

:- use_module(library(clpfd)).

dom_integers(D, Is) :- phrase(dom_integers_(D), Is).

dom_integers_(I)      --> { integer(I) }, [I].
dom_integers_(L..U)   --> { numlist(L, U, Is) }, Is.
dom_integers_(D1\/D2) --> dom_integers_(D1), dom_integers_(D2).

Ваша конкретная стратегия легко выражается в списке таких упорядоченных целых чисел, связывая эти целые числа со вторым списком, где значения встречаются в порядке, который вы описываете:

outside_in([]) --> [].
outside_in([I]) --> [I].
outside_in([First|Rest0]) --> [First,Last],
        { append(Rest, [Last], Rest0) },
        outside_in(Rest).

Пример запроса и результат:

? - фраза (outside_in([1,2,3,4]), есть).Is = [1, 4, 2, 3];
ложный.

Сочетая это с fd_dom/2 а также dom_integers/2мы получаем (привязки для переменных, кроме X опущены):

?- X in 10..20,
   fd_dom(X, Dom),
   dom_integers(Dom, Is0),
   phrase(outside_in(Is0), Is),
   member(X, Is).
X = 10 ;
X = 20 ;
X = 11 ;
X = 19 ;
X = 12 ;
X = 18 ;
etc.

Недетерминизм сохраняется member/2,

Answer 2

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

Двумя основными компонентами процедуры маркировки являются

1. выбор переменной: из всех оставшихся (т.е. еще не созданных) переменных задачи выберите одну, чтобы рассмотреть следующую.
2. Выбор значения или ответвление: исследуйте посредством обратного отслеживания две или более альтернативных подзадач, уменьшая область выбранной переменной (обычно) дополнительными способами.

Используя эту схему, процедуру маркировки по умолчанию можно записать как

label(Xs) :-
    ( select_variable(X, Xs, Xs1) ->
         branch(X),
         label(Xs1)
    ;
         true    % done, no variables left
    ).

select_variable(X, [X|Xs], Xs).     % 'leftmost' strategy

branch(X) :- indomain(X).

Теперь вы можете переопределить select_variable/3 реализовать такие методы, как "первый сбой", и переопределить branch/1 попробовать значения доменов в разных порядках. Пока вы уверены, что branch/1 перечисляет все XЗначения доменов при возврате, ваш поиск остается завершенным.

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

branch(X) :-
    fd_sup(X, Xmax),
    (
         X = Xmax           % try the maximum
    ;
         X #\= Xmax         % otherwise exclude the maximum
    ).

Поскольку эти два случая дополняют друг друга и охватывают все возможные значения X, ваш поиск все еще завершен. Однако из-за второй альтернативы branch/1 теперь может преуспеть с необоснованным XЭто означает, что вы должны убедиться, что в процедуре маркировки вы не потеряете эту переменную из своего списка. Одна возможность будет:

label(Xs) :-
    ( select_variable(X, Xs, Xs1) ->
         branch(X),
         ( var(X) -> append(Xs1, [X], Xs2) ; Xs2=Xs1 ),
         label(Xs2)
    ;
         true    % done, no variables left
    ).

Answer 3

Убедитесь, что вы отличаете стратегии маркировки от дополнительного распространения. Эти два аспекта в настоящее время немного смешаны в вашем вопросе.

В SWI-Прологе есть предикат clpfd:contracting/1, Он делает то, что вы описываете: он пробует значения из границ домена и удаляет значения, которые могут рассматриваться как несогласованные, т. Е. Для которых известно, что решения не существует.

Поэтому, если у вас есть список переменных Vs, ты можешь попробовать: clpfd:contracting(Vs)и посмотрите, поможет ли это.

Обратите внимание, что это также может значительно замедлить поиск, хотя, с другой стороны, также поможет значительно сократить пространство поиска, даже не пытаясь пометить метки!

Answer 4

В дополнение к другим ответам (одна контрастная маркировка и распространение, другая, показывающая выделенный метод маркировки), я теперь рассмотрю еще один очень важный аспект этого вопроса:

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

Следовательно, этот ответ указывает вам на то, чтобы сначала обеспечить фактическое прекращение ваших отношений.

Лучший способ обеспечить завершение программ CLP(FD) - разделить их на 2 части:

1. первое, называемое основным отношением, просто публикует все ограничения.
2. второе использование labeling/2 выполнить фактический поиск.

Вы сделали это в своей программе? Если нет, пожалуйста, сделайте. Когда это будет сделано, убедитесь, что основное отношение, скажем solution/2 (где аргументы: термин, обозначающий экземпляр задачи и список переменных, которые должны быть помечены) универсально завершается с помощью запроса:

?- solution(Instance, Vs), false.

Если это завершается, то следующее также прекращается:

?- solution(Instance, Vs), label(Vs), false.

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

Поэтому проверьте, заканчивается ли ваше основное отношение!

Answer 5

Это следует за предыдущим ответом @mat.

Если у вас есть еще несколько циклов ЦП для записи, попробуйте shave_zs/1 как определено в этом предыдущем ответе.

shave_zs/1 такие работы, как предикат вспомогательной библиотеки clpfd:contracting/1, В отличие от contracting/1однако, все значения "на руку", а не только на границе. YMMV!