C++决策树实现问题: Think In Code

Question

我已经编码了几年，但我仍然没有掌握伪编码的窍门，也没有真正用代码思考问题。由于这个问题，我无法弄清楚在创建学习决策树时究竟要做什么。

这是我看过的一些网站相信我还有很多

Decision Tree Tutorials

DMS Tutorials

还有几本书，例如 Ian Millington 的 AI for Games，其中包括对决策树中使用的不同学习算法的详细介绍，以及基本上都是关于决策树和理论的游戏编程行为数学。我了解决策树的概念以及熵、ID3 和一些关于如何交织遗传算法并让决策树决定 GA 节点的知识。他们提供了很好的洞察力，但不是我真正想要的。

我确实有一些为决策树创建节点的基本代码，我相信我知道如何实现实际逻辑，但如果我对程序没有目的或者没有熵或学习算法，那它就没有用涉及。

我想问的是，有人可以帮我弄清楚我需要做什么来创建这个学习决策树。我的节点在它们自己的类中，它们通过函数来​​创建树，但是我如何将熵放入其中，它是否应该有一个类，一个结构，我不确定如何将它组合在一起。伪代码和我将使用所有这些理论和数字去向何处的想法。只要我知道我需要编码什么，我就可以把代码放在一起。任何指导将不胜感激。

基本上，我将如何处理这个问题。

添加学习算法，例如 ID3 和 Entropy。应该如何设置？

一旦我确实弄清楚了如何处理这一切，我计划将其实现到一个状态机中，该状态机以游戏/模拟格式经历不同的状态。所有这些都已经设置好了，我只是认为它可以是独立的，一旦我弄明白了，我就可以将它移到另一个项目中。

这是我目前拥有的源代码。

提前致谢!

Main.cpp:

int main()
{
    //create the new decision tree object
    DecisionTree* NewTree = new DecisionTree();

    //add root node   the very first 'Question' or decision to be made
    //is monster health greater than player health?
    NewTree->CreateRootNode(1);

    //add nodes depending on decisions
    //2nd decision to be made
    //is monster strength greater than player strength?
    NewTree->AddNode1(1, 2);

    //3rd decision
    //is the monster closer than home base?
    NewTree->AddNode2(1, 3);

    //depending on the weights of all three decisions, will return certain node result
    //results!
    //Run, Attack, 
    NewTree->AddNode1(2, 4);
    NewTree->AddNode2(2, 5);
    NewTree->AddNode1(3, 6);
    NewTree->AddNode2(3, 7);

    //Others: Run to Base ++ Strength, Surrender Monster/Player, 
    //needs to be made recursive, that way when strength++ it affects decisions second time around DT

    //display information after creating all the nodes
    //display the entire tree, i want to make it look like the actual diagram!
    NewTree->Output();

    //ask/answer question decision making process
    NewTree->Query();

    cout << "Decision Made. Press Any Key To Quit." << endl;

    //pause quit, oh wait how did you do that again...look it up and put here

    //release memory!
    delete NewTree;

    //return random value
    //return 1;
}

决策树.h:

//the decision tree class
class DecisionTree
{
public:
    //functions
    void RemoveNode(TreeNodes* node);
    void DisplayTree(TreeNodes* CurrentNode);
    void Output();
    void Query();
    void QueryTree(TreeNodes* rootNode);
    void AddNode1(int ExistingNodeID, int NewNodeID);
    void AddNode2(int ExistingNodeID, int NewNodeID);
    void CreateRootNode(int NodeID);
    void MakeDecision(TreeNodes* node);

    bool SearchAddNode1(TreeNodes* CurrentNode, int ExistingNodeID, int NewNodeID);
    bool SearchAddNode2(TreeNodes* CurrentNode, int ExistingNodeID, int NewNodeID);

    TreeNodes* m_RootNode;

    DecisionTree();

    virtual ~DecisionTree();
};

Decisions.cpp:

int random(int upperLimit);

//for random variables that will effect decisions/node values/weights
int random(int upperLimit)
{
    int randNum = rand() % upperLimit;
    return randNum;
}

//constructor
//Step 1!
DecisionTree::DecisionTree()
{
    //set root node to null on tree creation
    //beginning of tree creation
    m_RootNode = NULL;
}

//destructor
//Final Step in a sense
DecisionTree::~DecisionTree()
{
    RemoveNode(m_RootNode);
}

//Step 2!
void DecisionTree::CreateRootNode(int NodeID)
{
    //create root node with specific ID
    // In MO, you may want to use thestatic creation of IDs like with entities. depends on how many nodes you plan to have
    //or have instantaneously created nodes/changing nodes
    m_RootNode = new TreeNodes(NodeID);
}

//Step 5.1!~
void DecisionTree::AddNode1(int ExistingNodeID, int NewNodeID)
{
    //check to make sure you have a root node. can't add another node without a root node
    if(m_RootNode == NULL)
    {
        cout << "ERROR - No Root Node";
        return;
    }

    if(SearchAddNode1(m_RootNode, ExistingNodeID, NewNodeID))
    {
        cout << "Added Node Type1 With ID " << NewNodeID << " onto Branch Level " << ExistingNodeID << endl;
    }
    else
    {
        //check
        cout << "Node: " << ExistingNodeID << " Not Found.";
    }
}

//Step 6.1!~ search and add new node to current node
bool DecisionTree::SearchAddNode1(TreeNodes *CurrentNode, int ExistingNodeID, int NewNodeID)
{
    //if there is a node
    if(CurrentNode->m_NodeID == ExistingNodeID)
    {
        //create the node
        if(CurrentNode->NewBranch1 == NULL)
        {
            CurrentNode->NewBranch1 = new TreeNodes(NewNodeID);
        }
        else 
        {
            CurrentNode->NewBranch1 = new TreeNodes(NewNodeID);
        }
        return true;
    }
    else
    {
        //try branch if it exists
        //for a third, add another one of these too!
        if(CurrentNode->NewBranch1 != NULL)
        {
            if(SearchAddNode1(CurrentNode->NewBranch1, ExistingNodeID, NewNodeID))
            {
                return true;
            }
            else
            {
                //try second branch if it exists
                if(CurrentNode->NewBranch2 != NULL)
                {
                    return(SearchAddNode2(CurrentNode->NewBranch2, ExistingNodeID, NewNodeID));
                }
                else
                {
                    return false;
                }
            }
        }
        return false;
    }
}

//Step 5.2!~    does same thing as node 1.  if you wanted to have more decisions, 
//create a node 3 which would be the same as this maybe with small differences
void DecisionTree::AddNode2(int ExistingNodeID, int NewNodeID)
{
    if(m_RootNode == NULL)
    {
        cout << "ERROR - No Root Node";
    }

    if(SearchAddNode2(m_RootNode, ExistingNodeID, NewNodeID))
    {
        cout << "Added Node Type2 With ID " << NewNodeID << " onto Branch Level " << ExistingNodeID << endl;
    }
    else
    {
        cout << "Node: " << ExistingNodeID << " Not Found.";
    }
}

//Step 6.2!~ search and add new node to current node
//as stated earlier, make one for 3rd node if there was meant to be one
bool DecisionTree::SearchAddNode2(TreeNodes *CurrentNode, int ExistingNodeID, int NewNodeID)
{
    if(CurrentNode->m_NodeID == ExistingNodeID)
    {
        //create the node
        if(CurrentNode->NewBranch2 == NULL)
        {
            CurrentNode->NewBranch2 = new TreeNodes(NewNodeID);
        }
        else 
        {
            CurrentNode->NewBranch2 = new TreeNodes(NewNodeID);
        }
        return true;
    }
    else
    {
        //try branch if it exists
        if(CurrentNode->NewBranch1 != NULL)
        {
            if(SearchAddNode2(CurrentNode->NewBranch1, ExistingNodeID, NewNodeID))
            {
                return true;
            }
            else
            {
                //try second branch if it exists
                if(CurrentNode->NewBranch2 != NULL)
                {
                    return(SearchAddNode2(CurrentNode->NewBranch2, ExistingNodeID, NewNodeID));
                }
                else
                {
                    return false;
                }
            }
        }
        return false;
    }
}

//Step 11
void DecisionTree::QueryTree(TreeNodes* CurrentNode)
{
    if(CurrentNode->NewBranch1 == NULL)
    {
        //if both branches are null, tree is at a decision outcome state
        if(CurrentNode->NewBranch2 == NULL)
        {
            //output decision 'question'
            ///////////////////////////////////////////////////////////////////////////////////////
        }
        else
        {
            cout << "Missing Branch 1";
        }
        return;
    }
    if(CurrentNode->NewBranch2 == NULL)
    {
        cout << "Missing Branch 2";
        return;
    }

    //otherwise test decisions at current node
    MakeDecision(CurrentNode);
}

//Step 10
void DecisionTree::Query()
{
    QueryTree(m_RootNode);
}

////////////////////////////////////////////////////////////
//debate decisions   create new function for decision logic

// cout << node->stringforquestion;

//Step 12
void DecisionTree::MakeDecision(TreeNodes *node)
{
    //should I declare variables here or inside of decisions.h
    int PHealth;
    int MHealth;
    int PStrength;
    int MStrength;
    int DistanceFBase;
    int DistanceFMonster;

    ////sets random!
    srand(time(NULL));

    //randomly create the numbers for health, strength and distance for each variable
    PHealth = random(60);
    MHealth = random(60);
    PStrength = random(50);
    MStrength = random(50);
    DistanceFBase = random(75);
    DistanceFMonster = random(75);

    //the decision to be made string example: Player health: Monster Health:  player health is lower/higher
    cout << "Player Health: " << PHealth << endl;
    cout << "Monster Health: " << MHealth << endl;
    cout << "Player Strength: " << PStrength << endl;
    cout << "Monster Strength: " << MStrength << endl;
    cout << "Distance Player is From Base: " << DistanceFBase << endl;
    cout << "Disntace Player is From Monster: " << DistanceFMonster << endl;

    //MH > PH
    //MH < PH
    //PS > MS
    //PS > MS
    //DB > DM
    //DB < DM

    //good place to break off into different decision nodes, not just 'binary'

    //if statement lower/higher query respective branch
    if(PHealth > MHealth)
    {
    }
    else
    {
    }
    //re-do question for next branch. Player strength: Monster strength: Player strength is lower/higher
    //if statement lower/higher query respective branch
    if(PStrength > MStrength)
    {
    }
    else
    {
    }

    //recursive question for next branch. Player distance from base/monster. 
    if(DistanceFBase > DistanceFMonster)
    {
    }
    else
    {
    }
    //DECISION WOULD BE MADE
    //if statement?
    // inside query output decision?
    //cout <<  << 

        //QueryTree(node->NewBranch2);

        //MakeDecision(node);
}

//Step.....8ish?
void DecisionTree::Output()
{
    //take repsective node
    DisplayTree(m_RootNode);
}

//Step 9
void DecisionTree::DisplayTree(TreeNodes* CurrentNode)
{
    //if it doesn't exist, don't display of course
    if(CurrentNode == NULL)
    {
        return;
    }

    //////////////////////////////////////////////////////////////////////////////////////////////////
    //need to make a string to display for each branch
    cout << "Node ID " << CurrentNode->m_NodeID << "Decision Display: " << endl;

    //go down branch 1
    DisplayTree(CurrentNode->NewBranch1);

    //go down branch 2
    DisplayTree(CurrentNode->NewBranch2);
}

//Final step at least in this case. A way to Delete node from tree. Can't think of a way to use it yet but i know it's needed
void DecisionTree::RemoveNode(TreeNodes *node)
{
    //could probably even make it to where you delete a specific node by using it's ID
    if(node != NULL)
    {
        if(node->NewBranch1 != NULL)
        {
            RemoveNode(node->NewBranch1);
        }

        if(node->NewBranch2 != NULL)
        {
            RemoveNode(node->NewBranch2);
        }

        cout << "Deleting Node" << node->m_NodeID << endl;

        //delete node from memory
        delete node;
        //reset node
        node = NULL;
    }
}

TreeNodes.h:

using namespace std;
//tree node class
class TreeNodes
{
public:
    //tree node functions
    TreeNodes(int nodeID/*, string QA*/);
    TreeNodes();

    virtual ~TreeNodes();

    int m_NodeID;

    TreeNodes* NewBranch1;
    TreeNodes* NewBranch2;
};

TreeNodes.cpp:

//contrctor
TreeNodes::TreeNodes()
{
    NewBranch1 = NULL;
    NewBranch2 = NULL;

    m_NodeID = 0;
}

//deconstructor
TreeNodes::~TreeNodes()
{ }

//Step 3! Also step 7 hah!
TreeNodes::TreeNodes(int nodeID/*, string NQA*/)
{
    //create tree node with a specific node ID
    m_NodeID = nodeID;

    //reset nodes/make sure! that they are null. I wont have any funny business #s -_-
    NewBranch1 = NULL;
    NewBranch2 = NULL;
}

Answer 1

如果我错了请纠正我，但从 http://dms.irb.hr/tutorial/tut_dtrees.php 的图片来看和 http://www.decisiontrees.net/?q=node/21实际的决策逻辑应该放在节点中，而不是树中。您可以通过使用多态节点对其进行建模，每个节点对应一个决策。对树结构进行一些更改并对决策委托(delegate)进行少量修改，您的代码应该没问题。