Создание двоичного дерева на Java для целей генетического программирования

Question

Я работаю над проектом для курса по разработке программного обеспечения, который учусь.Цель состоит в том, чтобы разработать программу, которая будет использовать генетическое программирование для генерации математического выражения, соответствующего предоставленным обучающим данным.

Я только начал работать над проектом и пытаюсь понять, как создать двоичное дерево, которое позволит задавать высоту дерева, определяемую пользователем, и хранить каждый узел отдельно, чтобы упростить кроссовер и мутацию, когда я доберусь до этого. реализации этих процессов.

Вот классы узлов, которые я создал на данный момент.Пожалуйста, простите меня за очевидную неопытность.

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

Это дает все, что мне нужно, из самих узлов, но я сталкиваюсь с проблемами, пытаясь понять, как превратить их в большее дерево.Я понимаю, что мне нужно использовать какой-то тип коллекции, но не могу найти в библиотеке тот, который кажется подходящим для того, что я пытаюсь сделать.

Даже толчок в правильном направлении был бы очень признателен.

Answer 1

Итак, вы хотите построить случайное дерево OperatorNodeс, OperandNodeпесок XNodeс?И вы сказали, что хотите, чтобы глубина дерева определялась пользователем?

Определите рекурсивную функцию с именем buildRandomTree или что-то подобное.Это должно занять один int параметр глубины дерева.Если параметр глубины равен 1, возвращает случайный листовой узел (OperandNode или XNode).Если параметр глубины больше 1, сгенерируйте случайный OperationNode и выполните рекурсивные вызовы для создания левого и правого поддеревьев (с глубиной на 1 меньше текущего уровня).

В зависимости от того, что вы хотите делать с узлами, вам придется определить другие рекурсивные функции.Например, вы, вероятно, захотите создать текстовые представления ваших деревьев выражений.Для этого вы можете определить toString() на каждом из классов узлов.(OperatorNode.toString() придется позвонить toString() в левом и правом поддеревьях.)

Вероятно, вам также захочется оценить деревья выражений (с заданными значениями переменных).Для этого вы можете определить другую рекурсивную функцию, возможно, называемую evaluate().Ему придется принять один параметр, возможно, Map, который даст значения переменных (или «привязки»), с помощью которых вы хотите оценить выражение.(Сейчас ваши деревья выражений могут содержать только одну переменную «x», но я думаю, вы захотите добавить больше.Если вы уверены, что будете использовать только одну переменную, тогда evaluate может принимать один числовой аргумент в качестве значения «x».)

Реализация evaluate для ваших трех классов узлов все будет очень просто. OperandNode и VariableNode просто вернет значение напрямую; OperatorNode придется позвонить evaluate в левом и правом поддеревьях объедините значения с помощью соответствующей операции, а затем верните результат.

Answer 2

Может быть, глядя на Это поможет вам.

.