最大独立集合在Prolog中

本文介绍了最大独立集合在Prolog中的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我试图实现一个获取二叉树的Prolog谓词（表示为t（Left，Root，Right）），并返回一个列表，该列表是该树的最大独立集（MIS）及其大小。
我首先明白MIS（T）是具有root的MIS和没有root的MIS之间的最大值。
然后，我使用了两个定理，指出具有根的MIS是所有子树的没有根的MIS的统一，没有根的MIS是所有子树的MIS的统一。

 ％mis是查找二叉树中最大独立集（MIS）的谓词。 
％它有三个参数：一个是输入 - 一个二叉树T  - 另外两个是输出 - 列表是最大独立树T中的元素列表，其中N是元素的数量这套。 
 mis（Tree，List2，N）： -  
 mis_no_root（Tree，List1，N1），％find没有root 
 mis_with_root（Tree，List2，N2） 
 max_set（List1，N1，List2，N2，List，N）。 ％选择更大的节点集合
 
％这是一个帮助谓词，分别获得长度为N1和N2的列表List1和List2，并将List实例化为更大的列表，其中N的大小为
 max_set（List1，N1，_，N2，List，N）： -  
 N1> = N2，如果N1大于或等于
 List = List1，％则max set为List1 
 N = N1。如果N2更大，$％b 
 
 max_set（_，N1，List2，N2，List，N）： -  
 N2> N1，％％
 List = List2，％那么最大集合是List2 
 N = N2。长度的百分比N2 
 
％帮助谓词找到t（L，_，R）的最大独立集合，排除根
 mis_no_root（nil，[]，0）。 ％空子树有一个空的最大独立集，大小为0 
 
 mis_no_root（t（L，_，R），List，N）： -  
 mis（L，LeftList，LeftN） ，％计算左子树的错误
 mis（R，RightList，RightN），％计算右子树的错误
 conc（LeftList，RightList，List），％根据给定公式计算节点连接列表统一所有的子树）
 N是LeftN + RightN。 ％并且用连接的独立集的累积大小赋值N，而不为根添加某些东西。 
 
％帮助谓词找到t（L，X，R）的最大独立集合，包括根
 mis_with_root（nil，[]，0）。 ％空子树有一个空的最大独立集，大小为0 
 
 mis_with_root（t（L，Root，R），[Root | List]，N）： -  
 mis_no_root（L， ％计算没有根的左子树的错误
 mis_no_root（R，RightList，RightN），％计算没有根的右子树的错误
 conc（LeftList，RightList，List），％连接列表根据给定的公式（所有子树的mis_no_root的统一）
 N是LeftN + RightN + 1.％，并且将连接的独立集合的累积大小赋值N，增加1（包括根）。

成功获取一组最大尺寸，但它不会继续搜索其他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).