1

嗨，对不起，我真的是 Prolog 的新手。假设我有一个事实列表，说 6 个事实，第一列数字代表个人 ID，第二列代表一个人的获胜次数。如果我想找到赢得最多的人，我会怎么做？

wins(1, 22).
wins(2, 24).
wins(3, 23).
wins(4, 20).
wins(5, 21).
wins(6, 19).

类似的东西？大声笑说实话，我真的不知道我在做什么

X = wins(_, Xs) 
Y = wins(_, Ys)
most wins(X) :- Xs > Ys
4

1 回答 1

2

获取该信息的方法不止一种。

most_wins(Id) :-
    wins(Id, W), \+ (wins(_, W1), W1 > W).

或者，如果您的 Prolog 有库（聚合）：-

most_wins(Id) :-
    aggregate(max(W, Id), wins(Id, W), max(_, Id)).

或者你可以使用setof /3

most_wins(Id) :-
    setof(N-Id, W^(wins(Id, W), N is -W), [_-Id|_]).

存在明显的速度/内存权衡：第一种方式是内存效率 O(1)，但时间复杂度为 O(N^2)，因为它扫描了 2 次候选集。第二个和第三个（我认为）实际上是等效的，在 SWI-prolog 中的当前实现下，都建立候选者列表（然后在空间中是 O(N)），然后及时选择元素 - O(N log N)。

如果候选人是事实，就选择第一个。

编辑另一种方式，从效率的角度来看更好，利用不可回溯的分配。只需扫描候选人，随时随地保持最大值。Plain Prolog 将需要 assert/retract 来执行这样的任务，这使得它相当低效。但是许多 Prologs 有更有效的方法来存储“全局”变量......

于 2013-03-03T16:34:54.773 回答