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 回答