在Prolog中强加事实

假设f(X)是一个动态事实，可以是assert ed和retract ed，并且假设X总是数字。现在，假设执行得最多的查询是关于找到f(X)这样的最小值。在SWI-Prolog的我可能会写：在Prolog中强加事实

min_f(R) :- aggregate(min(X), f(X), R).

但是，很显然，这总是导致Prolog的执行对所有事实线性搜索。现在，假设将有大量（例如1,000,000）这样的事实。因为我知道手我会经常执行min_f/1前：

我可以强加f/1排序，从而使发动机可以找到在O（1）最小？
我可以明确地指出assert一个包含所有事实的小堆，然后偷看它的头部;事实是否可以隐含地存储在最小堆中？

我对Prolog方言没有任何限制，所以任何替代的Prolog实现都可以。

来源

2015-10-14 Edoardo Vacchi

我建议你简单地使用SICStus，SWI等提供的'library（heap）'。保持一个明确的堆，你可以通过这个堆，并且你总是有O（1）访问权限。它还简化了代码的调试和推理，因为如果修改全局数据库，您不依赖于副作用和隐式状态。此外，它很可能*更快*。 – mat

我第二次由@mat推荐。一个逻辑变量通常比使用数据库和'assert'和'retract'更方便维护状态。对于你的用例，'图书馆（堆）'似乎是一个很好的匹配。即使只保留一个有序的值列表（有或没有重复）也是可以接受的选择：访问头是恒定时间，即使插入不是。 – 2015-10-14 09:48:14

我正在玩SWI-Prolog堆。显然，当它变得足够大时（〜100.000个条目），会使解释器发生段错误 –

:- dynamic(f/1). 

min_f(X) :- 
    f(X), 
    !. 
assert_f(X) :- 
    min_f(Min), 
    Min<X, 
    assertz(f(X)), 
    !. 
assert_f(X) :- 
    asserta(f(X)).

使用assert_f/1代替assert/1。 f/1的第一个解决方案总是最小值，但不要认为f/1的解决方案从低到高排列。

来源

2016-05-26 08:58:21 Zebollo

在Prolog中强加事实

回答

相关问题