PrologのMax Independent Set

Question

私は、バイナリツリー（t（Left、Root、Right）で表される）を取得し、このツリーのMaximal Independent Set（MIS）であるリストを返すProlog述語を実装しようとしています。そのサイズ。 私は最初にMIS（T）がルートを持つMISとルートのないMISの間の最大値であることを理解しました。 次に、2つの定理を使用して、ルートを持つ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

迷惑な問題があったときに怒らないでください！ 2番目のmax_set（N2> = N1）に=を追加するだけです。 :)