Criando uma árvore binária em Java para fins de programação genética

Question

Estou trabalhando em um projeto para um curso de engenharia de software que estou cursando.O objetivo é projetar um programa que utilize programação genética para gerar uma expressão matemática que se ajuste aos dados de treinamento fornecidos.

Acabei de começar a trabalhar no projeto e estou tentando entender como criar uma árvore binária que permitirá a altura da árvore definida pelo usuário e manterá cada nó separado para tornar o cruzamento e a mutação mais simples quando eu chegar. implementar esses processos.

Aqui estão as classes de nós que criei até agora.Por favor, perdoe o que tenho certeza de ser minha evidente inexperiência.

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;
    }
}

Isso realiza tudo o que preciso dos próprios nós, mas estou tendo problemas ao tentar descobrir como transformá-los em uma árvore maior.Sei que preciso usar algum tipo de coleção, mas não consigo encontrar na Biblioteca um que pareça apropriado para o que estou tentando fazer.

Mesmo um empurrãozinho na direção certa seria muito apreciado.

Answer 1

Então você quer construir uma árvore aleatória de OperatorNodeé, OperandNodeareia XNodeé?E você disse que quer definir a profundidade da árvore pelo usuário?

Defina uma função recursiva chamada buildRandomTree ou algo semelhante.Deve levar um único int parâmetro para profundidade da árvore.Se o parâmetro de profundidade for 1, retorne um nó folha aleatório (OperandNode ou XNode).Se o parâmetro de profundidade for maior que 1, gere um OperatorNode aleatório e faça chamadas recursivas para gerar as subárvores esquerda e direita (com profundidade 1 menor que o nível atual).

Dependendo do que você deseja fazer com os nós, você terá que definir outras funções recursivas.Por exemplo, você provavelmente desejará gerar representações textuais de suas árvores de expressão.Para isso, você pode definir toString() em cada uma das classes de nós.(OperatorNode.toString() terá que ligar toString() nas subárvores esquerda e direita.)

Você provavelmente também desejará avaliar as árvores de expressão (com determinados valores para as variáveis).Para isso, você pode definir outra função recursiva, talvez chamada evaluate().Terá que levar um parâmetro, provavelmente um Map, que fornecerá os valores das variáveis ​​(ou "ligações") com as quais você deseja avaliar a expressão.(No momento, suas árvores de expressão podem conter apenas uma única variável "x", mas imagino que você queira adicionar mais.Se você tem certeza de que usará apenas uma única variável, então evaluate pode receber um único argumento numérico para o valor de "x".)

A implementação de evaluate para suas classes de 3 nós será tudo muito simples. OperandNode e VariableNode apenas retornará um valor diretamente; OperatorNode terá que ligar evaluate nas subárvores esquerda e direita, combine os valores usando a operação apropriada e retorne o resultado.

Answer 2

Talvez olhando esse Ajudará você.