0

2 つのノード (type1 と type2 と呼ばれる) 間のオークション シナリオを表す大きなゲーム ツリーを生成しています。ノードの第 4 レベルに到達するまで、ツリーは完全に正常に生成されます。 

    #include <iostream>
    #include <vector>
    #include <queue>

    #define LEVEL 8

    using namespace std;

    class payoff_node{
        int agent_1;
        int agent_2;
    };

    class node{
        public:
            /* constructor to set payoff_ptr to NULL */
            node() { 
                payoff_ptr = NULL;
                parent = NULL; 
            }

            /* print the information about the node */
            void printNode(){
                cout << "type: " << type << "\t" << "level: " << level << "\t" << "purse: $" << purse << "\t" << "parent_bid: " << parent_bid << "\t" << "parent:" << parent->getType() << "\t" << endl;
                /*for (int i = 0; i < actions.size() ; i++){
                    cout << actions[i] << endl;
                }*/
            }

            void setType(int t){    type = t;   }

            void setLevel(int l){   level = l;  }

            void setPurse(int p){ 
                purse = p; 

                /* Depending on the purse value the action space is decided */
                for(int i = 0; i <= purse ; i++){
                    actions.push_back(new node);
                }
            }

            void setParentBid(int bid){ parent_bid = bid; }

            void setParent(node &parent_node){  parent = &parent_node;  }



            int getLevel(){ return level; }

            int getParentBid(){ return parent_bid;  }

            int getPurse(){ return purse; }

            node** getParent(){ return &parent; }

            int getType(){ return type; }


            vector<node*> actions;



        private:
            int type;
            int level;
            int purse;

            int parent_bid;
            node* parent;

            payoff_node* payoff_ptr;
    };

    int main(int argc, char* argv[]){
        bool D = false;
        /* Make the root node and set its properties */
        node root_node;
        root_node.setType(1);
        root_node.setLevel(1);
        root_node.setPurse(4);
        root_node.setParentBid(0);

    //  root_node.printNode();  
        queue<node> myQ;
        myQ.push(root_node);

        /* BFS like creation of perfect information tree */
        while(true){
            node &ext = myQ.front();
            if(D)
                cout << "h1" << endl;

            if(ext.getLevel() == LEVEL){
                break;
            }

            if(D)
                cout << "h2" << endl;

            int type = ext.getType();

            if(D)
            cout << "h3" << endl;
            for(int i = 0; i < ext.actions.size() ; i++){
                node &child = *(ext.actions[i]);
            if(D)
            cout << "h4" << endl;
                //process(child);

                /* set parent */
                child.setParent(ext);
            if(D)
            cout << "h5" << endl;

                /* set type  & items won so far */
                if((ext.getLevel()) % 2 == 0){    // i.e. even numbered level, then current round has ended 
                    if(i > ext.getParentBid()){
                        child.setType(type);    
                    }
                    else{
                        int type_val = ( *(*(ext.getParent()))).getType() ;
                        child.setType( type_val );
                    }
                }
                else{
                    if(type == 1){
                        child.setType(2);

                    }
                    else{
                        child.setType(1);

                    }
                }

            if(D)
            cout << "h6" << endl;
                /* set level */
                child.setLevel(ext.getLevel() + 1);
            if(D)
            cout << "h7" << endl;
                /* set purse */
                if(child.getType() == ext.getType()){
                    int val = ext.getPurse() - i;
                    if(val < 0){
                        child.setPurse(0);
                    }
                    else{
                        child.setPurse(val);
                    }
                }
                else{

                    if( *(ext.getParent()) != NULL  ){
                        int val = ( *(ext.getParent()))->getPurse()  - ext.getParentBid();
                        if(val < 0){
                            child.setPurse(0);
                        }
                        else{
                            child.setPurse( val );
                        }
                    }
                    else{
                        child.setPurse(3);
                    }
                }
            if(D)
            cout << "h8" << endl;

                /* set parent bid */
                child.setParentBid(i);


            if(D)
            cout << "h9" << endl;
                /* when the child is ready with all its attributes, add it to the queue */
                myQ.push(child);
                child.printNode();
            }

            cout << endl << endl << "----Next Set of Children----" << endl;
            myQ.pop();

        }



    return 0;

    }

プログラムはこの行でハングしchild.setPurse( val );ます。次の行で計算された値だと思います

    int val = ( *(ext.getParent()))->getPurse()  - ext.getParentBid();

間違っている。*(ext.getParent())ガベージノードを指している場所。24時間以上これを理解できないので、どんな助けでも大歓迎です. ありがとうございました。

4

1 に答える 1

1

キューはタイプのオブジェクトを格納していますnode。キューへのポインタを使用しています。あなたはそれをすべきではありません！メインループを通過するたびにキューからポップすると、オブジェクトが破棄されます。

見て：

node &ext = myQ.front();

// etc...

for(int i = 0; i < ext.actions.size() ; i++){
    node &child = *(ext.actions[i]);
    child.setParent(ext);

    // etc...

    myQ.push(child);
}

myQ.pop();  // <-- POOF!!  Every pointer to 'ext' is now invalid.

キューに追加するたびに、オブジェクトのコピーを作成します。そのコピーを参照するときは、キューの内部コピーを使用しています。最終的に、そのコピーは存在しなくなります。そのポインタを各子の親として設定すると、深刻な問題が発生します。

これがすぐに爆発しない唯一の理由は、node（クリーンアップするためにactions）に適切なデストラクタを提供しないことによってメモリリークが発生しているためです。実装する場合は、コピーコンストラクターも実装する必要があります（または、プライベートの空のコピーコンストラクターを作成してコピーを防止します）。

本当に行う必要があるのは、ポインタを使用するようにキューを変更することです。

queue<node*> myQ;
myQ.push(&root_node);
// etc...
于 2012-10-23T03:22:28.233 に答える