Prolog查询找到数据库中最大的元素？

如果我已经定义了Prolog数据库中的所有数字，例如dig(0), dig(1), ..., dig(9)。我能用Prolog返回最大的数字 - 在这种情况下是9？Prolog查询找到数据库中最大的元素？

我想是这样的：

?- dig(N), dig(M), N > M.

但只返回第一种可能性，而不是数量最多。

来源

2010-10-29 busdude

重复：http://stackoverflow.com/questions/1701693 – Kaarel 2010-10-29 19:10:12

的可能重复的[最大超时值的通过序言子句定义]（http://stackoverflow.com/questions/1701693/max-out-按照prolog-clause定义） – 2011-03-16 11:33:03

要找出你应该写一个适当的查询，最多也就是一个：

实例化的一个数字，数字
检查是否是最大的（即没有其他数字越大）

所以，你可能想要写的东西，如：

largest(N):- 
    dig(N), 
    not((
     dig(M), 
     M > N 
    )).

来源

2010-10-29 14:56:52 gusbro

这种方法有效，但复杂度很低，即O（n^2）。可以在O（n）中执行此查询。 – Kaarel 2010-10-29 19:06:44

在最短的解决方案可能是：

?- dig(Max), \+((dig(X), X > Max)).

概念上简单的解决方案可能是：

?- findall(X, dig(X), Digits), max_list(Digits, Max).

但检查出Max out of values defined by prolog clauses更多的解决方案，以更好和更坏的复杂性。

:- between(1, 12345, X), assert(dig(X)), fail ; true. 

:- time((findall(X, dig(X), Digits), max_list(Digits, Max))), 
     write('Findall max: '), write(Max), nl. 

:- time((dig(Max), \+((dig(X), X > Max)))), write('\\+ max: '), write(Max), nl.

在我5岁的笔记本电脑它清楚地表明，findall -version的速度要快得多，如果你有例如：

您可以通过查询该文件来测试这两种解决方案的速度您的数据库中的条目。

% 37,085 inferences, 0.05 CPU in 0.06 seconds (87% CPU, 741700 Lips) 
Findall max: 12345 
% 76,230,375 inferences, 60.94 CPU in 72.30 seconds (84% CPU, 1250909 Lips) 
\+ max: 12345

来源

2010-10-29 19:18:39 Kaarel

Prolog查询找到数据库中最大的元素？

回答

相关问题