C++决策树实现问题:思考代码

Question

我已经编写了几年但我仍然没有得到伪编码或实际上在代码中思考的问题.由于这个问题,我无法确定在创建学习决策树时应该做些什么.

以下是我看过的几个网站,相信我还有更多

决策树教程

DMS教程

除了Ian Millington的AI for Games之类的几本书,其中包括决策树中使用的不同学习算法和游戏编程的行为数学,这基本上都与决策树和理论有关.我理解决策树的概念以及Entropy,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;
}

决策Tree.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上的图像判断实际的决策逻辑应该放在节点中，而不是树中。您可以通过多态节点进行建模，每个节点对应一个要做出的决策。通过对树结构进行一些更改并对决策委托进行一些小的修改，您的代码应该没问题。