Créer un arbre binaire en Java à des fins de programmation génétique

Question

Je travaille sur un projet pour un cours de génie logiciel que je prends. L'objectif est de concevoir un programme qui utilisera la programmation génétique pour générer une expression mathématique qui s'adapte à des données d'entraînement.

Je viens de commencer à travailler sur le projet, et j'essaie de comprendre comment créer un arbre binaire qui permettra la hauteur de l'arbre définie par l'utilisateur et garder chaque nœud séparé pour rendre le croisement et la mutation plus simples lorsque j'arrive implémentation de ces processus.

Voici les classes de nœuds que j'ai créées jusqu'à présent. Veuillez pardonner ce que je suis sûr, c'est mon inexpérience évidente.

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

Cela accomplit tout ce dont j'ai besoin des nœuds eux-mêmes, mais je rencontre des problèmes en essayant de comprendre comment les transformer en un arbre plus grand. Je me rends compte que je dois utiliser un type de collection quelconque, mais je n'arrive pas à en trouver un dans la bibliothèque qui semble approprié pour ce que j'essaie de faire.

Même un coup de pouce dans la bonne direction serait grandement apprécié.

Answer 1

Vous voulez donc construire un arbre aléatoire de OperatorNodes, OperandNodele sable XNodes? Et vous avez dit que vous vouliez faire défini l'utilisateur de la profondeur de l'arborescence?

Définir une fonction récursive appelée buildRandomTree ou quelque chose de similaire. Ça devrait prendre un seul int Paramètre pour la profondeur de l'arborescence. Si le paramètre de profondeur est 1, renvoyez un nœud de feuille aléatoire (OperandNode ou Xnode). Si le paramètre de profondeur est supérieur à 1, générez un opératornode aléatoire et faites des appels récursifs pour générer les sous-arbres gauche et droit (avec une profondeur 1 inférieure au niveau actuel).

Selon ce que vous voulez faire avec les nœuds, vous devrez définir d'autres fonctions récursives. Par exemple, vous voudrez probablement générer des représentations textuelles de vos arbres d'expression. Pour ça, tu peux définir toString() sur chacune des classes de nœud. (OperatorNode.toString() devra appeler toString() sur les sous-arbres gauche et droit.)

Vous voudrez probablement également évaluer les arbres d'expression (avec des valeurs données pour les variables). Pour cela, vous pouvez définir une autre fonction récursive, peut-être appelée evaluate(). Il devra prendre un paramètre, probablement un Map, qui donnera les valeurs variables (ou "liaisons") avec lesquelles vous souhaitez évaluer l'expression. (En ce moment, vos arbres d'expression ne peuvent contenir qu'une seule variable "x", mais j'imagine que vous voudrez peut-être en ajouter plus. Si vous êtes sûr que vous n'utiliserez jamais qu'une seule variable, alors evaluate peut prendre un seul argument numérique pour la valeur de "x".)

L'implémentation de evaluate Pour vos 3 classes de nœud seront toutes très simples. OperandNode et VariableNode renvoie simplement une valeur directement; OperatorNode devra appeler evaluate Sur les sous-arbres gauche et droit, combinez les valeurs à l'aide de l'opération appropriée, puis renvoyez le résultat.

Answer 2

Peut-être regarder cette va vous aider.