Tworzenie drzewa binarnego w Javie do celów programowania genetycznego

Question

Pracuję nad projektem na zajęcia z inżynierii oprogramowania, które prowadzę. Celem jest zaprojektowanie programu, który będzie wykorzystywał programowanie genetyczne do generowania matematycznego wyrażenia pasującego do dostarczonych danych treningowych.

Właśnie rozpocząłem pracę nad projektem i staram się owijać głowę, jak stworzyć drzewo binarne, które pozwoli na zdefiniowanie przez użytkownika wysokości drzewa i utrzymać każdy węzeł osobno, aby ułatwić krosowanie i mutację. kiedy dojdę do wdrożenia tych procesów.

Oto klasy węzłów, które utworzyłem do tej pory. Proszę, wybacz, jestem pewien, że jestem ewidentnym brakiem doświadczenia.

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

ten osiąga wszystko, czego potrzebujesz z samymi węzłami, ale biegnę do problemów próbuje dowiedzieć się, jak włączyć je do większego drzewa. Zdaję sobie sprawę, że muszę użyć jakiegoś rodzaju kolekcji, ale nie mogę znaleźć takiego w Bibliotece, który wydaje się odpowiedni dla tego, co próbuję zrobić.

Nawet docieranie w dobrym kierunku byłoby bardzo cenne.

Answer 1

Więc chcesz zbudować losowe drzewo o numerach OperatorNode s, OperandNode s oraz XNode s? A Ty powiedziałeś, że chcesz zdefiniować użytkownika głębi drzewa?

Definiowanie funkcji rekurencyjnej o nazwie buildRandomTree lub podobnej. Powinien mieć pojedynczy parametr int dla głębokości drzewa. Jeśli parametr depth ma wartość 1, zwróć losowy węzeł liścia (OperandNode lub XNode). Jeśli parametr głębokości jest większy niż 1, wygeneruj przypadkowy węzeł OperatorNode i wywołaj rekursywnie, aby wygenerować lewe i prawe poddrzewnie (z głębokością 1 mniejszą niż bieżący poziom).

W zależności od tego, co chcesz zrobić z węzłami, będziesz musiał zdefiniować inne funkcje rekursywne. Na przykład prawdopodobnie będziesz chciał wygenerować tekstowe reprezentacje drzewek wyrażeń. W tym celu można zdefiniować toString() dla każdej z klas węzłów. (OperatorNode.toString() będzie musiał zadzwonić pod numer toString() po lewej i prawej poddrzewi).

Prawdopodobnie będziesz chciał również ocenić drzewa wyrażeń (z podanymi wartościami dla zmiennych). W tym celu można zdefiniować inną funkcję rekursywną, na przykład o nazwie evaluate(). Będzie musiał przyjąć jeden parametr, prawdopodobnie Map, który da wartości zmiennych (lub "wiązań"), z którymi chcesz ocenić wyrażenie. (W tej chwili twoje drzewa wyrażeń mogą zawierać tylko jedną zmienną "x", ale wyobrażam sobie, że możesz dodać więcej.Jeśli masz pewność, że będziesz używać tylko jednej zmiennej, to evaluate może przyjąć pojedynczy argument numeryczny dla wartości "x".)

Implementacja evaluate dla twoich klas 3-węzłowych będzie bardzo prosta. OperandNode i VariableNode po prostu zwrócą wartość bezpośrednio; OperatorNode będzie musiał zadzwonić pod numer evaluate po lewej i prawej poddrzewi, połączyć wartości za pomocą odpowiedniej operacji, a następnie zwrócić wynik.

Answer 2

Może pomóc Ci this.