Макс независимый набор в прологе

Question

Я пытаюсь реализовать предикат Prolog, который получает двоичное дерево (представленное как t(Left, Root, Right)) и возвращает список, который является максимальным независимым набором (MIS) этого дерева, и его размер. Сначала я понял, что MIS(T) - это максимум между MIS с рутом и MIS без рута. Затем я использовал две теоремы, утверждая, что MIS с корнем является объединением MIS без корня для всех поддеревьев, а MIS без корня является объединением MIS всех поддеревьев.

% mis is a predicate for finding the Max Independent Set (MIS) in a binary tree. 
% It has three arguments: one is input - a binary tree T - and the other two are output - List which is a list of elements in the max independent set of tree T, with N being the number of elements in this set.
mis(Tree, List, N) :-
    mis_no_root(Tree, List1, N1),       % find mis without root
    mis_with_root(Tree, List2, N2), % find mis with root
    max_set(List1, N1, List2, N2, List, N). % choose the bigger set of nodes

% This is a helping predicate, that gets lists List1 and List2 of lengths N1 and N2 respectively, and instantiates List to be the bigger list, with N being its size
max_set(List1, N1, _, N2, List, N) :-
    N1>=N2,             % if N1 is bigger or equal
    List=List1,         % then max set is List1
    N=N1.               % of length N1

max_set(_, N1, List2, N2, List, N) :-
    N2>N1,              % if N2 is bigger
    List=List2,         % then max set is List2
    N=N2.               % of length N2

% a helping predicate to find the max independent set of t(L,_,R), excluding the root
mis_no_root(nil, [], 0).            % the empty subtree has an empty max independent set of size 0

mis_no_root(t(L,_,R), List, N) :-
    mis(L, LeftList, LeftN),        % calculate mis of left subtree 
    mis(R, RightList, RightN),      % calculate mis of right subtree
    conc(LeftList, RightList, List),        % concatenate lists of nodes according to the given formula (unification of all mis of subtrees)
    N is LeftN + RightN.        % and assign N with the accumulated size of the concatenated independent set, without adding something for the root.

% a helping predicate to find the max independent set of t(L,X,R), including the root
mis_with_root(nil, [], 0).          % the empty subtree has an empty max independent set of size 0

mis_with_root(t(L,Root,R), [Root|List], N) :-
    mis_no_root(L, LeftList, LeftN),    % calculate mis of left subtree without root
    mis_no_root(R, RightList, RightN),  % calculate mis of right subtree without root
    conc(LeftList, RightList, List),        % concatenate lists of nodes according to the given formula (unification of all mis_no_root of subtrees)
    N is LeftN + RightN + 1.        % and assign N with the accumulated size of the concatenated independent set, incremented by 1 (including the root).

Он успешно получает набор максимального размера, но не продолжает поиск других MIS того же размера. Заранее благодарю за любую помощь!

Answer 1

Не сердитесь, когда вы видите, что раздражает проблема! просто добавьте = на второй max_set (N2>=N1).:)