Как структурировать это дерево узлов? - PullRequest
Новая
       3

Как структурировать это дерево узлов?

2 голосов
/ 11 июля 2010

Я пишу программу на C ++, которая использует генетические методы для оптимизации дерева выражений.

Я пытаюсь написать класс Tree, который имеет в качестве члена данных Node root. Конструктор узлов генерирует случайное дерево узлов с +, -, *, / в качестве узлов и целыми числами в виде листьев.

Я работал над этим некоторое время, и я еще не определился с лучшей структурой. Поскольку мне нужно получить доступ к любому узлу в дереве, чтобы мутировать или скрестить дерево, мне нужно сохранить филион Узлов. Массив подойдет, но кажется, что вектор является рекомендуемым контейнером. 

vector<Node> dict;

Таким образом, класс Tree будет содержать вектор dict со всеми узлами дерева (или указателями на него), корневой узел дерева и переменную для хранения пригодной меры для дерева. 

class Tree
    {
    public:
        typedef vector<Node>dict;
        dict v;
        Node *root;
        float fitness;

        Tree(void);
        ~Tree();
    };

class Node
    {
    public:
        char *cargo;
        Node *parent;
        Node *left;
        Node *right;
        bool entry;
        dict v;
        Node(bool entry, int a_depth, dict v, Node *pparent = 0);
                };

Tree::Tree()
    {
     Node root(true,  tree_depth, v);
    };

Кажется, нет хорошего места, чтобы поставить typedef vector<Node>dict;, потому что, если он идет в определении Tree, он не знает о Node и выдаст ошибку, говоря так. Я не смог найти место для typedef.

Но я даже не уверен, что вектор - лучший контейнер. Узлы просто должны быть последовательно проиндексированы. Контейнер должен будет расти, так как может быть от 200 до 500 узлов.

Ответы [ 3 ]

1 голос
/ 11 июля 2010

Я не думаю, что Node или Tree являются первыми классами для написания.

Я бы начал с Expression. В вашем случае вам нужно как минимум BinaryExpression, а также выражение без подузлов (констант или переменных). Каждое двоичное выражение должно содержать auto_ptr<Expression> lhs и auto_ptr<Expression> rhs.

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

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

1 голос
/ 11 июля 2010

Я думаю, что стандартное двоичное дерево должно подойти ... вот пример узла (двоичного) дерева выражений : 

const int NUMBER = 0,    // Values representing two kinds of nodes.
          OPERATOR = 1;

struct ExpNode {  // A node in an expression tree.

    int kind;        // Which type of node is this?
                     //   (Value is NUMBER or OPERATOR.)
    double number;   // The value in a node of type NUMBER.
    char op;         // The operator in a node of type OPERATOR.
    ExpNode *left;   // Pointers to subtrees,
    ExpNode *right;  //     in a node of type OPERATOR.

    ExpNode( double val ) {
          // Constructor for making a node of type NUMBER.
       kind = NUMBER;
       number = val;
    }

    ExpNode( char op, ExpNode *left, ExpNode *right ) {
          // Constructor for making a node of type OPERATOR.
       kind = OPERATOR;
       this->op = op;
       this->left = left;
       this->right = right;
    }

}; // end ExpNode

Итак, когда вы делаете кроссовер илимутации и вы хотите выбрать случайный узел, вы просто делаете следующее:

  1. Подсчитайте количество узлов в дереве (это нужно сделать только в конструкторе).
  2. Выберите случайный индекс от 0 до размера дерева.
  3. Посетите каждый узел и вычтите 1 из случайного индекса, пока не достигнете нуля.
  4. Верните узел, когда индекс равен 0.

В этом случае вам не нужно ничего знать о родительском узле.Таким образом, спаривание / мутация должны выглядеть следующим образом: 

select nodeX
select nodeY
    if( Rand(0,1) == 1 )
        nodeY->left = nodeX;
    else
        nodeY->right = nodeX;

И это должно быть так ...

0 голосов
/ 11 июля 2010

Вы можете реализовать список по узлам. Тогда каждый узел будет иметь два дополнительных указателя внутри: 

class Node{
...
Node* sequentialPrevious;
Node* sequentialNext;
...
}

И дерево тоже будет: 

class Tree{
...
Node* sequentialFirst;
Node* sequentialLast;
...
}

Чем вы будете вынуждены двунаправленно перемещаться по узлам, просто перейдя на sequentialFirst или sequentialLast, а затем итеративно на sequentialNext или sequentialPrevious Конечно, конструктор и деструктор Node должны быть правильно реализованы, чтобы поддерживать эти указатели в актуальном состоянии.

...