長いシーケンスと短いシーケンスの間の距離は、短いシーケンスと短いシーケンスと同じ長さの長いシーケンスの任意のサブシーケンスとの間の最小距離です。
私が使用している距離は、マンハッタン距離だと思います。（ただし、距離関数を変更できるようにしたいので、これは重要ではありません）。
この最初のバージョンは、早期放棄のない素朴な実装を示しています。同じ長さのすべてのサブシーケンスを生成し、これらをマップしてそれらと短いシーケンスの間の距離を見つけ、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]
しかし、これではアサートとリトラクトを使用しているので、同じアルゴリズムを実行するバージョンが必要ですが、これらはありません。セミコンテキスト表記の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 からの回答のおかげで、私はこれを手に入れました。これは大きな改善だと思います。誰でもこれに対するさらなる改善を見ることができますか? 私は二重にネストされた -> 構造と ! accumate_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].