序言集，堆棧溢出

我要顯示一些代碼並問，什麼可以優化，我在哪裏吸？序言集，堆棧溢出

sublist([], []). 
sublist([H | Tail1], [H | Tail2]) :- 
    sublist(Tail1, Tail2). 
sublist(H, [_ | Tail]) :- 
    sublist(H, Tail). 

less(X, X, _). 
less(X, Z, RelationList) :- 
    member([X,Z], RelationList). 
less(X, Z, RelationList) :- 
    member([X,Y], RelationList), 
    less(Y, Z, RelationList), 
    \+less(Z, X, RelationList). 

lessList(X, LessList, RelationList) :- 
    findall(Y, less(X, Y, RelationList), List), 
    list_to_set(List, L), 
    sort(L, LessList), !. 

list_mltpl(List1, List2, List) :- 
    findall(X, (
     member(X, List1), 
     member(X, List2)), 
    List). 

chain([_], _). 
chain([H,T | Tail], RelationList) :- 
    less(H, T, RelationList), 
    chain([T|Tail], RelationList), 
    !. 

have_inf(X1, X2, RelationList) :- 
    lessList(X1, X1_cone, RelationList), 
    lessList(X2, X2_cone, RelationList), 
    list_mltpl(X1_cone, X2_cone, Cone), 
    chain(Cone, RelationList), 
    !. 

relations(List, E) :- 
    findall([X1,X2], 
     (member(X1, E), 
     member(X2, E), 
     X1 =\= X2), 
    Relations), 
    sublist(List, Relations). 

semilattice(List, E) :- 
    forall(
     (member(X1, E), 
     member(X2, E), 
     X1 < X2), 
    have_inf(X1, X2, List) 
    ). 

main(E) :- 
    relations(X, E), 
    semilattice(X, E).

我想模擬N個元素的所有可能的圖形集。謂詞關係（列表，E）連接可能的圖表（列表）和輸入集合E的列表。然後我描述了semilattice謂詞來檢查關係列表中的某些屬性。

所以，我有。

1）半格/ 2工作快速，清晰

?- semilattice([[1,3],[2,4],[3,5],[4,5]],[1,2,3,4,5]). 
true. 

?- semilattice([[1,3],[1,4],[2,3],[2,4],[3,5],[4,5]],[1,2,3,4,5]). 
false.

2）關係/ 2的工作沒有得到很好的

?- findall(X, relations(X,[1,2,3,4]), List), length(List, Len), writeln(Len),fail. 
4096 
false. 

?- findall(X, relations(X,[1,2,3,4,5]), List), length(List, Len), writeln(Len),fail. 
ERROR: Out of global stack 
^ Exception: (11) setup_call_catcher_cleanup('$bags':'$new_findall_bag'(17852886), '$bags':fa_loop(_G263, user:relations(_G263, [1, 2, 3, 4|...]), 17852886, _G268, []), _G835, '$bags':'$destroy_findall_bag'(17852886)) ? abort 
% Execution Aborted

3）它們的混合尋找所有可能的半格不起作用在所有。

?- main([1,2]). 
ERROR: Out of local stack 
^ Exception: (15) setup_call_catcher_cleanup('$bags':'$new_findall_bag'(17852886), '$bags':fa_loop(_G41, user:less(1, _G41, [[1, 2], [2, 1]]), 17852886, _G52, []), _G4767764, '$bags':'$destroy_findall_bag'(17852886)) ?

來源

2011-02-14 ДМИТРИЙ МАЛИКОВ

一組節點上所有可能「關係」的低效生成是您問題的根源。 ** sublist/2 **將生成一個指數數量的解決方案，並不像寫尾部遞歸形式，因此它佔用了大量的堆棧空間。謂詞** less/3 **似乎效率低下，而不是尾遞歸形式（但是如果我理解它的目的應該是一個確定性謂詞，它可以用於此優化）。你在一組N個元素上討論圖，但**關係/ 2 **似乎旨在表示有向圖（二元圖）。那麼澄清一下？ – hardmath 2011-02-14 15:59:56

好，比郵寄答案這麼晚更糟糕的唯一的事情本來更快地發佈一個不正確的答案！而且我準備好幾次這樣做了。

，如果你糾正子表/ 3最後一句話，讓全高清讀取你應該沒問題：

sublist([], []). 
sublist([H | Tail1], [H | Tail2]) :- 
    sublist(Tail1, Tail2). 
sublist([_ | Tail1], Tail2) :- 
    sublist(Tail1, Tail2).

至於寫的東西到一個文件在第一遍，然後再讀它作爲第二回合返回，我的猜測是需要更多時間。謂詞將會剔除很多候選人。所以情況是，按照你的建議劃分事情會帶來兩個大問題（因爲關係/ 2會產生大的產出）。

也許改進的機會在於改進關係/ 2，以便它產生更少的輸出，比E×E的隨機子集減對角線更可能是半格的東西。在這方面撓頭，但我還沒有具體的建議。

來源

2011-03-18 00:08:35 hardmath

序言集，堆棧溢出

回答

相關問題