独立集合的算法总数总是减1

Question

我在编写算法来计算树中独立集合的数量时遇到了困难。 （一个独立的组为其中任意两个节点之间有没有边。）

这里是我的ListNode java类：

1public class ListNode 
2{ 
3 private Object data; 
4 private ListNode next; 
5 
6 public ListNode(Object data, ListNode next) 
7 { 
8  this.data = data; 
9  this.next = next; 
10 } 
11 
12 public Object getData() {return data;} 
13 public ListNode getNext(){return next;} 
14 public void setNext(ListNode n){next = n;} 
15 public void setData(Object d){data = d;} 
16 public boolean search(ListNode l, Object o) 
17 { 
18  while (l != null){ 
19   if (l.getData().equals(o)) 
20    return true; 
21   l = l.getNext(); 
22  } 
23  return false; 
24 } 
25 public static ListNode rev(ListNode curr) 
26 { 
27  ListNode rev = null; 
28  while (curr != null){ 
29   rev = new ListNode(curr.getData(), rev); 
30   curr = curr.getNext(); 
31  } 
32  return rev;}} 

而且我对树节点java类：

1public class TreeNode 
2{ ListNode children = null; 
3 public void addChild(TreeNode t) 
4 { 
5  if (children == null) 
6   children = new ListNode(t, null); 
7  else{ 
8   ListNode curr = children; 
9   while (curr.getNext() != null) 
10    curr = curr.getNext(); 
11   curr.setNext(new ListNode(t, null)); 
12  }} 
13 public void setChildren(ListNode t){this.children = t;} 
14 public int numStableSet() 
15 { 
16 
17  if (children == null || children.getNext() == null) 
18   return 2; 
19  else{ 
20   int count = 2; 
21   setChildren(children.getNext()); 
22   count *= numStableSet(); 
23   return count; 
24  } 
25 } 

方法numStableSet是我需要一些编码帮助的地方。如现在设置，它打印出1比正确的答案少。我还没有想出每个节点本身可能是树的情况。

帮助赞赏

Answer 1

我不相信你的算法总是会关闭一个。我们来看几个例子，从最简单的例子开始。

• 否节点=> 1分独立集，空集
• 一个节点=> 2个独立的集，空和所述一个节点
• 父母一方，其唯一子=> 3分独立集，空和节点

由于你的代码似乎给单个节点和单个子节点的结果都是2，所以我相信你的代码是错误的。

现在我们来看看递归情况，找到正确的算法。您正在访问给定的节点。你可以决定在而不是包含稳定集中的那个节点，然后访问它的所有子节点并为这些节点选择任意的稳定集。或者你可以决定包含当前节点，但是只有当它自己的父节点没有被包括时，并且当递归到子节点时，你必须确保不计数它们。跟踪所有可能的方法来结合这些选择，并且你有数。在Python的伪代码：

def combinationsWithoutCurrent(current): 
    num = 1 
    for child in current: 
    num *= stableSet(child) 
    return num 

def combinationsWithCurrent(current): 
    num = 1 
    for child in current: 
    num *= combinationsWithoutCurrent(child) 
    return num 

def stableSet(current): 
    return (combinationsWithCurrent(current) + 
      combinationsWithoutCurrent(current)) 

为您喜欢Java和晦涩的手工制作的容器类，这里是我怎么猜到你的数据结构旨在一些Java代码。由于您从不在调用遍历树中调用getData，所以在您的代码中看不到任何实际的递归。所以我的猜测可能是错误的。

private int combinationsWithoutCurrent() { 
    int num = 1; 
    for (ListNode iter = children; iter != null; iter = iter.getNext()) 
    num *= ((TreeNode)iter.getData()).numStableSets(); 
    return num; 
} 

private int combinationsWithCurrent() { 
    int num = 1; 
    for (ListNode iter = children; iter != null; iter = iter.getNext()) 
    num *= ((TreeNode)iter.getData()).combinationsWithoutCurrent(); 
    return num; 
} 

public int numStableSet() { 
    return combinationsWithCurrent() + combinationsWithoutCurrent(); 
}