我正在尝试实现一个 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。提前感谢您的帮助!