2

我有一个序言谓词:

Add( [A|B] , Answer ) :-
    ...
    ~ Add everything in the list to come up with answer
    ...

我现在想实现AddUnique它将为列表中的所有内容返回唯一值,除非我给它两次变量。


以下是逻辑上等价的内容:

?- AddUnique([A, B, C], 10).相当于:?- Add([A, B, C], 10), A != B, B != C, A != C.

和:

?- AddUnique([A, B, B], 10).相当于:?- Add([A, B, B], 10), A != B.

还:

?- AddUnique([A, B, B], 10).等于?- Add([A, B, B], 10), A != B, B!=B.


如果?- AddUnique([A,B,C,D], 4).给出它应该返回 false,因为它不能带有加到四的唯一正整数。

如果?- AddUnique([A,A,A,A], 4).给出它应该返回A=1


问题:如何A != B, B != C, A != C.在不执行此类操作的情况下移动谓词内的逻辑A != A

4

3 回答 3

1

Khm...你应该明白那个doStuff(A,B,C,D)doStuff(A,A,B,B)意思。首先是将价值观A..D与适当的价值观统一起来,从而实现doStuff/4目标。第二个等于A=B, C=D, doStuff(A,B,C,D)doStuff(A,B,C,D), A=B, C=D(但最后一个变体可能会导致回溯)。所以我希望你明白这unique/1不应该在内部进行doStuff/4,因为它是外部限制。所以你应该使用doStuff(A,B,C,D), unique([A,B,C,D])and doStuff(A,A,B,B), unique([A,B])

我想知道你是怎么阅读A is not B的......无论如何你可以定义unique/1

not_unique([H|T]):- member(H, T) ; not_unique(T).
unique(L):- not(not_unique(L)).
于 2010-06-06T13:22:07.463 回答
1

鉴于您对 addUnique/2谓词的描述,可以使用约束逻辑编程来实现解决方案。这远非初学者的东西,但无论如何我都会发布一个解释。

首先,查找什么是约束逻辑编程以及如何使用实现(例如,SWI-PL clpfd)可能是值得的。基本上,约束逻辑编程(特别是有限域求解器)将允许您对输入列表中的变量指定以下约束addUnique/2

  1. 输入列表中的变量如何绑定到某些数值(即从 0 到并包括指定值的整数)
  2. 输入列表上的不同变量如何不能同时绑定到相同的值(即!= 不同的地方)
  3. 输入列表中的变量之和加上任何数字必须加起来为指定值(即,变量可以在上面的 1 中取的最大值)。

总之,这些规范将允许基础约束求解器自动确定在给定上述约束的情况下变量可以同时采用的允许值,从而为您提供解决方案(可能有几个、一个或没有)。

这是在 SWI-PROLOG(clpfd 求解器)中使用上述约束求解器的解决方案:

:- use_module(library(clpfd)).  % import and use the constraint solver library

addUnique([A|As], Val) :-
    unique_vars([A|As], UVs),  % determine all unique variables
    UVs ins 0..Val,            % (1) domain of all unique variables is 0 to Val
    pairwise_inequ(UVs),       % (2) all unique variables are pairwise !=
    construct_sum_constr(As, Val, A, Program),  % (3) construct the sum constraint
    Program,              % assert the sum constraint
    label(UVs).           % label domains to enumerate a solution (backtracks)

% predicate to return a list of unique vars, if present
unique_vars([], []).
unique_vars([V|Vs], [V|Uniq]) :-
    var(V),
    \+ var_memberchk(V, Vs), !,
    unique_vars(Vs, Uniq).
unique_vars([_|Vs], Uniq) :-
    unique_vars(Vs, Uniq).

% predicate to test if a variable appears in a list (possibly including variables)
var_memberchk(V0, [V1|_]) :- 
    V0 == V1, !.
var_memberchk(V0, [_|V1s]) :- 
    var_memberchk(V0, V1s).

% create constraints that assert each in the input list != to each other
pairwise_inequ([]).
pairwise_inequ([V|Vs]) :-
    map_inequ(Vs, V),
    pairwise_inequ(Vs).

% predicate to pairwise assert inequality between all list members
map_inequ([], _).
map_inequ([V1|V1s], V0) :-
    V0 #\= V1,   % the inequality constraint
    map_inequ(V1s, V0).

% predicate to construct a summation constraint, whereby all variables in the 
% input list are constructed into a sum with +/2 and finally equated to a value
construct_sum_constr([], Val, Sum, (Sum #= Val)).
construct_sum_constr([V|Vs], Val, Sum, Program) :-
    construct_sum_constr(Vs, Val, (V + Sum), Program).

运行此代码,例如,为您提供:

?- addUnique([A,B,B], 6).
A = 0,
B = 3 ;
A = 4,
B = 1 ;
A = 6,
B = 0.

;枚举变量之间允许绑定的下一个解决方案。请注意,A并且B永远不要根据需要采用相同的值,但输入列表中的所有匹配项总和为6。另一个查询:

 ?- addUnique([A,A,A],4).
false.

这里的结果是失败,因为没有找到单个整数可以绑定到A该整数上,总计时,totaled 4,而:

 ?- addUnique([A,A,A,A],4).
A = 1.

...正如预期的那样。另外,您想尝试:

?- addUnique([A,B,C,D],4).
false.

同样,这里的结果是失败,因为所有变量、A和都被断言为不同的,并且不能都绑定到。BCD1

编辑附言。ony 也想试试:

?- addUnique([A,A,A,1],4).
A = 1.

对上面代码的简单修改可确保在调用断言域时仅使用变量ins(而不是输入列表中的任何数字)。

于 2010-06-08T00:03:41.007 回答
-1

这是我想出的解决方案。它只会将输入分配为小于十的数字,但效果很好!

addUnique( A, Answer ) :- 
    used(A,[0,1,2,3,4,5,6,7,8,9],_),
    add(A,Answer).

add( [A|B] , Answer ) :-
    ~ Add everything in the list to come up with answer ~.


% ================================
% Ensures that all variables are unique.  
% ================================

% Base case: Assigned variables unique values
used([], Nin, Nin).

% Have already assigned a value to this variable
used([A|B], Nin, Nout) :-
        integer(A),
        helper(B,Nin,Nout).

% Have not assigned a value to this variable yet
% Assign it and remove it from the list.  
used( [A|B] , Nin, Nout) :-
        member(A,Nin),
        delete(Nin,A,Temp),
        helper(B,Temp,Nout).
于 2010-06-08T18:54:17.273 回答