Прежде всего:
Что здесь происходит?
Чтобы увидеть, что происходит, вот PostScript определений, которые позволяют визуализировать поиск:
<b>/n 5 def</b>
340 n div dup scale
-0.9 0.1 translate % leave room for line strokes
/Palatino-Roman 0.8 selectfont
/coords { n exch sub translate } bind def
/num { 3 1 roll gsave coords 0.5 0.2 translate
5 string cvs dup stringwidth pop -2 div 0 moveto show
grestore } bind def
/clr { gsave coords 1 setgray 0 0 1 1 4 copy rectfill
0 setgray 0.02 setlinewidth rectstroke grestore} bind def
1 1 n { 1 1 n { 1 index clr } for pop } for
Эти определения дают вам две процедуры:
clr, чтобы очистить квадрат num, чтобы показать число наквадрат.
Например, если вы сохраните эти определения в tour.ps, а затем вызовете интерпретатор PostScript Ghostscript с:
gs -r72 -g350x350 tour.ps
, а затемвведите следующие инструкции:
1 2 3 num
1 2 clr
2 3 4 num
Вы получите:
PostScript - отличный язык программирования для визуализации процессов поиска, иЯ также рекомендую проверить postscript для получения дополнительной информации.
Мы можем легко модифицировать вашу программу для выдачи подходящих инструкций PostScript, которые позволяют нам непосредственно наблюдать за поиском.Я выделил соответствующие дополнения:
constrain_entries([], _Square, _X, _Y).
constrain_entries([E|Es], Square, X, Y) :-
<b>freeze(E, postscript(X, Y, E))</b>,
constrain_entry(E, Square, X, Y),
X1 #= X + 1,
constrain_entries(Es, Square, X1, Y).
<b>postscript(X, Y, N) :- format("~w ~w ~w num\n", [X,Y,N]).
postscript(X, Y, _) :- format("~w ~w clr\n", [X,Y]), false.</b>
Я также позволил себе изменить (is)/2 на (#=)/2, чтобы сделать программу более общей.
Предполагая, что вы сохранили определения PostScriptв tour.ps и вашей программе Prolog в tour.pl следующий вызов SWI-Prolog и Ghostscript иллюстрирует ситуацию:
swipl -g "number_puzzle_(_, Vs), label(Vs)" tour.pl | gs -g350x350 -r72 tour.ps -dNOPROMPT
Например, мы видим много возвратов в выделенной позиции:
Тем не менее, основные проблемы уже лежат в другом месте:
Ни один из выделенных квадратов не является действительным ходом!
Исходя из этого, мы видим, что ваша текущая формулировка не позволяет - по крайней мере, недостаточно рано - разрешить решателю распознавать частичное назначение не может быть завершено к решению!Это плохие новости , так как неспособность распознавать несогласованные назначения часто приводит к неприемлемой производительности.Например, чтобы исправить переход 1 → 3 (который никогда не может произойти таким образом, но это уже один из первых вариантов, сделанных в этом случае), решатель должен будет вернуться назад примерно на 8 квадратов после перечисления - какочень грубая оценка - 25 8 = 152587890625 частичных решений, а затем начать все сначала только со второй позиции на доске.
В литературе по ограничениям такиевозврат называется thrashing .Это означает повторный сбой по той же причине .
Как это возможно?Ваша модель кажется правильной и может быть использована для обнаружения решений.Это хорошо!Однако хорошая формулировка ограничений не только распознает решения, но и быстро обнаруживает частичных присвоений, которые не могут быть выполнены решениям.Это то, что позволяет решателю эффективно сократить поиск, и именно в этом важном отношении ваша текущая формулировка не справляется.Одна из причин этого связана с распространением ограничений в уточненных ограничениях , которые вы используете.В частности, рассмотрим следующий запрос:
?- (X + 1 #= 3) #<==> B, <b>X #\= 2</b>.
Интуитивно, мы ожидаем B = 0.Но это не тот случай!Вместо этого мы получаем:
X in inf..1\/3..sup,
X+1#=_3840,
_3840#=3#B,
<b>B in 0..1</b>.
Таким образом, решатель не очень сильно распространяет истинное равенство. Может быть, хотя это и должно быть! Только достаточная обратная связь от специалистов-практиков Пролога скажет, следует ли изменить эту область решателя ограничений, возможно, поменяв немного скорости для более сильного распространения.Высокая актуальность этой обратной связи является одной из причин, почему я рекомендую использовать ограничения CLP (FD) всякий раз, когда у вас есть такая возможность, т. Е. Каждый раз, когда вы рассуждаете о целых числах .
ДляВ этом конкретном случае я могу вам сказать, что укрепление решателя в этом смысле не имеет большого значения.По сути, вы получаете версию платы, в которой все еще возникает основная проблема, со многими переходами (некоторые из них выделены ниже), которые не могут возникнуть ни в одном решении:
Устранение проблемы с ядром
Мы должны устранить причину обратного отслеживания в его ядре .Чтобы сократить поиск, мы должны распознать несогласованные (частичные) назначения ранее.
Интуитивно мы ищем подключенный тур и хотим вернуться назад, как только станет ясно, что тур не может быть продолжен по назначению.
КомуДля достижения того, что мы хотим, у нас есть по крайней мере два варианта:
- изменить стратегию распределения, чтобы принять во внимание связность
- смоделировать проблему таким образом, чтобы связность была более сильно учтенаaccount.
Вариант 1. Стратегия распределения
Основная привлекательность ограничений CLP (FD) заключается в том, что они позволяют нам отделить описание задачи от поиска.При использовании ограничений CLP (FD) мы часто выполняем поиск с помощью label/1 или labeling/2.Тем не менее, мы можем присваивать значения переменным любым способом, который нам нужен .Это очень легко, если мы следуем - как вы это сделали - хорошей практике помещения части «публикации ограничений» в свой собственный предикат, называемый ядро отношения .
Например, здесь пользовательская стратегия размещения, которая гарантирует, что тур всегда остается подключенным:
allocation(Vs) :-
length(Vs, N),
numlist(1, N, Ns),
maplist(member_(Vs), Ns).
member_(Es, E) :- member(E, Es).
С помощью этой стратегии мы получаем решение для экземпляра 5 × 5 с нуля:
?- number_puzzle_(Square, Vars), time(<b>allocation(Vars)</b>).
% 5,030,522 inferences, 0.907 CPU in 0.913 seconds (99% CPU, 5549133 Lips)
Square = square(row(1, 8, 5, 2, 11), ...),
Vars = [1, 8, 5, 2, 11, 16, 21, 24, 15|...]
Существуют различные модификации этой стратегии, которые стоит попробовать.Например, когда допустимы несколько квадратов, мы можем попытаться сделать более разумный выбор, учитывая количество оставшихся доменных элементов квадратов.Я оставляю попытки усовершенствования как вызов.
Из стандартных стратегий маркировки опция маркировки min в этом случае очень похожа на эту стратегию, и она действительно находит решение для 5 ×.5 случай:
?- number_puzzle_(Square, Vars), time(labeling([<b>min</b>], Vars)).
% 22,461,798 inferences, 4.142 CPU in 4.174 seconds (99% CPU, 5422765 Lips)
Square = square(row(1, 8, 5, 2, 11), ...),
Vars = [1, 8, 5, 2, 11, 16, 21, 24, 15|...] .
Однако даже подходящая стратегия распределения не может полностью компенсировать распространение слабых ограничений.Для экземпляра 10 × 10 доска выглядит так после некоторого поиска с опцией min:
min">
Обратите внимание, что мы также должны адаптироватьзначение n в коде PostScript для визуализации этого по назначению.
В идеале, мы должны сформулировать задачу таким образом, чтобы извлечь пользу из сильного распространения, а затем также использоватьхорошая стратегия распределения.
Вариант 2: ремоделирование
Хорошая формулировка CLP распространяется настолько сильно, насколько это возможно (в приемлемое время).Поэтому мы должны стремиться использовать ограничения, которые позволяют решателю с большей готовностью рассуждать о наиболее важных требованиях задачи.В этом конкретном случае это означает, что мы должны попытаться найти более подходящую формулировку для того, что в настоящее время выражается как дизъюнкция ограниченных ограничений, которые, как показано выше, не допускают большого распространения.Теоретически, решатель ограничений может автоматически распознавать такие шаблоны.Однако это нецелесообразно для многих случаев использования, и поэтому мы иногда должны экспериментировать, вручную пробуя несколько многообещающих составов.Тем не менее, и в этом случае: при достаточной обратной связи от программистов приложений, такие случаи с большей вероятностью будут улучшены и проработаны!
Теперь я использую ограничение CLP (FD) circuit/1чтобы прояснить, что мы ищем гамильтонову схему в конкретном графе.График выражается в виде списка целочисленных переменных, где каждый элемент обозначает позицию своего преемника в списке.
Например, список из 3 элементов допускает ровно 2 гамильтоновых схемы:
<b>?- Vs = [_,_,_], circuit(Vs), label(Vs).</b>
Vs = [2, 3, 1] ;
Vs = [3, 1, 2].
Я использую circuit/1 для описания решений, которые также являются закрытыми турами .Это означает, что, если мы найдем такое решение, тогда мы сможем начать сначала с начала действительным ходом с последнего квадрата в найденном туре:
n_tour(N, Vs) :-
L #= N*N,
length(Vs, L),
successors(Vs, N, 1),
circuit(Vs).
successors([], _, _).
successors([V|Vs], N, K0) :-
findall(Num, n_k_next(N, K0, Num), [Next|Nexts]),
foldl(num_to_dom, Nexts, Next, Dom),
V in Dom,
K1 #= K0 + 1,
successors(Vs, N, K1).
num_to_dom(N, D0, D0\/N).
n_x_y_k(N, X, Y, K) :- [X,Y] ins 1..N, K #= N*(Y-1) + X.
n_k_next(N, K, Next) :-
n_x_y_k(N, X0, Y0, K),
( [DX,DY] ins -2 \/ 2
; [DX,DY] ins -3 \/ 0 \/ 3,
abs(DX) + abs(DY) #= 3
),
[X,Y] ins 1..N,
X #= X0 + DX,
Y #= Y0 + DY,
n_x_y_k(N, X, Y, Next),
label([DX,DY]).
Обратите внимание, как допустимые преемники теперь выражаются как элементы домена , что сокращает количество ограничений и полностью устраняет необходимость в пересмотрах.Самое главное, что предполагаемая связность теперь автоматически учитывается и применяется в каждой точке во время поиска.Предикат n_x_y_k/4 связывает (X,Y) координаты с индексами списка.Вы можете легко адаптировать эту программу к другим задачам (например, тур рыцаря), изменив n_k_next/3.Я оставляю обобщение для открытых туров в качестве проблемы.
Вот дополнительные определения, которые позволяют нам печатать решения в более удобочитаемой форме:
:- set_prolog_flag(double_quotes, chars).
print_tour(Vs) :-
length(Vs, L),
L #= N*N, N #> 0,
length(Ts, N),
tour_enumeration(Vs, N, Es),
phrase(format_string(Ts, 0, 4), Fs),
maplist(format(Fs), Es).
format_(Fs, Args, Xs0, Xs) :- format(chars(Xs0,Xs), Fs, Args).
format_string([], _, _) --> "\n".
format_string([_|Rest], N0, I) -->
{ N #= N0 + I },
"~t~w~", call(format_("~w|", [N])),
format_string(Rest, N, I).
tour_enumeration(Vs, N, Es) :-
length(Es, N),
maplist(same_length(Es), Es),
append(Es, Ls),
foldl(vs_enumeration(Vs, Ls), Vs, 1-1, _).
vs_enumeration(Vs, Ls, _, V0-E0, V-E) :-
E #= E0 + 1,
nth1(V0, Ls, E0),
nth1(V0, Vs, V).
В формулировках с сильным распространением предопределенная стратегия поиска ff часто является хорошей стратегией.И действительно, это позволяет нам решить всю задачу, т. Е. Оригинальный экземпляр 10 × 10, в течение нескольких секунд на обычном компьютере:
?- n_tour(10, Vs),
time(labeling([ff], Vs)),
print_tour(Vs).
<b>% 5,642,756 inferences, 0.988 CPU in 0.996 seconds (99% CPU, 5710827 Lips)</b>
1 96 15 2 97 14 80 98 13 79
93 29 68 94 30 27 34 31 26 35
16 3 100 17 4 99 12 9 81 45
69 95 92 28 67 32 25 36 33 78
84 18 5 83 19 10 82 46 11 8
91 23 70 63 24 37 66 49 38 44
72 88 20 73 6 47 76 7 41 77
85 62 53 86 61 64 39 58 65 50
90 22 71 89 21 74 42 48 75 43
54 87 60 55 52 59 56 51 40 57
Vs = [4, 5, 21, 22, 8, 3, 29, 26, 6|...]
Для максимальной производительности, я рекомендую вам также попробовать это с другими Prologсистемы.Эффективность систем CLP (FD) коммерческого уровня часто является важной причиной для покупки системы Prolog.
Следует также отметить, что это ни в коем случае не является единственной многообещающей формулировкой задачи Prolog или даже CLP (FD).и я оставляю думать о других формулировках как о проблеме.