在 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
s, OperandNode
沙 XNode
是?你说你想让树深度由用户定义?
定义一个递归函数,称为 buildRandomTree
或类似的东西。应该需要一个 int
树深度参数。如果深度参数为1,则返回一个随机叶节点(OperandNode或XNode)。如果深度参数大于1,则随机生成一个OperatorNode,并递归调用生成左右子树(深度比当前层级小1)。
根据您想要对节点执行的操作,您必须定义其他递归函数。例如,您可能想要生成表达式树的文本表示。为此,您可以定义 toString()
在每个节点类上。(OperatorNode.toString()
必须打电话 toString()
在左子树和右子树上。)
您可能还想评估表达式树(使用给定的变量值)。为此,您可以定义另一个递归函数,可能称为 evaluate()
. 。它必须采用一个参数,可能是一个 Map
, ,这将给出您想要用来评估表达式的变量值(或“绑定”)。(现在你的表达式树只能包含一个变量“x”,但我想你可能想添加更多。如果您确定只会使用单个变量,那么 evaluate
可以采用单个数字参数作为“x”的值。)
实施 evaluate
你的 3 个节点类都会非常简单。 OperandNode
和 VariableNode
直接返回一个值; OperatorNode
必须打电话 evaluate
在左子树和右子树上,使用适当的操作组合值,然后返回结果。
其他提示
也许看这个将帮助您。