遺伝的プログラミング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アレイを生成するときは、各タイプのノードを1つしか作成していないので、getFunction()はこれらの同じノードを再利用するという問題があります。何が起こるかは、例えば、 "AND"ノードを挿入し、その子ノードも "AND"ノードである場合、実際には同じオブジェクトなのでサイクルが作成されます。

それはあなたがちょうどそうのように、たとえば、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

のようなものです。単に事前に作成されたノードを使用してランダムに選択するからです。ノードが深くなればなるほど、確率は高くなります。そのノードが1回以上挿入されます。その場合、あなたのサイクルがあり、JVMはSSOに不満を持ちます。

問題の根はfunctions配列です（端末ノードに子がないため、terminalsはOKです）。

この配列を削除して、ノードごとにという新しい機能オブジェクトを作成します（）。