Создание двоичного дерева на Java для целей генетического программирования
-
12-11-2019 - |
Вопрос
Я работаю над проектом для курса по разработке программного обеспечения, который учусь.Цель состоит в том, чтобы разработать программу, которая будет использовать генетическое программирование для генерации математического выражения, соответствующего предоставленным обучающим данным.
Я только начал работать над проектом и пытаюсь понять, как создать двоичное дерево, которое позволит задавать высоту дерева, определяемую пользователем, и хранить каждый узел отдельно, чтобы упростить кроссовер и мутацию, когда я доберусь до этого. реализации этих процессов.
Вот классы узлов, которые я создал на данный момент.Пожалуйста, простите меня за очевидную неопытность.
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;
}
}
Это дает все, что мне нужно, из самих узлов, но я сталкиваюсь с проблемами, пытаясь понять, как превратить их в большее дерево.Я понимаю, что мне нужно использовать какой-то тип коллекции, но не могу найти в библиотеке тот, который кажется подходящим для того, что я пытаюсь сделать.
Даже толчок в правильном направлении был бы очень признателен.
Решение
Итак, вы хотите построить случайное дерево 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
в левом и правом поддеревьях объедините значения с помощью соответствующей операции, а затем верните результат.
Другие советы
Может быть, глядя на Это поможет вам.
.