Я не понимаю, что делает ярлык в Прологе
Я просмотрел руководство и документацию, но до сих пор не понимаю. Я пытаюсь реализовать решение судоку, в котором после написания всех других правил игры я добавил ярлык (доску) в соответствии с инструкциями моего учителя.
Однако я все еще не понимаю, как это работает или что он делает. Разве другие ограничения (у меня есть проверки, говорящие о том, что числа должны быть 1..9, строки должны быть разными и т. Д.) Не могли бы дать мне ответ сам по себе?
2 ответа
Если вы хотите быстро изучить Prolog и CLP(FD), используйте оболочку высшего уровня Prolog, чтобы поиграть, пока вы не освоитесь с ней. Фактически все, что вам нужно знать о CLP(FD) и Прологе, можно объяснить там; или почти. Не нужно писать (как их зовут?) Файлы, все помещается в одну строку. Да, я знаю, наши родители предупредили нас: "Мой ребенок, пообещай мне, никогда не делай строчки". Но вы будете учиться намного быстрее.
Так у вас есть ?- ждать?
В традиционном Прологе (без ограничений) то, что вы получаете от запроса, это так называемая замена ответа. Во многих ситуациях такая замена ответа уже описывает решение. Это тот случай, если для каждой переменной найден свободный термин переменной. Давайте рассмотрим конкретный пример и опишем список из 5 элементов, где каждый элемент имеет значение от 1 до 5. В этом случае решения находятся для разных значений для L,
?- N = 5, length(L,N),maplist(between(1,N),L).
N = 5, L = [1, 1, 1, 1, 1] ;
N = 5, L = [1, 1, 1, 1, 2] ;
N = 5, L = [1, 1, 1, 1, 3] ...
Пролог покажет вам только одно решение (в тайне надеясь, что вы будете довольны им, оно немного ленивое, а не строгое). Вы получаете все из них, набрав пробел или ;, Попробуйте немного, чтобы увидеть, сколько их...
Всего 5^5 решения. Это не очень практично, если вы просто хотите выбрать несколько решений из этого множества. Большой набор решений представляется весьма неэффективным образом. А потом подумайте о бесконечных множествах! Как может Пролог или любое конечное существо перечислить бесконечное множество? Мы можем только начать делать это, конечно, как мы.
Чтобы преодолеть это, Прологу не всегда приходится показывать конкретные значения, то есть решения, но он может немного их перечислить, показывая вместо этого ответы:
?- N = 5, length(L,N).
N = 5, L = [_A, _B, _C, _D, _E].
Этот ответ (-замена) содержит все 5^5 ответы выше и многое, многое другое, как L = [stack,over,flow,dot,com], На самом деле, он описывает бесконечный набор решений! Разве я не говорил, что мы, ограниченные существа, не можем этого сделать? Пока мы настаиваем на конкретных решениях, мы не можем, но если вместо этого мы довольны ответами, мы можем сделать невозможное.
Эта идея может быть расширена для описания более конкретных наборов. Все с одним ответом. Для множеств о целых числах мы имеем library(clpfd), Используйте это так:
?- use_module(library(clpfd)).
?- asserta(clpfd:full_answer). % only necessary for SICStus
Теперь мы можем переформулировать наш исходный запрос (в SWI вы можете сделать Курсор вверх ↑, чтобы получить его):
?- N = 5, length(L,N),L ins 1..N.
N = 5, L = [_A, _B, _C, _D, _E],
_A in 1..5, _B in 1..5, _C in 1..5, _D in 1..5,_E in 1..5.
Теперь все 3125 решений компактно описаны с одним ответом. (3125? Это 5^5). Мы можем продолжать формулировать дополнительные требования, например, что они все разные:
?- N = 5, length(L,N),L ins 1..N, all_different(L).
N = 5, L = [_A, _B, _C, _D, _E],
_A in 1..5,_B in 1..5,_C in 1..5,_D in 1..5,_E in 1..5,
all_different([_A, _B, _C, _D, _E]).
Общим (практически) общим ограничением является то, что они не перечисляют решения, а пытаются поддерживать согласованность. Давайте попробуем это, заявив, что первый элемент должен быть 1:
?- N = 5, length(L,N),L ins 1..N, all_different(L), L = [1|_].
N = 5, L = [1, _A, _B, _C, _D],
_A in 2..5,_B in 2..5,_C in 2..5,_D in 2..5,
all_different([1, _A, _B, _C, _D]).
Вы видели эффект? Они быстро изменили свои домены! Теперь они все в 2..5,
И все они должны быть в 1..4:
?- N = 5, length(L,N),L ins 1..N, all_different(L), L = [1|_], L ins 1..4.
N = 5, L = [1, _A, _B, _C, _D],
_A in 2..4,_B in 2..4,_C in 2..4,_D in 2..4,
all_different([1, _A, _B, _C, _D]).
Опять они обновляются. Но... подумайте об этом: осталось 4 переменные, все они должны быть разными, но для них есть только 3 разных значения.
Итак, мы застали Пролога немного ленивым. Там на самом деле есть лучшее ограничение под названием all_distinct/1 сейчас это потерпит неудачу, но независимо от того, сколько у системы умных ограничений, всегда будут такие несоответствия. Спросите профессора Геделя. Единственными способами выручить были бы ошибки или бесконечные циклы.
Поэтому нам нужен другой метод, чтобы быть уверенным, что ответ описывает реальные решения. Введите маркировку! С label/1 или же labeling/2 мы можем устранить все эти странные ограничения и несоответствия:
?- N = 5, length(L,N),L ins 1..N, all_different(L), L = [1|_], L ins 1..4, labeling([], L).
false.
?- N = 5, length(L,N),L ins 1..N, all_different(L), L = [1|_], labeling([], L).
N = 5, L = [1, 2, 3, 4, 5] ;
N = 5, L = [1, 2, 3, 5, 4] ;
N = 5, L = [1, 2, 4, 3, 5] ...
Как мы можем быть уверены, что это реальные решения? Легко: они не содержат никаких дополнительных целей, кроме ответов на вопросы 1. Ибо, если мы забыли немного:
?- N = 5, length(L,N),L ins 1..N, all_different(L), L = [1,B,C|_], labeling([],[B,C]).
N = 5, L = [1, 2, 3, _A, _B], B = 2, C = 3,
_A in 4..5, _B in 4..5,
all_different([1, 2, 3, _A, _B]),
Они бы показали.
SWI-х labeling/2 имеет очень полезную гарантию:
Маркировка всегда завершена, всегда заканчивается и не приводит к избыточным решениям.
1 Поскольку верхний уровень SWI не показывает все ограничения, вам нужно будет перенести call_residue_vars(Goal, Vs) вокруг него. Но для простых запросов верхнего уровня выше достаточно.
Грубо говоря, в программировании ограничений есть 2 этапа: распространение ограничений и поиск.
Только распространение ограничений может дать конкретные значения, и это часто так. Но в целом, это только уменьшает область (набор возможных значений для переменной) до меньшего подмножества, и тогда вам нужен поиск (значения меток из подмножества, полученные с распространением ограничения).
Очень простой пример (псевдокод):
A #:: 0..1,
B #:: 0..1,
A #\= B
Распространение ограничений не может решить это само по себе, оно не может даже уменьшить область A или B - оно может только создать отложенное ограничение. После этого поиск (метка) пытается получить значение 0 для A, отсроченное ограничение срабатывает, и домен B уменьшается до {1}.
Напротив, это может быть решено только с помощью распространения ограничений:
A #:: 1,
B #:: 0..1,
A #\= B