наборы пролога, переполнение стека

Я покажу какой-нибудь код и спрошу, что можно оптимизировать и где я лажаю?

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 элементов. Отношения-предикаты (List, E) соединяют список возможных графов (List) и входной набор E. Затем я описываю semilattice предикат для проверки списка отношений на наличие некоторых свойств.

Итак, что у меня есть.

1) semilattice/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)) ?

algebra prolog
person ДМИТРИЙ МАЛИКОВ    schedule 14.02.2011    source источник
comment
Неэффективная генерация всех возможных отношений на наборе узлов — корень ваших проблем. sublist/2 будет генерировать экспоненциальное количество решений и не будет соответствовать форме хвостовой рекурсии, поэтому он использует много места в стеке. Предикат less/3 также кажется неэффективным и не в хвостовой рекурсивной форме (но, насколько я понимаю, его целью должен быть детерминированный предикат, который поддается этой оптимизации). Вы говорите о графах на наборе из N элементов, но relations/2, кажется, нацелен на представление ориентированных графов (орграфов). Итак, небольшое уточнение?   -  person hardmath    schedule 14.02.2011
comment
›Неэффективная генерация всех возможных отношений на наборе узлов является корнем ваших проблем. Если вы знаете лучший способ сделать это, скажите мне, пожалуйста, ›sublist/2 будет генерировать экспоненциальную число решений и не так, как написано в хвостовой рекурсивной форме, поэтому он использует много места в стеке. Да, для n точек его 2^(n^2-n) устанавливает less/3 в порядке, он создал все отношения с транзитивным свойством › Relations/2, кажется, нацелен на представление ориентированных графов Да, это то, что я хочу, потому что это проблема бинарных отношений ›Итак, немного разъяснение? Вовсе нет, но спасибо   -  person ДМИТРИЙ МАЛИКОВ    schedule 14.02.2011
comment
Спасибо, я имел в виду, что разъяснение было для меня, и вы его предоставили!   -  person hardmath    schedule 14.02.2011
comment
Возможно, лучшее решение — разделить эту большую проблему на 2 маленькие. Сначала сгенерируйте все возможные отношения и запишите их в файл. И второе - прочитать файл и проверить каждое отношение на полурешетчатость. Конечно, если весь этот код будет максимально быстрым   -  person ДМИТРИЙ МАЛИКОВ    schedule 14.02.2011

Ответы (1)


arrow_upward
2
arrow_downward

Ну, единственное, что может быть хуже, чем публиковать ответ так поздно, - это быстрее публиковать неправильный ответ! И я собирался сделать это несколько раз.

Все будет в порядке, если вы исправите последнее предложение в sublist/3, чтобы все определение читалось так:

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

Что касается записи данных в файл при первом проходе и последующего чтения во время второго прохода, я предполагаю, что это займет больше времени. Ваш предикат semilattice/2 отсеет множество кандидатов. Таким образом, ситуация такова, что разделение вещей, как вы предлагаете, создает две большие проблемы (поскольку relations/2 дает большой результат).

Возможно, возможность улучшения заключается в переработке relations/2 таким образом, чтобы он давал меньше выходных данных, которые, скорее всего, будут полурешетками, а не случайным подмножеством E x E за вычетом диагонали. Ломаю голову над этим, но конкретного предложения пока нет.

person hardmath    schedule 18.03.2011