Crear un árbol binario en Java para fines de programación genética

Question

Estoy trabajando en un proyecto para una clase de ingeniería de software que estoy tomando. El objetivo es diseñar un programa que utilizará la programación genética para generar una expresión matemática que se ajuste a los datos de capacitación proporcionados.

Acabo de empezar a trabajar en el proyecto, y estoy tratando de entender cómo crear un árbol binario que permita la altura del árbol definida por el usuario y mantener cada nodo separado para simplificar el cruce y la mutación cuando llego a implementar esos procesos.

Aquí están las clases de nodo que he creado hasta ahora. Perdón por lo que estoy seguro es mi evidente inexperiencia.

public class Node 
{ 
    Node parent; 
    Node leftchild; 
    Node rightchild; 

    public void setParent(Node p) 
    { 
     parent = p; 
    } 

    public void setLeftChild(Node lc) 
    { 
     lc.setParent(this); 
     leftchild = lc; 
    } 

    public void setRightChild(Node rc) 
    { 
     rc.setParent(this); 
     rightchild = rc; 
    } 
} 


public class OperatorNode extends Node 
{ 
    char operator; 


    public OperatorNode() 
    { 
     double probability = Math.random(); 

     if (probability <= .25) 
     { 
      operator = '+'; 
     } 
     else if (probability > .25 && probability <= .50) 
     { 
      operator = '-'; 
     } 
     else if (probability > .50 && probability <= .75) 
     { 
      operator = '*'; 
     } 
     else 
     { 
      operator = '/'; 
     } 
    } 

    public void setOperator(char op) 
    { 
     if (op == '+' || op == '-' || op == '*' || op == '/') 
     { 
      operator = op; 
     } 
    } 


/** 
* Node that holds x variables. 
*/ 
public class XNode extends Node 
{ 
    char x; 

    public XNode() 
    { 
     x = 'x'; 
    }  
} 

import java.util.Random; 


public class OperandNode extends Node 
{ 
    int operand; 

    /** 
    * Initializes random number generator, sets the value of the node from zero to 9. 
    */ 
    public OperandNode() 
    { 
     Random rand = new Random(); 
     operand = rand.nextInt(10); 
    } 

    /** 
    * Manually changes operand. 
    */ 
    public void setOperand(int o) 
    { 
     operand = o; 
    } 
} 

Con esto se logran todo lo que necesito salir de los propios nodos, pero estoy corriendo en problemas tratando de encontrar la manera de convertirlas en un árbol grande. Me doy cuenta de que necesito usar algún tipo de colección, pero parece que no puedo encontrar una en la Biblioteca que me parezca apropiada para lo que estoy tratando de hacer.

Incluso un pequeño empujón en la dirección correcta sería muy apreciado.

Answer 1

¿Desea construir un árbol al azar de OperatorNode s, OperandNode s y XNode s? ¿Y dijiste que querías definir el árbol de profundidad definido por el usuario?

Defina una función recursiva llamada buildRandomTree o algo similar. Debería tomar un único parámetro int para la profundidad del árbol. Si el parámetro de profundidad es 1, devuelve un nodo de hoja aleatorio (OperandNode o XNode). Si el parámetro de profundidad es mayor que 1, genere un OperatorNode aleatorio y realice llamadas recursivas para generar los subárboles izquierdo y derecho (con una profundidad 1 menor que el nivel actual).

Dependiendo de lo que quieras hacer con los nodos, deberás definir otras funciones recursivas. Por ejemplo, probablemente desee generar representaciones textuales de sus árboles de expresiones. Para eso, puede definir toString() en cada una de las clases de nodo. (OperatorNode.toString() tendrá que llamar al toString() en los subárboles izquierdo y derecho.)

Probablemente también quiera evaluar los árboles de expresión (con valores dados para las variables). Para eso, puede definir otra función recursiva, quizás llamada evaluate(). Tendrá que tomar un parámetro, probablemente un Map, que dará los valores variables (o "enlaces") con los que desea evaluar la expresión. (En este momento, los árboles de expresiones solo pueden contener una sola variable "x", pero imagino que es posible que desee agregar más. Si está seguro de que solo usará una sola variable, entonces evaluate puede tomar un único argumento numérico para el valor de "x".)

La implementación de evaluate para sus 3 clases de nodo será muy simple. OperandNode y VariableNode simplemente devolverá un valor directamente; OperatorNode tendrá que llamar al evaluate en los subárboles izquierdo y derecho, combinar los valores usando la operación apropiada, luego devolver el resultado.

Answer 2

Tal vez mirando this le ayudará.