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

Question

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

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

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

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

需要注意的是我需要使用BFS（我不能使用A*让搜索树变小）

此外，如果您需要知道，地图是一个散列 table，我在其中保存节点的颜色，因此在探索时我没有重复（这是因为散列根据状态保存信息而不是节点信息）。

编辑：我被告知要指出要完成的目标，例如在搜索树中找到目标状态，目标是能够迭代像 rubik 3x3x3、n-puzzle 4x4 5x5、河内塔和 such.To 这样的大问题，使用的内存必须是最小的，因为这些问题的搜索树非常大，最后的 objective 是将该算法与 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;

更重要的none你在队列中推送的节点被删除这可能是非常大的内存消耗的来源。

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

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

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

How can i make this algorithm more memory efficient?

c++

performance

algorithm

memory

breadth-first-search