3

これは私の問題です：

がアイテム間の距離を超えない制約 (は –匿名変数のリスト として実装されて いる) のサブリストでdistance(List, Nemptylist, SubList)/3あるかどうかをチェックするプロシージャを作成します。 が完全にインスタンス化されていると仮定します。数が有限である限り、重複した回答が許可されます。SublistListNNNemptylistNList

たとえば、N= 2 の場合:

?- distance( [a,t,d,r,a,n,c,b,c] , [_,_], [a,b,c] ).
true

?- distance( [m,a,t,d,r,b,c,t] , [_,_] , [a,b,c] ).
false

?- distance([a, t, d, r, a, n, c, b], [_, _], [a, b, c]).
false

?- distance([c, c, c, a, c, c, c], [_, _], [a]).
true.

この問題を解決しようと何時間も座っていて、最終的に上記の例が機能しましたが、いくつかのテストを実行して失敗しました。

今のところ私の解決策は次のとおりです。

distance( L1 , L2 , [X]   ) :-
  member(X,L1) .
distance( L1 , L2 , [H|T] ) :-
  distance(L1,L2,T) ,
  append(Y,Z,L2) ,
  T=[Hs|Ts] ,
  append([H],Y,W) ,
  append(W,[Hs],R) ,
  sublist(R,L1) .

prefix(X,L) :- append(X, _, L).

suffix(X,L) :- append(_, X, L).

sublist(X,L) :- suffix(S,L) , prefix(X,S) .

このテストを実行しようとすると:

distance( [r,a,n,c,b,c],[],X) .

ランタイム超過エラーが原因で失敗します。

何時間もデバッグしましたが、本当に疲れました。この恐ろしい任務を終わらせるのを手伝ってください。

4

2 に答える 2

3

以下は、不完全な定義から始まる段階的な解決策です。

distance_tentative(Xs, _Ys, Zs) :-
   phrase(( ..., seq(Zs), ... ), Xs).

... --> [] | [_], ... .

seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).

このソリューションは、サブストリングのみを記述し、サブシーケンスを記述しないため、特殊すぎます。サブシーケンスはむしろ次のとおりです。

subseq([]) --> [].
subseq([E|Es]) --> [E], subseq(Es).
subseq(Es) --> [_], subseq(Es).

ここで、中間の無関係な要素の数を制限したいと考えています。つまり、最後のルールの適用をこのリスト引数の長さに制限したいのですLN。

subseq_n([], _) --> [].
subseq_n([E|Es], LN) --> [E], subseq_n(Es, LN).
subseq_n(Es, [_|LN]) --> [_], subseq_n(Es, LN).

たぶん、最後のルールは次のように読むべきです。

subseq_n(Es, [E|LN]) --> [E], subseq_n(Es, LN).

問題文の翻訳に問題があると思います。いずれにせよ、これで次のようになりました。

distance(Xs, Ys, Zs) :-
   phrase(( ..., subseq_n(Zs, Ys), ... ), Xs).

多くの冗長な回答がありますが、これで問題ないとおっしゃいました。

最適化

...の最初の要素と最初の要素の開始の間には、多くの冗長性、つまりあいまいさが存在しsubseq_n//2ます。同様に、間subseq_n//2と...最後に。さらに、Zsが空の場合、単一の回答で十分です。簡単に

distance(_Xs, _Ys, []).
distance(Xs, Ys, [Z|Zs]) :-
   phrase( ( ..., [Z], rsubseq_n(Zs, Ys), ... ), Xs).

rsubseq_n([], _) --> [].
rsubseq_n([E|Es], Ys) --> [E], rsubseq_n(Es, Ys).
rsubseq_n([E|Es], [_|Ys]) --> [_], rsubseq_n([E|Es], Ys).

「距離リスト」はサブシーケンス内でのみ使用されることに注意してください。

このプログラムには、非常に有利な終了特性があります。

distance(A,B,C)terminates_if b(A).

したがって、述語を終了させるためには、最初の引数だけを知る必要があります。

N編集：距離が適用される場所について、問題の説明があいまいです：

...アイテム制約間の距離がN以下の場合...

これは、総編集距離が N を超えないこと、または連続する各ペア間の距離を意味する場合があります。したがって、連続する各ペア間の距離が次のように意味されていると仮定します。

distanceII(_Xs, _Ys, []).
distanceII(Xs, Ys, [Z|Zs]) :-
   phrase( ( ..., [Z], rsubseq_d(Zs, Ys), ... ), Xs).

rsubseq_d([], _) --> [].
rsubseq_d([E|Es],Max) -->
   maxseq(Max),
   [E],
   rsubseq_d(Es, Max).

maxseq(_) --> [].
maxseq([_|Es]) --> [_], maxseq(Es).
于 2014-06-14T08:23:03.273 に答える
2

あなたの実装には 2 つの大きな問題があると思います。

  1. NEmptyListListからの要素とからの要素をsublist(R, L1)ゴールに統合しています。からの連続する要素と統合されないため、将来のsublist目標は失敗する可能性があります。append を使用したい場合 (これで問題ありません)、毎回新しい長さのリストを作成する必要があります (以下を参照)。NEmptyListNListN

  2. からの同じ一意のシーケンスを使用して、からの異なるシーケンスを検証する場合SubListListがあります。これを実証するには、ソリューションでこれを試してください。

    ?- distance([a,a],[],[a,a,a,a,a,a]).
true ;
true ;
false.

ここに解決策があります：

distance(_, _, []).
distance(List, NEmpty, Sublist):-
    append(_, Right, List),   % The first element can be anywhere in the list
    distance2(Right, NEmpty, Sublist).

distance2([X|_], _, [X]).
distance2(List, NEmpty, [X|Sublist]):-
    length(NEmpty, N),
    between(0, N, N1),
    length(AtMostNEmpty, N1), % Make a different list each time of length <N
    append([X|AtMostNEmpty], Right, List),
    distance2(Right, NEmpty, Sublist).
于 2014-06-14T08:24:35.003 に答える