长序列和短序列之间的距离是短序列与长序列的任何与短序列长度相同的子序列之间的最小距离。
我使用的距离是我认为的曼哈顿距离。（但这应该不重要，因为我希望能够改变距离函数）。
第一个版本展示了一个简单的实现，没有提前放弃。我生成所有相同长度的子序列，映射它们以找到它们与短序列之间的距离，然后使用 aggregate/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].
但我需要以一种有效的方式做到这一点。
更新- 感谢 Mat 的回答，我现在有了这个，我认为这是一个很大的改进。谁能看到对此的进一步改进？我有一个双嵌套 -> 结构和一个！在 accumulate_dis/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].