C++での効率

Question

私はツリーを設定しようとしています（最終的には "ニューラルネットワーク"で使用するために、できるだけ効率的にセットアップを行おうとしています）残念なことに、ツリーを設定するのに約3分かかります。できるだけ負荷を最小限に抑えるためにポインターを使用しようとしましたが、それでもなお永遠に何が起こっていますか？私は間違っていますか？

PSこれは最終的にはTic Tac Toe AI（はい、愚かなゲームを見るだけで解決できると知っていますが、私は単純なAIとしてそれをやりたいと思っていました）

ツリーの各枝にはノードが9つあり、各ノードは分岐して別のノード9.最後のブランチセットは約4億ノードになります。このコードをより効率的に行う方法はありますか？

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

Answer 1

あなたは完全にバランスの取れた9進ツリーを持っていますか？ 各要素にノードを割り当てないでください！あなたはi * 9 + 1を計算したい一番左の子を見つけるには(i - 1)/9

を計算したい親にノードiから移動するに

• ：代わりに、ノードの配列を割り当てて、計算を使用してツリーをナビゲート

（これは真夜中にあり、私はこの数学をするのが賢明ではありません）。どのような場合でも、次のような公式を使用して、完全にバランスの取れたn-aryツリーをナビゲートできます。このアプローチは、例えば、d-heapsに使用される。この方法の利点は、1つの大きな割り当てしか持たず、ツリーをナビゲートするだけでメモリのルックアップではなくコンピューティングになるということです。

つまり、私はあなたが本当にこのようなツリーを望んでいるのか疑問に思っています。選択肢の数が移動ごとに小さくなり、特定の支店を完全に殺したいと思うかもしれません。しかし、木のテクニックはまだ役に立つかもしれません。