Я думаю, что моделирование этой головоломки с помощью CLPFD может быть выполнено с помощью automaton / 8. На Прологе я бы написал
escape_zurg(T,S) :-
aggregate(min(T,S), (
solve([5,10,20,25], [], S),
sum_timing(S, T)), min(T,S)).
solve([A, B], _, [max(A, B)]).
solve(L0, R0, [max(A, B), C|T]) :-
select(A, L0, L1),
select(B, L1, L2),
append([A, B], R0, R1),
select(C, R1, R2),
solve([C|L2], R2, T).
sum_timing(S, T) :-
aggregate(sum(E), member(E, S), T).
что дает это решение
?- escape_zurg(T,S).
T = 60,
S = [max(5, 10), 5, max(20, 25), 10, max(10, 5)].
редактировать
ну, автомат / 8 мне недоступен ... давайте начнем проще: что может быть простым представлением состояния? слева / справа у нас есть 4 слота, которые могут быть пустыми: итак
escape_clpfd(T, Sf) :-
L0 = [_,_,_,_],
Zs = [0,0,0,0],
L0 ins 5\/10\/20\/25,
all_different(L0),
...
теперь, поскольку проблема настолько проста, мы можем жестко запрограммировать изменение состояния
...
lmove(L0/Zs, 2/2, L1/R1, T1), rmove(L1/R1, 1/3, L2/R2, T2),
lmove(L2/R2, 3/1, L3/R3, T3), rmove(L3/R3, 2/2, L4/R4, T4),
lmove(L4/R4, 4/0, Zs/ _, T5),
...
первый lmove/4 должен сдвинуть 2 элемента слева направо, и после этого у нас будет 2 нуля слева и 2 справа. Время (T1) будет max(A,B), где A, B к настоящему времени инкогнито. rmove/4 аналогичен, но «вернет» в T2 единственный элемент (инкогнито), который он будет перемещать справа налево. Мы кодируем эволюцию, утверждая количество нулей на каждой стороне (кажется, нетрудно обобщить).
Завершим:
...
T #= T1 + T2 + T3 + T4 + T5,
Sf = [T1,T2,T3,T4,T5].
Теперь rmove / 4 проще, поэтому давайте закодируем его:
rmove(L/R, Lz/Rz, Lu/Ru, M) :-
move_one(R, L, Ru, Lu, M),
count_0s(Ru, Rz),
count_0s(Lu, Lz).
он откладывает фактическую работу move_one / 5, а затем применяет числовое ограничение, которое мы жестко запрограммировали выше:
count_0s(L, Z) :-
maplist(is_0, L, TF),
sum(TF, #=, Z).
is_0(V, C) :- V #= 0 #<==> C.
is_0 / 2 усиливает условие пустого слота, то есть делает счетным значение истинности. Стоит протестировать:
?- count_0s([2,1,1],X).
X = 0.
?- count_0s([2,1,C],1).
C = 0.
?- count_0s([2,1,C],2).
false.
Кодирование move_one / 5 в CLP (FD) кажется сложным. Здесь действительно уместен недетерминизм Пролога ...
move_one(L, R, [Z|Lt], [C|Rt], C) :-
select(C, L, Lt), is_0(C, 0),
select(Z, R, Rt), is_0(Z, 1).
select / 3 это чистый предикат, и Prolog вернется, когда для маркировки потребуется ...
Минимизации нет, но ее легко добавить после того, как мы получим решения. Пока все кажется мне «логичным». Но конечно...
?- escape_clpfd(T, S).
false.
Итак, вот драконы ...
?- spy(lmove),escape_clpfd(T, S).
% Spy point on escape_zurg:lmove/4
* Call: (9) escape_zurg:lmove([_G12082{clpfd = ...}, _G12164{clpfd = ...}, _G12246{clpfd = ...}, _G12328{clpfd = ...}]/[0, 0, 0, 0], 2/2, _G12658/_G12659, _G12671) ? creep
Call: (10) escape_zurg:move_one([_G12082{clpfd = ...}, _G12164{clpfd = ...}, _G12246{clpfd = ...}, _G12328{clpfd = ...}], [0, 0, 0, 0], _G12673, _G12674, _G12661) ? sskip
... и т. д. и т. д.
Извините, опубликую решение, если у меня будет свободное время для отладки ...
edit было несколько ошибок ... с этим lmove / 4
lmove(L/R, Lz/Rz, Lu/Ru, max(A, B)) :-
move_one(L, R, Lt, Rt, A),
move_one(Lt, Rt, Lu, Ru, B),
count_0s(Lu, Lz),
count_0s(Ru, Rz).
по крайней мере, мы начинаем получать решения (добавлены переменные в интерфейс для маркировки извне ...)
escape_clpfd(T, Sf, L0) :- ...
?- escape_clpfd(T, S, Vs), label(Vs).
T = 85,
S = [max(5, 10), 10, max(10, 20), 20, max(20, 25)],
Vs = [5, 10, 20, 25] ;
T = 95,
S = [max(5, 10), 10, max(10, 25), 25, max(25, 20)],
Vs = [5, 10, 25, 20] ;
...
редактировать
приведенный выше код работает, но очень медленно:
?- time((escape_clpfd(60, Sf, L0),label(L0))).
% 15,326,054 inferences, 5.466 CPU in 5.485 seconds (100% CPU, 2803917 Lips)
Sf = [max(5, 10), 10, max(20, 25), 5, max(5, 10)],
L0 = [5, 10, 20, 25]
с этим изменением на move_one / 5:
move_one([L|Ls], [R|Rs], [R|Ls], [L|Rs], L) :-
L #\= 0,
R #= 0.
move_one([L|Ls], [R|Rs], [L|Lu], [R|Ru], E) :-
move_one(Ls, Rs, Lu, Ru, E).
У меня производительность лучше:
?- time((escape_clpfd(60, Sf, L0),label(L0))).
% 423,394 inferences, 0.156 CPU in 0.160 seconds (97% CPU, 2706901 Lips)
Sf = [max(5, 10), 5, max(20, 25), 10, max(5, 10)],
L0 = [5, 10, 20, 25]
затем, добавив к lmove / 4
... A #< B, ...
я получил
% 233,953 inferences, 0.089 CPU in 0.095 seconds (94% CPU, 2621347 Lips)
Sf = [max(5, 10), 5, max(20, 25), 10, max(5, 10)],
в целом это все еще намного медленнее, чем мое чистое решение Prolog ...
редактировать
другие небольшие улучшения:
?- time((escape_clpfd(60, Sf, L0),maplist(#=,L0,[5,10,20,25]))).
% 56,583 inferences, 0.020 CPU in 0.020 seconds (100% CPU, 2901571 Lips)
Sf = [max(5, 10), 5, max(20, 25), 10, max(5, 10)],
где all_different / 1 заменено на
...
chain(L0, #<),
...
Еще одно улучшение: считать обе стороны на нули бесполезно: удаляя (произвольно) одну сторону как в lmove, так и в rmove, мы получаем
% 35,513 inferences, 0.014 CPU in 0.014 seconds (100% CPU, 2629154 Lips)
Sf = [max(5, 10), 5, max(20, 25), 10, max(5, 10)],
редактировать
Ради удовольствия, вот то же самое чистое (за исключением агрегации) решение Prolog, использующее простой детерминированный «подъем» переменных (любезно предоставлено lifter '):
:- use_module(carlo(snippets/lifter)).
solve([A, B], _, [max(A, B)]).
solve(L0, R0, [max(A, B), C|T]) :-
solve([C|select(B, select(A, L0, °), °)],
select(C, append([A, B], R0, °), °),
T).
кстати, довольно быстро:
?- time(escape_zurg(T,S)).
% 50,285 inferences, 0.065 CPU in 0.065 seconds (100% CPU, 769223 Lips)
T = 60,
S = [max(5, 10), 5, max(20, 25), 10, max(10, 5)].
(абсолютная синхронизация не так хороша, потому что я использую SWI-Prolog, скомпилированный для отладки)
person
CapelliC
schedule
07.10.2015
