0

我正在尝试计算给定poset的最大反链。我创建了以下方法：

public boolean isIncomparable(Node a,Node b)
{
    if(isReachable(a,b)||isReachable(b,a))
         return false;
    return true;
}

当且仅当两个节点不可比较（即，没有 from atob 或 from bto的路径a）时，它才返回 true。

我定义了一个 LinkedHashMap

LinkedHashMap<Node,ArrayList<Node>> map=new LinkedHashMap<Node,ArrayList<Node>>();

它将每个节点 N 映射到其无与伦比的元素Incomp(N)。

for(int i=0;i<nodes.size();i++)
{
   Node a=nodes.get(i);
   ArrayList<Node> tmp=new ArrayList<Node>();
   for(int j=i+1;j<nodes.size();j++)
   {
      Node b=nodes.get(j);
      if(isIncomparable(a,b))
           tmp.add(b)
   }
   map.put(a,tmp);
}

例如：假设元素是 {A,B,C,D} 具有以下关系 A>B, A>C, D>C 那么

Incomp(A)={D}
Incomp(B)={C,D}
Incomp(C)={}
Incomp(D)={}

请注意，不允许重复（即Incomp(C)={B}，但由于 (B,C) 在Incomp(B)我们不需要重复它）。

我被困在这里。我应该只检查Incomp(N)元素之间的不可比性，然后将最大尺寸的密钥作为最大反链吗？换句话说，如何通过这个设置找到最大的反链？

我不能生成所有大小为 k 的子集，因为这将是低效的。

4

0 回答 0