1

我需要实现一个谓词：

leastUpper(L1,L2,L)

当 L 是多重集 L1 和 L2 的最小上界时，它将被满足。这意味着对于 L 中的每个元素 X/N，X 是至少出现在 L1 和 L2 集合之一中的原子，N 是 L1 和 L2 中 X 的最大索引。如果 X 没有出现在一个集合中，则它在该集合中的索引为 0。

例如：

leastUpper([],[a/1,b/2,c/3],L) will be satisfied when L=[a/1,b/2,c/3]

or leastupper([a/2,b/3,c/2],[b/3,c/4,d/1],L) is satisfied if L=[a/2,b/3,c/4,d/1].

我目前的想法是：对于L1中的每个元素X/N，检查元素X/_是否存在于L2中。如果存在，比较它们的索引得到最大的索引Nx，然后在L中添加X/Nx。同时删除L1和L2中的对应元素。继续这个过程直到L1结束。对于 L1 和 L2 中的其余元素，它们只出现在一组 L1 或 L2 中，只需将它们添加到 L 中即可。原始想法可以用以下谓词来说明：

check(X/N,L2) :- member(X/_,L2),compare(...),append(X/Nx,L),delete(X/_,L1,L2).

我不知道我的想法是否正确以及如何在Prolog中实现它。欢迎任何想法并非常感谢！

4

2 回答 2

2

我倾向于同意@mbratch。您直接通过了一个逻辑公式进入程序部分。我想出的答案要简单得多。关键是这句话：

对于 L 中的每个元素 X/N，X 是至少出现在 L1 和 L2 集合之一中的原子，N 是 X 在 L1 和 L2 中的最大索引。

您已经在这里有了逻辑定义。让我们简化一下：最小上界的元素是集合 L 的元素 X/N，使得 N 是集合中 X/N 的最大分母。这在 Prolog 中很容易表达：

leastUpper(X/N, L) :-
    member(X/N, L),
    \+ (member(X/M, L), M > N).

从字面上看，如果 X/N 在 L 中并且 L 中没有成员 X/M 使得 M 大于 N，则 X/N 是 L 的最小上界元素。

请注意，两个“多重集”的最小上界是两个列表的最小上界（列表和多重集之间的唯一区别是顺序的概念，这里不相关），并且两个列表的最小上界列表与一个列表的最小上限相同（两个列表连接）。惊喜！:) 您的谓词现在有两行：

leastUpper(L1, L2, L) :-
    append(L1, L2, Concatenated),
    setof(X, leastUpper(X, Concatenated), L).

这满足您的要求：

?- leastUpper([a/2, b/3, c/2], [b/3, c/4, d/1], L).
L = [a/2, b/3, c/4, d/1].

学习如何以声明式和逻辑方式思考是迄今为止学习 Prolog 最难的事情。

一些注意事项：

  • leastUpper/2是与 不同的谓词leastUpper/3。值得注意的是，前者是生成器，而后者不是。重命名它可能是明智的。
  • leastUpper/2不是特别有效：这种遍历是 O(N^2)。您可以轻松地将其替换为排序，然后进行线性扫描，并达到 O(N log N)。替换可能会长达 5-6 行，并且可能需要另一个辅助谓词，所以如果您关心这一点，请尝试自己实现它（这并不困难）。
于 2013-07-17T04:34:27.767 回答
0

我自己的解决方案：

larger(X,Y,N):- X>=Y, N=X.
larger(X,Y,N):- X<Y,N=Y.

remove([],X,[]) :- !.
remove([X|T],X,L1) :- remove(T,X,L1), !.
remove([H|T],X,[H|L1]) :- remove(T,X,L1).

check(X/N) :- atom(X), integer(N), N > 0.

least_Upper([],M2,M2):-!.
least_Upper(M1,[],M1):-!.

least_Upper([X/N1|R1],L2,[X/N|R]):-      
                  maplist(check[X/N1|R1]),maplist(check,L2),member(X/N2,L2), 
          larger(N1,N2,N), remove(L2, X/N2, L2R), least_Upper(R1,L2R,R),!.

least_Upper([X/N1|R1],L2,[X/N|R]):- maplist(check,[X/N1|R1]),maplist(check,L2),
                  \+member(X/_,L2), N=N1, least_Upper(R1,L2,R),!.
于 2013-07-18T13:01:19.497 回答