DCG состояние реализации алгоритма
Расстояние между длинной последовательностью и короткой последовательностью - это минимальное расстояние между короткой последовательностью и любой подпоследовательностью длинной последовательности, равное длине короткой последовательности.
Расстояние, которое я использую, - это, я думаю, расстояние до Манхэттена. (Но это должно быть неважно, так как я хотел бы иметь возможность изменять функции расстояния).
Эта первая версия показывает наивную реализацию без раннего отказа. Я генерирую все подпоследовательности одинаковой длины, отображаю их, чтобы найти расстояние между ними и короткой последовательностью, а затем использую агрегат /3, чтобы найти мин.
abs(X,Y,Z):-
Z is abs(X-Y).
seq_seq_absdis(Seq1,Seq2,Dis):-
same_length(Seq1,Seq2),
maplist(abs,Seq1,Seq2,Dislist),
sumlist(Dislist,Dis).
seq_subseq(List1,List2):-
append(List2,_,List1),
dif(List2,[]).
seq_subseq([_|T],Subseq):-
seq_subseq(T,Subseq).
smallseq_largeseq_dis(Sseq,Lseq,Dis):-
findall(Subseq, (same_length(Subseq,Sseq),seq_subseq(Lseq,Subseq)),Subseqs),
maplist(seq_seq_absdis(Sseq),Subseqs,Distances),
aggregate(min(D),member(D,Distances),Dis).
Пример запроса:
?-smallseq_largeseq_dis([1,2,4],[1,2,3,1,2,5],Dis).
Dis = 1
Эта следующая версия должна быть более эффективной, так как она откажется от вычисления расстояния между подпоследовательностью длинной последовательности и короткой последовательностью, как только расстояние превысит уже найденный минимум.
ea_smallseq_largeseq_dis(Sseq,Lseq,Subseq,Dis):-
retractall(best(_,_)),
assert(best(initial,10000)),
findall(Subseq-Dis, ea_smallseq_largeseq_dis_h(Sseq,Lseq,10000,Subseq,Dis),Pairs),
append(_,[Subseq-Dis|[]],Pairs).
ea_smallseq_largeseq_dis_h(Sseq,Lseq,BestSofar1,Subseq,Dis):-
same_length(Sseq,Subseq),
seq_subseq(Lseq,Subseq),
best(_,BestSofar2),
( ( BestSofar2 < BestSofar1) ->
accumulate_dis(Sseq,Subseq,BestSofar2,Dis),
retractall(best(_,_)),
assert(best(Subseq,Dis))
;(
accumulate_dis(Sseq,Subseq,BestSofar1,Dis),
retractall(best(_,_)),
assert(best(Subseq,Dis))
)
).
accumulate_dis(Seq1,Seq2,Best,Dis):-
accumulate_dis(Seq1,Seq2,Best,Dis,0).
accumulate_dis([],[],_Best,Dis,Dis).
accumulate_dis(Seq1,Seq2,Best,Dis,Ac):-
Seq1=[H1|T1],
Seq2=[H2|T2],
abs(H1,H2,Dis1),
Ac1 is Dis1 + Ac,
Ac1 <Best,
accumulate_dis(T1,T2,Best,Dis,Ac1).
Запрос:
?-ea_smallseq_largeseq_dis([1,2,3],[1,2,4,5,6,7,8,1,2,3],Subseq,Dis).
Dis = 0,
Subseq = [1, 2, 3]
Но в этом я использовал assert и retract, поэтому я хочу иметь версию, которая выполняет тот же алгоритм, но без них. Я думаю, что я должен быть в состоянии сделать это с помощью dcg с полуконтекстовой нотацией, но мне трудно это понять... как я могу отслеживать подпоследовательности, которые я генерирую при возврате, и в то же время "состояние" минимального расстояния нашел так далеко?
У меня проблема.. seq_subseq/2 генерирует подпоследовательности путем обратного отслеживания. Первый проверенный последующий запрос должен быть установлен на минимальное расстояние. Затем я хочу зациклить, поэтому вернемся назад, чтобы создать другую последовательность. Но чтобы вернуться на прежний уровень, я должен потерпеть неудачу. Но тогда я не могу вернуть минимальное расстояние, чтобы проверить следующую последовательность.
Если я не хочу использовать возврат, мне нужно определить предикат перехода состояния для генерации подпоследовательностей по порядку.
В данный момент
? seq_subseq([1,2,3,4],X).
X = [1]
X = [1, 2]
X = [1, 2, 3]
X = [1, 2, 3, 4]
X = [2]
X = [2, 3]
X = [2, 3, 4]
X = [3]
X = [3, 4]
X = [4]
Поэтому я думаю, что мне нужно определить отношение:
subseq0_seq_subseq1(Subseq0,Seq,Subseq1)
Это будет работать так:
?-subseq0_seq_subseq1([1,2,3,4],[1,2,3,4],Subseq1).
Subseq1 = [2].
а также
?-subseq0_seq_subseq1([1,2,3],[1,2,3,4],Subseq1).
Subseq1 = [1,2,3,4].
Но мне нужно сделать это эффективно.
Обновление - благодаря ответу от Мата у меня теперь есть это, и я думаю, что это большое улучшение. Кто-нибудь может увидеть дальнейшие улучшения в этом? У меня двойная вложенная структура -> и! в определении Наклят_дис /4 оба кажутся безобразными. Я также заставил его возвращать подпоследовательность длинной последовательности, которая является кратчайшим расстоянием от короткой последовательности.
Он должен работать с не целыми числами, поэтому я думаю, что clpfd не подходит.
abs(X,Y,Z):-
Z is abs(X-Y).
list_subseq_min(Ls, Subs, Min,BestSeq1) :-
prefix_dist(Ls, Subs, 1000, Front, D0),
BestSeq0=Front,
min_sublist(Ls, Subs,BestSeq0,BestSeq1, D0, Min).
prefix_dist(Ls, Ps, Best,Front,D) :-
same_length(Front, Ps),
append(Front, _, Ls),
accumulate_dis(Front, Ps, Best, D).
min_sublist(Ls0, Subs, BestSeq0,BestSeq2, D0, D) :-
( prefix_dist(Ls0, Subs, D0, Front,D1) ->
min_list([D0,D1],D2),
Ls0 = [_|Ls],
( D0 < D1 ->
BestSeq1 =BestSeq0
;
BestSeq1 =Front
),
min_sublist(Ls, Subs, BestSeq1,BestSeq2, D2, D)
; D = D0,BestSeq0 =BestSeq2
).
accumulate_dis(Seq1,Seq2,Best,Dis):-
accumulate_dis(Seq1,Seq2,Best,Dis,0),!.
accumulate_dis([],[],_Best,Dis,Dis).
accumulate_dis(Seq1,Seq2,Best,Dis,Ac):-
Seq1=[H1|T1],
Seq2=[H2|T2],
abs(H1,H2,Dis1),
Ac1 is Dis1 + Ac,
Ac1 <Best,
accumulate_dis(T1,T2,Best,Dis,Ac1).
accumulate_dis(Seq1,Seq2,Best,Dis):-Dis is Best+1.
запрос:
?- list_subseq_min([2.1,3.4,4,1.1,2,4,10,12,15],[1,2,3],D,B).
D = 1.1,
B = [1.1, 2, 4].
1 ответ
Одно важное замечание: вы должны были уточнить, что вы говорите о расстоянии между списками по Манхэттену. Это было ясно только из вашего кода, тогда как ваша формулировка может легко заставить читателей предположить, что вы говорите о расстоянии редактирования.
Вот решение, которое просто просматривает список, отслеживает минимум и, в конечном итоге, дает найденный минимум.
list_subseq_min (Ls, Subs, Min): -
prefix_dist (Ls, Subs, D0),
min_sublist (Ls, Subs, D0, Min).
absdiff (X, Y, Z): - Z # = abs (XY).
lists_dist(Ls1, Ls2, D):-
список карт (absdiff, Ls1, Ls2, Ds),
сумма (Ds, #=, D).
prefix_dist(Ls, Ps, D):-
same_length(фронт, пс),
добавить (передний, _, Ls),
lists_dist(Front, Ps, D).
min_sublist(Ls0, Subs, D0, D):-
( prefix_dist(Ls0, Subs, D1) ->
D2 #= мин (D0,D1),
Ls0 = [_|Ls],
min_sublist(Ls, Subs, D2, D); D #= D0).
Пример запроса и его результат:
? - list_subseq_min ([1,2,3,1,2,5], [1,2,4], D). D = 1.
Это довольно просто, и, поскольку бухгалтерия ограничена только одним предикатом, использование полуконтекстных обозначений на самом деле не окупается. Особенно полезно использовать полуконтекстную нотацию - и DCG в целом - когда то, что описывается, охватывает различные правила, и в противном случае связь между ними будет сложнее.
Время работы в O (N × M).
А теперь пункт, который я оставляю в качестве упражнения: измените это решение, чтобы сократить ранее, если ранее найденный минимум уже превышен. Делайте это чистым способом или, по крайней мере, настолько чистым, насколько это возможно: assertz/1 и о друзьях определенно не может быть и речи, поскольку они мешают вам тестировать эти предикаты изолированно. Обходите аргументы и увеличивайте расстояние постепенно! Это может помочь вам улучшить среднее время выполнения, хотя, конечно, не в худшем случае.
Именно для этого обхода состояний между различными предложениями полуконтекстная запись может, наконец, стать полезной.
РЕДАКТИРОВАТЬ: Очень хорошо, вы внедрили решение, которое делает сокращение. Я сейчас тоже покажу свою. Я буду использовать вспомогательные предикаты absdiff/3 а также lists_dist/3 сверху и следующий дополнительный вспомогательный предикат:
same_length_prefix (Ls, Ps, Front): -
same_length (фронт, пс),
добавить (Front, _, Ls).
list_subseq_min/3 теперь немного отличается:
list_subseq_min (Ls, Subs, Min): -
same_length_prefix (Ls, Subs, Front),
lists_dist (Front, Subs, D0),
фраза (min_sublist(Ls, Subs), [D0-Front], [Min-_]).
А теперь суть: min_sublist//2 это нетерминал DCG, который кратко описывает основную идею алгоритма:
min_sublist (Ls0, Subs) ->
(спереди (Ls0, Subs) ->
{ Ls0 = [_|Ls] },
min_sublist(Ls, Subs); []).
Из этого описания очень ясно, что мы рассматриваем список элемент за элементом. Он использует меньше (явных) аргументов, чем ранее. Два дополнительных аргумента неявно передаются как пара D-Front, который отслеживает лучшее расстояние и последовательность, найденную до сих пор. Обратите внимание, как нотация DCG раскрывает суть вычислений и скрывает то, что не имеет значения в этом месте.
Все остальное не требует пояснений и аналогично выполненному вами сокращению. Я подчеркиваю единственное использование полуконтекстовой нотации в этой программе, которая позволяет нам выразить любое изменение оптимальной последовательности, найденной до сих пор.
front (Ls, Subs), [D-Front] ->
[Current],
{ same_length_prefix(Ls, Subs, Front1),
capped_dist(Front1, Subs, Current, 0-Front1, D-Front) }.
capped_dist([], [], _, DF, DF).
capped_dist([L|Ls], [P|Ps], ток, D1-Front1, DF):- абсдифф (L, P, D2),
D3 #= D1 + D2, ток = D0-_,
( D3 #> D0 -> DF = Current; capped_dist(Ls, Ps, Current, D3-Front1, DF)). Я не могу заставить себя принять мерзость и примитивность современных чисел с плавающей точкой, поэтому я сохранил целочисленную арифметику и просто умножил все показанные вами числа, чтобы они стали целыми числами:
? - list_subseq_min ([21,34,40,11,20,40,100,120,150], [10,20,30], D). D = 11
Я оставляю это расширение, чтобы оно также показывало найденную подпоследовательность как простое упражнение.
Одно важное замечание: ограничение влияет только на расчет расстояния; обратите внимание, в частности, что время работы составляет Θ(N×M) из-за способа same_length_prefix/3 используется в front//2! Я оставляю улучшение этого упражнения немного сложнее.