c++ - 我怎样才能使这个算法的内存效率更高？

Question

我已经在这段代码上工作了几天，看起来 对于相对较小的搜索树工作得很好，但使用较大的搜索树会出现段错误。

我试图通过使用打印标志找到此类错误的具体来源，它似乎在 is_goal() 函数处中断。但是可以假定该函数的代码是正确的。

所以问题似乎是内存问题，这就是为什么我在堆中有队列，还有我正在创建的节点。但它仍然崩溃。

是否还有更多我没有使用的内存节省技巧可以考虑在内？或者也许有更好的方法来保存这些节点？

需要注意的是，我需要使用BFS(我不能使用A*来让搜索树变小)。

此外，如果您需要知道，该 map 是一个哈希表，我在其中保存了节点的颜色，因此在探索时我没有重复(这是因为哈希保存取决于状态信息而不是节点信息).

编辑:有人告诉我指出要完成的目标，例如在搜索树中找到目标状态，目标是能够迭代 诸如 rubik 3x3x3、n-puzzle 4x4 5x5、汉诺塔等大问题。为此，使用的内存必须最少，因为此类问题的搜索树非常大，最终目标是将此算法与其他算法进行比较如 a*、dfid、ida* 等。我希望这是足够的信息。

  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

我看到了一些内存泄漏。

open 永远不会被删除，但也许可以分配到堆栈而不是堆中。

std::queue<Node*> open;

更重要的是，你插入队列的节点都没有被删除，这可能是内存消耗非常大的根源。

删除您从队列中移除且您不打算重用的节点。在摆脱队列之前删除队列中的节点。

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;
}