遺傳編程Stackoverflow錯誤

Question

我的代碼似乎做無限遞歸，當我用更深的樹調用它時。 我試圖做到這一點沒有遞歸，而且這很難做，因爲我需要操縱樹本身，無論如何這裏是m代碼。由於

問題是與printPostOrder方法，它到達葉節點和往返打印該葉子節點及其父，直到堆棧溢出

我寧願我後，我完全的代碼，以便你可以得到我想要做的。

節點插入是這樣

import java.util.*; 

public class IPG { 

    class Node { 

     private int arity; 
     private String label; 
     private int value; 
     private Node[] children; 
     protected int visit = 0; 
     protected boolean isVisited = false; 

     public Node(int arity, String label) { 
      this.arity = arity; 
      this.label = label; 
      this.children = new Node[3]; 
     } 

     public Node(Node another) { 
      this.label = another.label; 
      this.arity = another.arity; 
     } 

     @Override 
     public String toString() { 
      return label; 
     } 

     String getLabel() { 
      return label; 
     } 

     void insertChild(int pos, Node n) { 
      if (pos < arity) { 
       children[pos] = n; 
      } 
     } 

     Node getChildAt(int i) { 
      return children[i]; 
     } 

     void setValue(int value) { 
      this.value = value; 
     } 

     int getArity() { 
      return arity; 
     } 

     void replace(Node another) { 
      this.arity = another.arity; 
      this.children = another.children; 
      this.label = another.label; 
     } 

    } 

    private Node[] functions = { new Node(2, "AND"), new Node(2, "OR"), 
      new Node(1, "NOT"), new Node(3, "IF") }; 

    private Node[] terminals = { new Node(0, "A0"), new Node(0, "D1"), 
      new Node(0, "D0"), new Node(0, "A1"), new Node(0, "D2"), 
      new Node(0, "D3"), new Node(0, "A2"), new Node(0, "D4"), 
      new Node(0, "D5"), new Node(0, "D6"), new Node(0, "D7") }; 

    private Random random = new Random(); 

    private int multiplexerType = 3; 

    public Node getTerminal() { 
     return terminals[random.nextInt(multiplexerType)]; 
    } 

    public Node getFunction() { 

     return functions[random.nextInt(3)]; 
    } 

    public Node getAnyNode() { 
     return random.nextInt(2) == 1 ? getFunction() : getTerminal(); 
    } 

    public Node generateGrow(int depth) { 
     Node root; 

     if (depth > 1) 
      root = getAnyNode(); 

     else 
      root = getTerminal(); 

     for (int i = 0; i < root.getArity(); i++) 
      root.insertChild(i, generateGrow(depth - 1)); 

     return root; 
    } 

    public Node generateFull(int depth) { 
     Node root; 

     if (depth > 1) 
      root = getFunction(); 

     else 
      root = getTerminal(); 

     for (int i = 0; i < root.getArity(); i++) 
      root.insertChild(i, generateFull(depth - 1)); 

     return root; 
    } 

    public void printPostOrder() { 
     Node root = generateFull(3); 
     printPostOrder(root); 
    } 

    private void printPostOrder(Node n) { 
     if (n == null) { 
      return; 
     } else { 
      System.out.println(n + " "); 

      printPostOrder(n.children[0]); 
      printPostOrder(n.children[1]); 
      printPostOrder(n.children[2]); 
     } 
    } 

    public static void main(String[] args) { 
     new IPG().printPostOrder(); 
    } 
} 

Answer 1

問題是，當您生成functions陣列時，您只創建每種類型的一個節點，然後getFunction()重新使用這些相同的節點。什麼情況是，如果例如，你插入一個「和」節點及其子也是一個「和」節點，創建一個週期，因爲它們實際上是同一個對象。

這是一個簡單的辦法，你只需要確保創建的getFunction()每次調用一個新的節點，例如像這樣：

private String [] functionNames = {"AND", "OR", "NOT", "IF"}; 
private int [] functionArities = {2,2,1,3}; 

public Node getFunction() { 
    int index = random.nextInt(3); // If you want to use "IF" nodes too this 
            // needs to be nextInt(4) 
    return new Node(functionArities[index],functionNodes[index]); 
} 

Answer 2

有機會的，該圖形是環狀的。只是因爲你使用預先創建的節點並隨機選擇它們。節點越深，概率越高，一個節點插入多次。在那種情況下，你有你的週期，JVM對SSO抱怨。

問題的根源是functions數組（terminals是好的，因爲終端節點沒有任何子節點）。

卸下陣列和爲每個節點創建一個新功能對象。