最大独立集合在Prolog中 [英] Max Independent Set in 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相同的尺寸。
在此先感谢您的帮助！ 解决方案

当您看到恼人的问题时，不要生气！只需在第二个max_set（N2> = N1）上加上=即可。 ：）

I am trying to implement a Prolog predicate that gets a binary tree (represented as t(Left, Root, Right)) and returns a list that is the Maximal Independent Set (MIS) of this tree, and its size. I first understood that MIS(T) is the maximum between the MIS with root and the MIS without the root. Then, I used two theorems, stating that the MIS with root is the unification of the MIS's without the root for all the subtrees, and that MIS without root is the unification of the MIS's of all the subtrees.

% 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).

It does succeed retrieving a set of maximal size, but it does NOT continue searching for other MIS's of the same size. Thanks in advance for any help!

解决方案

Don't get mad when you see what the annoying issue was! just add = on the second max_set (N2>=N1). :)

这篇关于最大独立集合在Prolog中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！