6

我正在尝试设置一棵树（最终用于“神经网络”并试图使设置尽可能高效。不幸的是，即使设置树也需要大约 3 分钟，我无法弄清楚是什么让它变得如此低效。我试图尽可能使用指针来最小化负载，但它仍然需要永远。我做错了什么？

PS。这最终适用于井字游戏 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。这种方法的优点是您只有一个大的分配并且导航树变成了计算而不是内存查找。

也就是说，我怀疑你是否真的想要这样的树：每一步选择的数量都会变少，你可能想完全杀死某些树枝。不过，树的技术可能仍然有用。

于 2012-11-15T00:53:43.997 回答