How can i make this algorithm more memory efficient?

Question

I have been working on this piece of code for a couple of days and it seems to work just fine for search trees of relative small size, but working with higher ones gives segmentation fault.

I have tried to find the specific place where such error comes from by using printing flags, and it seems to break at the is_goal() function. But the code of that function can be assumed as correct.

So the problems seems to be a memory problem, that's why I have the queue in the heap, and also the Nodes that I am creating. But it still crashes.

Are there any more memory saving tricks that can be taking into account that I am not using? Or maybe there is a better way to save such nodes?

It is important to note that I need to use BFS (I can't use A* to make the search tree smaller).

Also if you need to know, the map is a hash table where I save the coloring of the nodes so I don't have duplicates when exploring (This is because the hash saves depending on the state information and not the Node information).

EDIT: i have been told to indicate the goal to accomplish, such is to find the goal state in the search tree, the goal is to be be able to iterate over big problems like rubik 3x3x3, n-puzzle 4x4 5x5, tower of hanoi and such.To do so, the memory used has to be minimal since the search tree of such problems are really big, the final objective is to compare this algorithm with others like a*, dfid, ida*, and so on. I hope this is enough information.

  Node* BFS(state_t start ){

    state_t state, child;  
    int d, ruleid;
    state_map_t *map = new_state_map();
    ruleid_iterator_t iter;
    std::queue<Node*> *open = new std::queue<Node*>();

    state_map_add( map, &start, 1); 

    Node* n = new Node(start);
    open->push(n);

    while( !open->empty() ) {
        n = open->front();
        state = n->get_state();
        open->pop();

        if (is_goal(&state) == 1) return n;

        init_fwd_iter( &iter, &state ); 

        while( ( ruleid = next_ruleid( &iter ) ) >= 0 ) {
            apply_fwd_rule( ruleid, &state, &child );


            const int *old_child_c = state_map_get( map, &child );
            if ( old_child_c == NULL ) {
                state_map_add( map, &child, 1 );
                Node* nchild = new Node(child); 
                open->push(nchild);
            }

        }

    }

    return NULL;
}  

Answer 1

I see a number of memory leaks.

open is never deleted but maybe could allocated in the stack instead of in the heap.

std::queue<Node*> open;

More important none of the node you push in the queue are deleted this is probably the origin of very big memory consumption.

Delete the nodes that you remove from the queue and that you don't plan to reuse. Delete the nodes of the queue before your get rid of the queue.

Node* BFS(state_t start ){

    state_t state, child;  
    int d, ruleid;
    state_map_t *map = new_state_map();
    ruleid_iterator_t iter;
    std::queue<Node*> open;

    state_map_add( map, &start, 1); 

    Node* n = new Node(start);
    open.push(n);

    while( !open.empty() ) {
        n = open.front();
        state = n->get_state();
        open.pop();

        if (is_goal(&state) == 1) {
            for (std::queue<Node*>::iterator it = open.begin(); it != open.end(); ++it)
                delete *it;

            return n;
        }
        else {
            delete n;
        }

        init_fwd_iter( &iter, &state ); 

        while( ( ruleid = next_ruleid( &iter ) ) >= 0 ) {
            apply_fwd_rule( ruleid, &state, &child );


            const int *old_child_c = state_map_get( map, &child );
            if ( old_child_c == NULL ) {
                state_map_add( map, &child, 1 );
                Node* nchild = new Node(child); 
                open.push(nchild);
            }

        }

    }

    return NULL;
}