序言集，堆栈溢出

我要显示一些代码并问，什么可以优化，我在哪里吸？序言集，堆栈溢出

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

序言集，堆栈溢出

回答

相关问题