6

ツリーをセットアップしようとしています (最終的には「ニューラル ネットワーク」で使用するために、セットアップだけをできるだけ効率的にしようとしています。残念ながら、ツリーのセットアップにも約 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;
}
4

1 に答える 1

4

完全にバランスの取れた 9 進木がありますか? 各要素にノードを割り当てないでください! 代わりに、ノードに配列を割り当て、計算を使用してツリーをナビゲートします。

  • ノードiからその親に移動するには、計算します(i - 1) / 9
  • 計算する一番左の子を見つけるにはi * 9 + 1

(またはこのようなもの; 真夜中にあり、私はこの計算を行う準備ができていません)。いずれにせよ、次のような式を使用して、完全にバランスの取れた n 分木をナビゲートできます。このアプローチは、たとえばd-heapsに使用されます。このアプローチの利点は、大きな割り当てが 1 つしかなく、ツリーのナビゲートがメモリ ルックアップではなくコンピューティングになることです。

そうは言っても、あなたが本当にこのような木を望んでいるとは思えません。選択肢の数は移動するたびに少なくなり、おそらく特定の枝を完全に殺したいと思うでしょう。ただし、ツリーの手法はまだ役立つ場合があります。

于 2012-11-15T00:53:43.997 に答える