prolog 查找最小值查询 [英] prolog find minimum value query

问题描述

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

If I have the facts in following format:

person(name,age).

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

How can I write a query to find the youngest person?

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

I have tried using recursion but I kept getting stuck in infinite loops. So far from all the reading I done I found out I need to use the ! cut operator. Any help would be very much appreciated.

推荐答案

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

You definitely do not need to use the cut operator. I'm hard-pressed to imagine what that solution would look like.

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

The simplest thing to do is to make a query of this sort:

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

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

This is regrettably not very efficient, since it may have to search the database once for each person, leading to O(N^2) performance. But it should be clear why it works.

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

A faster solution is to use setof/3.

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

我们依赖于 setof/3 将对列表进行排序的事实，这将导致最年轻的人被移动到结果列表的开头以使其工作.它的性能更好，但读起来不是那么清楚.

We're relying on the fact that setof/3 is going to sort the list and that this will result in the youngest person being moved to the start of the result list for this to work. It performs better, but it doesn't read all that clearly.

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

There is a standard library you can use to solve these sorts of problems with SWI, but I'm not sure if you're using SWI and I haven't used it myself, but you might look into it. It's called aggregate.

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

Another approach would be to materialize the database directly with findall/3 and then find the minimum directly with a predicate written just to do that. Such a solution would probably look something like this:

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).

然而，这似乎需要大量工作，即使它可能为您提供最佳性能(应该是线性时间).

However, this seems like a lot of work, even though it probably gives you the best performance (should be linear time).

这篇关于prolog 查找最小值查询的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！