在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中強加事實

回答

相關問題