prolog 查找最小值查询

Question

如果我有以下格式的事实：

person(name,age).

如何编写查询以找到最年轻的人？

我试过使用递归，但我一直陷入无限循环。到目前为止，从我完成的所有阅读中，我发现我需要使用 ! 切割运算符。任何帮助将不胜感激。

Answer 1

您绝对不需要使用 cut 运算符。我很难想象这个解决方案会是什么样子。

最简单的方法是进行这样的查询：

youngest(person(Name,Age)) :-
  person(Name, Age),
  \+ (person(Name2,Age2), Name2 \= Name, Age2 < Age).

遗憾的是，这不是很有效，因为它可能必须为每个人搜索一次数据库，导致 O(N^2) 性能。但它为什么有效应该很清楚。

更快的解决方案是使用setof/3.

youngest(person(Name, Age)) :-
  setof(Age-Name, person(Name,Age), [Age-Name|_]).

我们依赖于对setof/3列表进行排序的事实，这将导致最年轻的人被移动到结果列表的开头以使其工作。它表现得更好，但它并没有那么清楚地阅读所有内容。

有一个标准库可以用来解决 SWI 的这类问题，但我不确定你是否在使用 SWI，我自己也没有使用过它，但你可以研究一下。它被称为聚合。

另一种方法是直接将数据库具体化findall/3，然后直接使用为此编写的谓词找到最小值。这样的解决方案可能看起来像这样：

youngest(Person) :-
  findall(person(Name,Age), person(Name,Age), [P1|Rest]),
  youngest(P1, Rest, Person).

youngest(Person, [], Person).
youngest(person(Name, Age), [person(N2,A2)|Rest], Person) :-
  Age < A2 -> youngest(person(Name, Age), Rest, Person)
            ; youngest(person(N2, A2),    Rest, Person).

然而，这似乎需要大量的工作，即使它可能会给你最好的性能（应该是线性时间）。