производительность — эффективность при переполнении стека

Я пытаюсь настроить дерево (в конечном итоге для использования в «нейронной сети» и пытаюсь сделать настройку максимально эффективной. К сожалению, даже настройка дерева занимает около 3 минут, и я не могу понять, что из-за этого делает его настолько неэффективным? Я пытался использовать указатели везде, где это возможно, чтобы минимизировать нагрузку, но это все еще занимает вечность. Что я делаю не так?

PS. Это в конечном итоге для ИИ Tic Tac Toe (да, я знаю, что это можно решить, просто взглянув на глупую игру, но я хотел сделать это как простой ИИ, чтобы научить себя, как.

Каждая ветвь дерева будет иметь 9 узлов, каждый из которых разветвляется, чтобы получить еще 9. Это дает последнему набору ветвей приблизительно 400 миллионов узлов. Есть ли ЛЮБОЙ способ сделать этот код более эффективно?

#include <iostream>
#include <vector>using namespace std;

class Node;
class Set;class Node {
public:
Node(double, Set*);
Node();
double value;
Set * nextSet;
};
class Set {
public:
Set(vector<Node *>);
Set();
vector<Node *> nodes;
};
class NeuralNet {
public:
Set * firstSet;
};
Node::Node(double val, Set * newSet){
value = val;
nextSet = newSet;
}
Set::Set(vector<Node *> input){
nodes = input;
}
Node::Node(){
Set temp;
nextSet = &temp;
}
Set::Set(){
vector<Node *> temp;
nodes = temp;
}
void setUpNeuralNetRecursive(Set * curSet, int curDepth){
if(curDepth<9){
for(int i=0;i<9;i++){
Set newSet;
Node newNode(1,&newSet);
(*curSet).nodes.push_back(&newNode);
setUpNeuralNetRecursive(&newSet, curDepth+1);
}
}
}
void setUpNeuralNet(NeuralNet net){
Set newSet;
net.firstSet=&newSet;
setUpNeuralNetRecursive(&newSet, 0);
}
int main()
{
cout << "Setting up neural network.  This may take up to 3 minutes." << endl;
NeuralNet net;
setUpNeuralNet(net);
cout << "Setup ended." << endl;

return 0;
}

6

Решение

У вас полностью сбалансированное 9-и дерево? не выделить узел для каждого элемента! Вместо этого выделите массив для ваших узлов и перемещайтесь по дереву, используя вычисления:

  • Для навигации от узла i его родителю вы бы вычислили (i - 1) / 9
  • Чтобы найти самого левого ребенка, которого вы бы вычислили i * 9 + 1

(или что-то вроде этого; это среди ночи, и я не совсем в курсе этой математики). В любом случае вы можете перемещаться по полностью сбалансированному n-арному дереву, используя такую ​​формулу. Этот подход, например, используется для D-куч. Преимущество этого подхода состоит в том, что у вас есть только одно большое выделение, и навигация по дереву становится вычислением, а не поиском памяти.

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

3

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector