2

いくつかのコードを示して、何が最適化できるのか、どこに問題があるのか​​を尋ねます。

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 要素のすべての可能なグラフ セットをモデル化しようとしています。述語 Relations(List, E) は、可能なグラフのリスト (List) と入力セット E を接続します。次に、いくつかのプロパティについて関係の List をチェックするセミラティス述語を記述します。

それで、私が持っているもの。

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)) ?
4

1 に答える 1

2

答えを投稿するのが遅すぎることよりも悪い唯一のことは、間違った答えをもっと早く投稿することです! そして、私はそれを数回やろうとしていました。

sublist/3の最後の節を修正して、定義全体を次のようにすれば問題ありません。

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

最初のパスでファイルに書き込んでから、2 番目のパスとして読み戻す場合は、もっと時間がかかると思います。あなたのsemilattice/2述語は、多くの候補をノックアウトします。したがって、あなたが提案したように物事を分割すると、2 つの大きな問題が生じるという状況です (関係/2が大きな出力を生成するため)。

おそらく、改善の機会は関係/2を作り直して、E x E から対角線を引いたランダムなサブセットよりも半格子である可能性が高いものを生成するようにすることです。頭を悩ませていますが、まだ具体的な提案はありません。

于 2011-03-18T00:08:35.667 に答える