獨立集合的算法總數總是減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(); 
}