一次性删除不正确的后续解决方案 [英] Remove incorrect subsequent solutions without once

问题描述

我有一个谓词可以找到正确的解决方案，但随后又找到了不正确的解决方案.

?- data(D),data_threshold_nonredundantbumps(D,5,Bs),write(D).[3,6,7,8,2,4,5,6,9,4,7,3]D = [3, 6, 7, 8, 2, 4, 5, 6, 9|...],Bs = [bump([11], [7])、bump([8, 9], [6, 9])、bump([2, 3, 4], [6, 7, 8])] ;[3,6,7,8,2,4,5,6,9,4,7,3]D = [3, 6, 7, 8, 2, 4, 5, 6, 9|...],Bs = [凹凸([8, 9], [6, 9]), 凹凸([2, 3, 4], [6, 7, 8])] ;[3,6,7,8,2,4,5,6,9,4,7,3]D = [3, 6, 7, 8, 2, 4, 5, 6, 9|...],Bs = [凹凸([8], [6]), 凹凸([2, 3, 4], [6, 7, 8])] ;[3,6,7,8,2,4,5,6,9,4,7,3]D = [3, 6, 7, 8, 2, 4, 5, 6, 9|...],Bs = [凹凸([9], [9]), 凹凸([2, 3, 4], [6, 7, 8])] ;[3,6,7,8,2,4,5,6,9,4,7,3]D = [3, 6, 7, 8, 2, 4, 5, 6, 9|...],Bs = [凹凸([11], [7]), 凹凸([2, 3, 4], [6, 7, 8])] ;[3,6,7,8,2,4,5,6,9,4,7,3]D = [3, 6, 7, 8, 2, 4, 5, 6, 9|...],Bs = [bump([2, 3, 4], [6, 7, 8])] ;

等

的想法是，它会找到数据中所有非冗余的bump，其中一个bump是data的一个连续子列表，它高于threshold，返回一个有序的(按大小)bump/2s 列表，其中bump/2 的第一个arg 是来自数据的索引列表，第二个arg 是值列表.所以 bump([2, 3, 4], [6, 7, 8]) 表示在数据索引 2,3 和 4 大于 5 时，它们是 6,7,8.

如何添加条件以便找不到这些额外的解决方案?- 不使用 once/1.

如果我的代码可以通过其他方式简化，请告诉我.它试图做的事情似乎有点复杂.

所以:

这是我的代码:

:-use_module(library(clpfd)).fd_length(L, N) :-N#＞＝0，fd_length(L, N, 0).fd_length([], N, N0) :-N#=N0.fd_length([_|L], N, N0) :-N1是N0+1，N#＞＝N1，fd_length(L, N, N1).equidistant_stride([],_).equidistant_stride([Z|Zs],D) :-foldl(equidistant_stride_(D),Zs,Z,_).equidistant_stride_(D,Z1,Z0,Z1) :-Z1 #= Z0+D.Continuous_ascending_integers(Zs) :-equidistant_stride(Zs,1).continuous_ascending_integers_from(Zs,Z0) :-Zs = [Z0|_],Continuous_ascending_integers(Zs).bool01_t(1,true).bool01_t(0,false).if_(C_1,Then_0,Else_0) -->{电话(C_1，真相)}，{ functor(Truth,_,0) }, % 安全检查( { Truth == true } -> 短语(Then_0);{ 真相 == 错误 }，短语(Else_0)).if_(If_1, Then_0, Else_0) :-呼叫(If_1，T)，( T == true -> call(Then_0);T == 假 ->呼叫(Else_0);nonvar(T) ->抛出(错误(类型错误(布尔，T)，_));/* var(T) */throw(error(instantiation_error,_))).#=<(X,Y,Truth) :- X #=<是#<==>B, bool01_t(B,Truth).#<(X,Y,Truth) :- X #<是#<==>B, bool01_t(B,Truth).#>(X,Y,Truth) :- X #>是#<==>B, bool01_t(B,Truth).#>=(X,Y,Truth) :- X #>= Y #<==>B, bool01_t(B,Truth).tinclude(P_2,Xs,Zs) :-list_tinclude_list(Xs,P_2,Zs).list_tinclude_list([], _P_2,[]).list_tinclude_list([i_v(E0,E1)|Es],P_2,Fs0) :-if_(call(P_2,E1), Fs0 = [i_v(E0,E1)|Fs], Fs0 = Fs),list_tinclude_list(Es,P_2,Fs).tfilter(P_2,As,Bs) :-tinclude(P_2,As,Bs).%% ======================================================================%% ======================================================================数据([5,6,7,8,3,2,6,7]).list_index_element(L,I,E):-nth1(I,L,E).过滤器(阈值，数据对，过滤器对):-tfilter(#<(阈值),DataPairs,FilterdPairs).i_v_pair(I,V,i_v(I,V)).data_indices_indicespairs(D,Is,Pairs):-same_length(D,Is),continuous_ascending_integers_from(Is,1),地图列表(i_v_pair，Is，D，Pairs).list_ascending(List,MinLength,MaxLength):-MinLength 中的最大值..MaxLength，标签([最大(最大)]，[最大])，fd_length(List,Max),连续_升序_整数(列表).region_minlength_maxlength(Region,MinLength,MaxLength,All):-list_ascending(Region,MinLength,MaxLength),追加(_Before,End,All),追加(区域，_End2，End).data_threshold_bumpvalues_bumplocation(Data,Threshold,Bumpvalues,Bumplocation):-长度(数据，MaxBump)，data_indices_indicespairs(Data,_Is,Pairs),过滤器(阈值，对，过滤对)，地图列表(i_v_pair，FilteredIndices，_FilteredValues，FilteredPairs)，%Test =test(FilteredIndexes,FilteredValues),差异(凹凸定位，[])，region_minlength_maxlength(Bumplocation,0,MaxBump,FilteredIndices),地图列表(列表索引元素(数据)，凹凸定位，凹凸值).list_first_last([H|T],H,L):-最后(T，L).listoflists_firsts_lasts(Listoflists,Firsts,Lasts):-地图列表(list_first_last，Listoflists，Firsts，Lasts).%start 不在 location1 和 location2 之间start_location1_location2(Start,Location1,Location2) :-#\( Location1 #=< 开始，开始#=<位置 2).bumplocation_notsublist_of_any_acs(Bumplocation,Acs):-listoflists_firsts_lasts(Acs,Firsts,Lasts),%bumplocation 的开始不能在任何 Acs 的开始之间Bumplocation =[Bumpstart|_],maplist(start_location1_location2(Bumpstart),Firsts,Lasts).loc_val_bump(Location,Value,bump(Location,Value)).data_bumplocations_bumpvalues(Data,Bumplocations,Bumpvalues):-maplist(list_index_element(Data),Bumplocations,Bumpvalues).%this 有效，但会发现额外的溶质，因此需要改进.data_threshold_nonredundantbumps(Data,Threshold,Bumps):-data_threshold_nonredundantbumps_ac(Data,Threshold,Nonredundantbumpslocations,[]),maplist(data_bumplocations_bumpvalues(Data),Nonredundantbumpslocations,Nonredundantbumps),地图列表(loc_val_bump，Nonredundantbumpslocations，Nonredundantbumps，Bumps).data_threshold_nonredundantbumps_ac(Data,Threshold,Nonredundantbumps,Ac0):-bumplocation_notsublist_of_any_acs(Bumplocation,Ac0),data_threshold_bumpvalues_bumplocation(Data,Threshold,_Bumpvalues,Bumplocation),追加([凹凸定位]，Ac0，Ac1)，data_threshold_nonredundantbumps_ac(Data,Threshold,Nonredundantbumps,Ac1).data_threshold_nonredundantbumps_ac(_Data,_Threshold,Ac0,Ac0).

解决方案

我的印象是你有点想多了.对于运行超过阈值的数字有一个直接的公式，可以通过在列表的单次遍历中考虑从头到尾的元素来定义.特别是，我们不需要需要append/3来做到这一点.

始终考虑使用 DCG 符号(dcg) 在 Prolog 中描述 lists 时.在这种情况下，需要考虑一下来决定如何最好地应用 DCG，因为我们描述了两个列表:

• 运行列表(超过阈值的连续元素)
• 在运行中，索引和值的列表.

然而，除了一些技巧和扩展之外，DCG 本质上只能让我们描述单个列表，而不是同时描述单独的列表.因此，我们拥有这种强大且可能非常合适的机制供我们使用，并且必须选择我们要主要将它应用于哪种列表.

在下面，我展示了一个使用 DCG 来描述 bump/1 术语列表的解决方案，即我专门"使用机制来描述上面提到的第一种列表，并使用另一个 DCG 来描述 第二种 类型的列表，我通过 phrase/2 从第一个 DCG 中调用它.

data_threshold_bumps(Ds, T, Bs) :-短语(颠簸(Ds，1，T)，Bs).颠簸([], _, _) -->[].颠簸([D|Ds0], I0, T) -->{ D #>,短语(凹凸(D，T，Ds0，Ds，I0，I)，Bs)}，[凹凸(Bs)],颠簸(Ds，I，T).颠簸([D|Ds0], I0, T) -->{ D #=<,我#= I0 + 1 },颠簸(Ds0，I，T).凹凸(D，T，Ds0，Ds，I0，I)->[I0-D],{ I1 #= I0 + 1 },运行(Ds0，Ds，T，I1，I).运行([], [], _, I, I) -->[].运行([D|Ds0], Ds, T, I0, I) -->[I0-D],{ D #>,I1 #= I0 + 1 },运行(Ds0，Ds，T，I1，I).run([D|Ds0], [D|Ds0], T, I, I) -->{ D #=

示例查询和回答:

<预>?- data_threshold_bumps([3,6,7,8,2,4,5,6,9,4,7,3], 5, Bs).Bs = [凹凸([2-6, 3-7, 4-8]), 凹凸([8-6, 9-9]), 凹凸([11-7])];错误的.

请注意，这与完全不是您需要的完全相同的数据表示形式，但是将其转换为那种 很简单.

以下是改进此解决方案的一些想法，从易到难:

• 使用 if_/3 去除不必要的选择点.
• 在上面的代码中对 bumps//3 和 run//5 使用 DCG 表示法实际上有意义吗?与常规谓词相比，在此处使用 DCG 有哪些优点和缺点?
• 以不同的视角看待问题:你能扭转 DCG 视角吗?例如，如何使用 DCG 而不是颠簸来描述实际数据?
• 追踪您发布的代码中不需要的解决方案的来源.

顺便说一下，要否定(具体化的)CLP(FD) 约束，您需要使用 (#/\)/2 来表示连词.它不能与 (,)/2 一起使用.

I have a predicate that finds the correct solution but then goes on to find solutions which are not right.

?- data(D),data_threshold_nonredundantbumps(D,5,Bs),write(D).
[3,6,7,8,2,4,5,6,9,4,7,3]
D = [3, 6, 7, 8, 2, 4, 5, 6, 9|...],
Bs = [bump([11], [7]), bump([8, 9], [6, 9]), bump([2, 3, 4], [6, 7, 8])] ;
[3,6,7,8,2,4,5,6,9,4,7,3]
D = [3, 6, 7, 8, 2, 4, 5, 6, 9|...],
Bs = [bump([8, 9], [6, 9]), bump([2, 3, 4], [6, 7, 8])] ;
[3,6,7,8,2,4,5,6,9,4,7,3]
D = [3, 6, 7, 8, 2, 4, 5, 6, 9|...],
Bs = [bump([8], [6]), bump([2, 3, 4], [6, 7, 8])] ;
[3,6,7,8,2,4,5,6,9,4,7,3]
D = [3, 6, 7, 8, 2, 4, 5, 6, 9|...],
Bs = [bump([9], [9]), bump([2, 3, 4], [6, 7, 8])] ;
[3,6,7,8,2,4,5,6,9,4,7,3]
D = [3, 6, 7, 8, 2, 4, 5, 6, 9|...],
Bs = [bump([11], [7]), bump([2, 3, 4], [6, 7, 8])] ;
[3,6,7,8,2,4,5,6,9,4,7,3]
D = [3, 6, 7, 8, 2, 4, 5, 6, 9|...],
Bs = [bump([2, 3, 4], [6, 7, 8])] ;

etc

The idea is that it will find all the nonredundant bumps in the data, where a bump is a consecutive sublist of data that is above threshold, Returning an ordered (by size) list of bump/2s where the first arg of bump/2 is a list of indicies from data and the second arg is the list of values. So bump([2, 3, 4], [6, 7, 8]) means that in data indices 2,3 and 4 are above 5, they are 6,7,8.

How do I add conditions so that these extra solutions are not found? -Without using once/1.

If my code could be streamlined in other ways please let me know. It seems a little complicated for what it is trying to do.

So:

Here is my code:

:-use_module(library(clpfd)).

fd_length(L, N) :-
 N #>= 0,
 fd_length(L, N, 0).

fd_length([], N, N0) :-
 N #= N0.
fd_length([_|L], N, N0) :-
 N1 is N0+1,
 N #>= N1,
 fd_length(L, N, N1).

equidistant_stride([],_).
equidistant_stride([Z|Zs],D) :-
 foldl(equidistant_stride_(D),Zs,Z,_).

equidistant_stride_(D,Z1,Z0,Z1) :-
 Z1 #= Z0+D.

consecutive_ascending_integers(Zs) :-
 equidistant_stride(Zs,1).

consecutive_ascending_integers_from(Zs,Z0) :-
 Zs = [Z0|_],
 consecutive_ascending_integers(Zs).

bool01_t(1,true).
bool01_t(0,false).

if_(C_1,Then_0,Else_0) -->
 { call(C_1,Truth) },
 { functor(Truth,_,0) },  % safety check
 (  { Truth == true }  -> phrase(Then_0)
 ;  { Truth == false },   phrase(Else_0)
 ).

if_(If_1, Then_0, Else_0) :-
 call(If_1, T),
 (  T == true -> call(Then_0)
 ;  T == false -> call(Else_0)
 ;  nonvar(T) -> throw(error(type_error(boolean,T),_))
 ;  /* var(T) */ throw(error(instantiation_error,_))
 ).


 #=<(X,Y,Truth) :- X #=< Y #<==> B, bool01_t(B,Truth).

 #<( X,Y,Truth) :- X #<  Y #<==> B, bool01_t(B,Truth).

 #>( X,Y,Truth) :- X #>  Y #<==> B, bool01_t(B,Truth).

 #>=(X,Y,Truth) :- X #>= Y #<==> B, bool01_t(B,Truth).

tinclude(P_2,Xs,Zs) :-
 list_tinclude_list(Xs,P_2,Zs).

list_tinclude_list([],   _P_2,[]).
list_tinclude_list([i_v(E0,E1)|Es],P_2,Fs0) :-
 if_(call(P_2,E1), Fs0 = [i_v(E0,E1)|Fs], Fs0 = Fs),
 list_tinclude_list(Es,P_2,Fs).


tfilter(P_2,As,Bs) :-
 tinclude(P_2,As,Bs).

%% =====================================================================
%% =====================================================================

data([5,6,7,8,3,2,6,7]).

list_index_element(L,I,E):-
 nth1(I,L,E).  

filter(Threshold,DataPairs,FilterdPairs):-
 tfilter(#<(Threshold),DataPairs,FilterdPairs).

i_v_pair(I,V,i_v(I,V)).

data_indices_indicespairs(D,Is,Pairs):-
 same_length(D,Is),
 consecutive_ascending_integers_from(Is,1),
 maplist(i_v_pair,Is,D,Pairs).

list_ascending(List,MinLength,MaxLength):-
 Max in MinLength..MaxLength,
 labeling([max(Max)],[Max]),
 fd_length(List,Max),
 consecutive_ascending_integers(List).

region_minlength_maxlength(Region,MinLength,MaxLength,All):-
 list_ascending(Region,MinLength,MaxLength),
 append(_Before,End,All),
 append(Region,_End2,End).

data_threshold_bumpvalues_bumplocation(Data,Threshold,Bumpvalues,Bumplocation):-
 length(Data,MaxBump),
 data_indices_indicespairs(Data,_Is,Pairs),
 filter(Threshold,Pairs,FilteredPairs),
 maplist(i_v_pair,FilteredIndices,_FilteredValues,FilteredPairs),
 %Test =test(FilteredIndexes,FilteredValues),
 dif(Bumplocation,[]),
 region_minlength_maxlength(Bumplocation,0,MaxBump,FilteredIndices),
 maplist(list_index_element(Data), Bumplocation,Bumpvalues).


list_first_last([H|T],H,L):-
 last(T,L).

listoflists_firsts_lasts(Listoflists,Firsts,Lasts):-
 maplist(list_first_last,Listoflists,Firsts,Lasts).

%start is not between location1 and location2
start_location1_location2(Start,Location1,Location2) :-
 #\(   Location1 #=< Start,
 Start #=< Location2).

bumplocation_notsublist_of_any_acs(Bumplocation,Acs):-
 listoflists_firsts_lasts(Acs,Firsts,Lasts),
 %the start of bumplocation can not be between the start of any Acs
 Bumplocation =[Bumpstart|_],
 maplist(start_location1_location2(Bumpstart),Firsts,Lasts).


loc_val_bump(Location,Value,bump(Location,Value)).

data_bumplocations_bumpvalues(Data,Bumplocations,Bumpvalues):-
 maplist(list_index_element(Data),Bumplocations,Bumpvalues).

%this works but finds extra solutins so needs to be refined.
data_threshold_nonredundantbumps(Data,Threshold,Bumps):-
 data_threshold_nonredundantbumps_ac(Data,Threshold,Nonredundantbumpslocations,[]),
 maplist(data_bumplocations_bumpvalues(Data),Nonredundantbumpslocations,Nonredundantbumps),
 maplist(loc_val_bump,Nonredundantbumpslocations,Nonredundantbumps,Bumps).

data_threshold_nonredundantbumps_ac(Data,Threshold,Nonredundantbumps,Ac0):-
 bumplocation_notsublist_of_any_acs(Bumplocation,Ac0),
 data_threshold_bumpvalues_bumplocation(Data,Threshold,_Bumpvalues,Bumplocation),
 append([Bumplocation],Ac0,Ac1),
 data_threshold_nonredundantbumps_ac(Data,Threshold,Nonredundantbumps,Ac1).

data_threshold_nonredundantbumps_ac(_Data,_Threshold,Ac0,Ac0).

解决方案

My impression is that you are overthinking this slightly. There is a straight-forward formulation for runs of numbers that exceed the threshold, which can be defined by considering the elements from first to last in a single traversal of the list. In particular, we do not need append/3 to do this.

Always consider using DCG notation (dcg) when describing lists in Prolog. In this case, it takes a moment of reflection to decide how to best apply DCGs, because we are describing two lists:

• lists of runs (successive elements exceeding the threshold)
• within runs, lists of indices and values.

However, excepting a few tricks and extensions, a DCG essentially only lets us describe a single list, not separate lists at the same time. So, we have this powerful and likely very suitable mechanism at our disposal, and must choose for which kind of list we want to apply it primarily.

In the following, I show a solution that uses a DCG to describe a list of bump/1 terms, that is, I "dedicate" the mechanism to describe the first kind of lists mentioned above, and use another DCG to describe the second kind of list, which I invoke via phrase/2 from within the first DCG.

data_threshold_bumps(Ds, T, Bs) :-
        phrase(bumps(Ds, 1, T), Bs).

bumps([], _, _) --> [].
bumps([D|Ds0], I0, T) -->
        { D #> T,
          phrase(bump(D, T, Ds0, Ds, I0, I), Bs) },
        [bump(Bs)],
        bumps(Ds, I, T).
bumps([D|Ds0], I0, T) -->
        { D #=< T,
          I #= I0 + 1 },
        bumps(Ds0, I, T).


bump(D, T, Ds0, Ds, I0, I) --> [I0-D],
        { I1 #= I0 + 1 },
        run(Ds0, Ds, T, I1, I).

run([], [], _, I, I) --> [].
run([D|Ds0], Ds, T, I0, I) --> [I0-D],
        { D #> T,
          I1 #= I0 + 1 },
        run(Ds0, Ds, T, I1, I).
run([D|Ds0], [D|Ds0], T, I, I) -->
        { D #=< T }.

Example query and answer:

?- data_threshold_bumps([3,6,7,8,2,4,5,6,9,4,7,3], 5, Bs).
Bs = [bump([2-6, 3-7, 4-8]), bump([8-6, 9-9]), bump([11-7])] ;
false.

Note that this is not quite the exact same data representation that you need, but it is trivial to convert it to that one.

Here are a few ideas to improve upon this solution, from easier to harder:

• Get rid of unnecessary choice-points, using if_/3.
• Does it actually make sense to use DCG notation for bumps//3 and run//5 in the code above? What are the benefits and drawbacks of using DCGs here over regular predicates?
• Play with different views of the problem: Can you turn the DCG view around? For example, what about describing the actual data with a DCG, instead of the bumps?
• Track down the origin(s) of unwanted solutions in the code you posted.

By the way, to negate a (reifiable) CLP(FD) constraint, you need to use (#/\)/2 to denote a conjunction. It does not work with (,)/2.

这篇关于一次性删除不正确的后续解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！